A modal perspective on the computational complexity of attribute value grammar

Patrick Blackburn*, Edith Spaan

*Corresponding author

Publikation: Bidrag til tidsskriftTidsskriftartikelpeer review

Abstract

Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computational linguistics are noted.
OriginalsprogEngelsk
TidsskriftJournal of Logic, Language and Information
Vol/bind2
Udgave nummer2
Sider (fra-til)129-169
Antal sider41
ISSN0925-8531
DOI
StatusUdgivet - jun. 1993
Udgivet eksterntJa

Emneord

  • computational complexity
  • modal logic
  • unification formalisms

Citer dette