A modal perspective on the computational complexity of attribute value grammar

DOI10.1007/BF01050635zbMath0793.03018OpenAlexW338087933MaRDI QIDQ1314274

Patrick Blackburn, Edith Hemaspaandra

Publication date: 22 February 1994

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01050635

zbMATH Keywords

Kripke modelspropositional modal logicattribute value grammarfragments of propositional dynamic logicmodal satisfiabilityunification formalisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Natural language processing (68T50)

Related Items

Complexity of finite-variable fragments of propositional temporal and modal logics of computation, Fibred semantics for feature-based grammar logic, Tableaux and algorithms for Propositional Dynamic Logic with Converse, Complexity of the universal theory of modal algebras, The price of universality, Optionality, scope, and licensing: An application of partially ordered categories, EXPtime tableaux for ALC, Combining deduction and model checking into tableaux and algorithms for converse-PDL., On the expressivity of feature logics with negation, functional uncertainty, and sort equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An essay in combinatory dynamic logic
• Determinism and looping in combinatory PDL
• PDL with data constants
• Subsumption computed algebraically
• Propositional dynamic logic of regular programs
• Modal logic with names
• Deterministic propositional dynamic logic: finite models, complexity, and completeness
• Varieties of complex algebras
• The logic of unification in grammar
• The complexity of propositional linear temporal logics
• Feature-constraint logics for unification grammars
• Using the Universal Modality: Gains and Questions
• The Logic of Typed Feature Structures
• The Computational Complexity of Provability in Systems of Modal Propositional Logic