Guaranteeing Parsing Termination of Unification Grammars

Guaranteeing Parsing Termination of Unification Grammars Efrat Jaeger and Nissim Francez Department of Computer Science Technion, Israel Institute of Technology 32000 Haifa, Israel Shuly Wintner Department of Computer Science University of Haifa 31905 Haifa, Israel Abstract Unification grammars are known to be Turing- equivalent; given a grammar � and a word � , it is undecidable whether ���� �� . 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 satisfies OLP. In this paper we investigate various definitions of OLP, discuss their inter-relations and show that some of them are undecidable. 1 Introduction Context-free grammars are considered to lack the expressive power needed for modelling natural lan- guages. Unification grammars have originated as an extension of context-free grammars, the basic idea being to augment the context-free rules with fea- ture structures (FSs) in order to express additional information. Today, several variants of unification grammars exist, some of which do not necessarily assume an explicit context-free backbone. The recognition problem (also known as the membership problem), for a grammar � and a string � , is whether ��� � �� . The parsing problem, for a grammar � and a string � , is to deliver all parse trees that � induces on � , determining what struc- tural descriptions are assigned by � to � . The rest of this paper is concerned with recognition. Unification grammars have the formal power of Turing machines, thus the recognition problem for them is undecidable. In order to ensure decidability of the recognition problem, a constraint called off- line parsability (OLP) was suggested. The recog- nition problem is decidable for OLP grammars. There exist several variants of OLP in the literature (Pereira and Warren, 1983; Johnson, 1988; Haas, 1989; Torenvliet and Trautwein, 1995; Shieber, 1992; Wintner and Francez, 1999; Kuhn, 1999). Some variants of OLP were suggested without recognizing the existence of all other variants. In this paper we make a comparative analysis of the different OLP variants for the first time. Some re- searchers (Haas, 1989; Torenvliet and Trautwein, 1995) conjecture that some of the OLP variants are undecidable (it is undecidable whether a grammar satisfies the constraint), althoughnone of them gives any proof of it. There exist some variants of OLP for which decidability holds, but these conditions are too restrictive; there is a large class of non-OLP grammars for which parsing termination is guaran- teed. Our main contribution is to show proofs of undecidability for three OLP definitions. Section 2 defines the basic concepts of our for- malism. Section 3 discusses the different OLP defi- nitions. Section 4 gives an analysis of several OLP definitions and the inter-relations among them. Sec- tion 5 proves the undecidability of three of the OLP conditions. 2 Preliminaries The following definitions are based on Francez and Wintner (In preperation) and Carpenter (1992). Grammars …

Content truncated to 500 words