A modal perspective on the computational complexity of attribute value grammar

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.
Keywords Modal logic  computational complexity  unification formalisms
Categories (categorize this paper)
Options
 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: 11,005
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
Patrick Blackburn (1992). Nominal Tense Logic. Notre Dame Journal of Formal Logic 34 (1):56-83.
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 8 references

Citations of this work BETA

No citations found.

Similar books and articles
Analytics

Monthly downloads

Added to index

2009-01-28

Total downloads

14 ( #113,890 of 1,101,138 )

Recent downloads (6 months)

8 ( #27,838 of 1,101,138 )

How can I increase my downloads?

My notes
Sign in to use this feature


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