Decidability and Undecidability in stand-alone Feature Logics

Decidability and Undecidability in stand-alone Feature Logics Patrick Blackburn Department of Philosophy, University of Utrecht Heidelberglaan 8, 3584 CS Utrecht, The Netherlands Email: patrick@phil.ruu.nl Edith Spaan Department of Computer Science, SUNY at Buffalo 226 Bell Hall, Buffalo, NY 14260, United States of America Emaih spaan@cs.buffalo.EDU Abstract This paper investigates the complexity of the satisfiability problem for feature logics strong enough to code entire grammars un- aided. We show that feature logics capable of both enforcing re-entrancy and stating linguistic generalisations will have undecid- able satisfiability problems even when most Boolean expressivity has been discarded. We exhibit a decidable fragment, but the restrictions imposed to ensure decidability render it unfit for stand-alone use. The im- port of these results is discussed, and we conclude that there is a need for feature log- ics that are less homogeneous in their treat- ment of linguistic structure. 1 Introduction This paper investigates decidability and undecidabil- ity in stand-alone feature logics, that is, feature logics strong enough to express entire grammars without the assistance of a phrase-structure backbone. Our results are predominately negative and seem appli- cable to most existing stand-alone formalisms. We strengthen a result of [Blackburn and Spaan 1991, 1992] to show that the ability to express re-entraney and the ability to express generalisations about fea- ture structures interact in ways that lead to unde- cidability even if most Boolean expressivity has been dropped from the logic. Even our positive results have a negative flavour. We exhibit a decidable frag- ment, but the restrictions imposed to attain decid- ability render it incapable of encoding interesting grammars unaided. But what is the import of such results? This is the question we turn to in the last section of the paper. Basically, we regard such results as a sign that existing feature logics treat linguistic structure too homogeneously. What is needed are feature log- ics which are more sensitive to the fine structure of linguistic theorising. The paper is relatively self contained, nonetheless the reader may find it helpful to have [Kasper and Rounds 1986, 1990] and [Blackburn and Spaan 1991, 1992] to hand. 2 Preliminaries Feature logics are abstractions from the unifica- tion based formalisms of computational linguistics. Originally feature logics embodied just one compo- nent of unification based formalisms. Early unifica- tion formalisms such as GPSG [Gazdar et al. 1985] and LFG [Kaplan and Bresnan 1982] have impor- tant phrase structure components in addition to their feature passing mechanisms, and the study of feature logic was originally intended to throw light only on the latter. These early unification formMisms are thus highly heterogeneous: they are architectures with roots in both formal language theory and logic. In recent years this picture has changed. For ex- ample, in HPSG [Pollard and Sag 1987] the feature machinery has largely displaced the phrase struc- ture component. Indeed in HPSG the residue of the phrase structure component is coded up as part of the feature system. Logic has swallowed formal lan- guage theory, and in effect the entire …

Content truncated to 500 words