Recognition of Linear Context-Free Rewriting Systems

RECOGNITION OF LINEAR CONTEXT-FREE REWRITING SYSTEMS* Giorgio Satta Institute for Research in Cognitive Science University of Pennsylvania Philadelphia, PA 19104-6228, USA gsatta@linc.cis.upenn.edu ABSTRACT The class of linear context-free rewriting sys- tems has been introduced as a generalization of a class of grammar formalisms known as mildly context-sensitive. The recognition problem for lin- ear context-free rewriting languages is studied at length here, presenting evidence that, even in some restricted cases, it cannot be solved efficiently. This entails the existence of a gap between, for exam- ple, tree adjoining languages and the subclass of lin- ear context-free rewriting languages that generalizes the former class; such a gap is attributed to "cross- ing configurations". A few other interesting conse- quences of the main result are discussed, that con- cern the recognition problem for linear context-free rewriting languages. 1 INTRODUCTION Beginning with the late 70's, there has been a consid- erable interest within the computational linguistics field for rewriting systems that enlarge the gener- ative power of context-free grammars (CFG) both from the weak and the strong perspective, still re- maining far below the power of the class of context- sensitive grammars (CSG). The denomination of mildly context-sensitive (MCS) has been proposed for the class of the studied systems (see [Joshi et al., 1991] for discussion). The rather surprising fact that many of these systems have been shown to be weakly equivalent has led researchers to generalize *I am indebted to Anuj Dawax, Shyam Kaput and Owen Rainbow for technical discussion on this work. I am also grateful to Aravind Joshi for his support in this research. None of these people is responsible for any error in this work. This research was partially funded by the following grants: ARO grant DAAL 03-89-C-0031, DARPA grant N00014-90- J-1863, NSF grant IRI 90-16592 and Ben Franklin grant 91S.3078C-1. 89 the elementary operations involved in only appar- ently different formalisms, with the aim of captur- ing the underlying similarities. The most remark- able attempts in such a direction are found in [Vijay- Shanker et al., 1987] and [Weir, 1988] with the in- troduction of linear context-free rewriting systems (LCFRS) and in [Kasami et al., 1987] and [Seki et a/., 1989] with the definition of multiple context-free grammars (MCFG); both these classes have been in- spired by the much more powerful class of gener- alized context-free grammars (GCFG; see [Pollard, 1984]). In the definition of these classes, the gener- alization goal has been combined with few theoret- ically motivated constraints, among which the re- quirement of efficient parsability; this paper is con- cerned with such a requirement. We show that from the perpective of efficient parsability, a gap is still found between MCS and some subclasses of LCFRS. More precisely, the class of LCFRS is carefully studied along two interesting dimensions, to be pre- cisely defined in the following: a) the fan-out of the grammar and b) the production length. From previous work (see [Vijay-Shanker et al., 1987]) we know that the recognition problem for LCFRS is in P …

Content truncated to 500 words