A modal perspective on the computational complexity of attribute value grammar

Journal of Logic, Language and Information 2 (2):129-169 (1993)
  Copy   BIBTEX


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.



    Upload a copy of this work     Papers currently archived: 77,869

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

76 (#164,945)

6 months
1 (#483,919)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Patrick Blackburn
Roskilde University

Citations of this work

The Price of Universality.Edith Hemaspaandra - 1996 - Notre Dame Journal of Formal Logic 37 (2):174-203.
EXPtime tableaux for ALC.Francesco M. Donini & Fabio Massacci - 2000 - Artificial Intelligence 124 (1):87-138.
Fibred semantics for feature-based grammar logic.Jochen Dörre, Esther König & Dov Gabbay - 1996 - Journal of Logic, Language and Information 5 (3-4):387-422.

View all 10 citations / Add more citations

References found in this work

Past, Present and Future.Arthur Prior - 1967 - Oxford, England: Clarendon Press.
Past, present, and future.Arthur Prior - 1967 - Revue Philosophique de la France Et de l'Etranger 157:476-476.
Dynamic Logic.Lenore D. Zuck & David Harel - 1989 - Journal of Symbolic Logic 54 (4):1480.

View all 14 references / Add more references