A modal perspective on the computational complexity of attribute value grammar

Patrick Blackburn*, Edith Spaan

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-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.

Original languageEnglish
JournalJournal of Logic, Language and Information
Volume2
Issue number2
Pages (from-to)129-169
Number of pages41
ISSN0925-8531
DOIs
Publication statusPublished - Jun 1993
Externally publishedYes

Keywords

  • computational complexity
  • modal logic
  • unification formalisms

Cite this