Paper Info
Title
Underspecified computation of normal forms
Abstract
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 set L' subset 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.
Year
DOI
Venue
2010
10.4230/LIPIcs.RTA.2010.177
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
normal forms,tree automata,incomplete inference,computational linguistics
Discrete mathematics,Logical consequence,Computer science,Computational linguistics,Automaton,Algorithm,Theoretical computer science,Natural language,Computation
Conference
Volume
ISSN
Citations 
6
1868-8969
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Alexander Koller143835.50
Stefan Thater275638.54