A modal perspective on the computational complexity of attribute value grammar

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.
Keywords Modal logic  computational complexity  unification formalisms
Categories (categorize this paper)
DOI 10.1007/BF01050635
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 15,879
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
George Gargov & Valentin Goranko (1993). Modal Logic with Names. Journal of Philosophical Logic 22 (6):607 - 636.
Robert Goldblatt (1989). Varieties of Complex Algebras. Annals of Pure and Applied Logic 44 (3):173-242.

View all 11 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

21 ( #134,855 of 1,725,259 )

Recent downloads (6 months)

3 ( #210,900 of 1,725,259 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.