- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The complexity of modellability in finite and computable signatures of a constraint logic for head-driven phrase structure grammar
Journal of Logic, Language and Information 8 (1):83-110 (1999)
Abstract
The SRL of King is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG of Pollard and Sag. The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan in order to prove that – modellability in each computable signature is 1 0 – modellability in some finite signature is 1 0 -hard, and – modellability in some finite signature is decidableOther Versions
No versions found
My notes
Similar books and articles
Paul John King, kiril Ivanov Simov, and bjørn Aldag.Alexander Franz, Carson T. Schütze, Jaakko Hintikka & Ahti Pietarinen - 1999 - Journal of Logic, Language, and Information 8:487-489.
Polyadic dynamic logics for hpsg parsing.Anders Søgaard & Martin Lange - 2009 - Journal of Logic, Language and Information 18 (2):159-198.
Morph Moulder: Teaching Software for HPSG and Description Logics.Ekaterina Ovichinnikova & Frank Richter - 2007 - Logic Journal of the IGPL 15 (4):333-345.
Finite basis problems and results for quasivarieties.Miklós Maróti & Ralph Mckenzie - 2004 - Studia Logica 78 (1-2):293 - 320.
Logic in Finite Structures: Definability, Complexity, and Randomness.Scott Weinstein - 2002 - In Dale Jacquette (ed.), A Companion to Philosophical Logic. Malden, MA, USA: Wiley-Blackwell. pp. 332–348.
Index sets for some classes of structures.Ekaterina B. Fokina - 2009 - Annals of Pure and Applied Logic 157 (2-3):139-147.
Hybrid logics of separation axioms.Dmitry Sustretov - 2009 - Journal of Logic, Language and Information 18 (4):541-558.
Is a spectrum of a non-disintegrated flat strongly minimal model complete theory in a language with finite signature.Uri Andrews & Omer Mermelstein - 2021 - Journal of Symbolic Logic 86 (4):1632-1656.
A first-order axiomatization of the theory of finite trees.Rolf Backofen, James Rogers & K. Vijay-Shanker - 1995 - Journal of Logic, Language and Information 4 (1):5-39.
P versus np and computability theoretic constructions in complexity theory over algebraic structures.Gunther Mainhardt - 2004 - Journal of Symbolic Logic 69 (1):39-64.
Analytics
Added to PP
2009-01-28
Downloads
52 (#422,607)
6 months
8 (#613,944)
2009-01-28
Downloads
52 (#422,607)
6 months
8 (#613,944)
Historical graph of downloads
Citations of this work
Polyadic dynamic logics for hpsg parsing.Anders Søgaard & Martin Lange - 2009 - Journal of Logic, Language and Information 18 (2):159-198.
References found in this work
A modal perspective on the computational complexity of attribute value grammar.Patrick Blackburn & Edith Spaan - 1993 - Journal of Logic, Language and Information 2 (2):129-169.
The logic of unification in grammar.Robert T. Kasper & William C. Rounds - 1990 - Linguistics and Philosophy 13 (1):35 - 58.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-648784bb4d-82spv uwo