Paper: Guaranteeing Parsing Termination Of Unification Grammars

ACL ID C02-1066
Title Guaranteeing Parsing Termination Of Unification Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2002
Authors

Uni cation grammars are known to be Turing- equivalent; given a grammar a0 and a word a1, it is undecidable whether a1a3a2a5a4a7a6 a0a9a8. In order to ensure decidability, several constraints on grammars, com- monly known as off-line parsability (OLP) were suggested. The recognition problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satis es OLP. In this paper we investigate various de nitions of OLP, discuss their inter-relations and show that some of them are undecidable.