Paper: Decidability And Undecidability In Stand-Alone Feature Logics

ACL ID E93-1005
Title Decidability And Undecidability In Stand-Alone Feature Logics
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1993
Authors

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.