Computing relative normal forms in regular tree languages

Alexander Koller and Stefan Thater

In Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA), Edinburgh, 2010.

We solve the problem of computing, out of a regular language L of trees and a rewriting system R, a regular tree automaton describing the subset L' of L of trees which cannot be R-rewritten into a tree in L. We call the elements of L' the relative normal forms of L. We apply our algorithm to the problem of computing weakest readings of sentences in computational linguistics, by approximating logical entailment with a rewriting system, and give the first efficient and practically useful algorithm for this problem. This problem has been open for 25 years in computational linguistics.

Download: Download

BibTeX Entry
@InProceedings{usp-rewriting,
	author = {Alexander Koller and Stefan Thater},
	title = {Computing relative normal forms in regular tree languages},
	year = {2010},
	address = {Edinburgh},
	booktitle = {Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA)}
}

Back: Publications