COMPUTING RELATIVE NORMAL FORMS IN REGULAR TREE LANGUAGES
Alexander K Oller, Stefan Thater · 2010
W e solve the problem of computing, out of a regular language L of trees and a rewriting system R, a regular tree automaton describing the set L ' ⊆ L of trees which cannot be R-rewritten into a tree in L. We call the elements of Lthe 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.