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: 9,357
External links
  •   Try with proxy.
  • Through your library Configure
    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

    6 ( #162,810 of 1,088,753 )

    Recent downloads (6 months)

    1 ( #69,601 of 1,088,753 )

    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.