Computational structure of GPSG models

Linguistics and Philosophy 13 (5):521 - 587 (1990)
  Copy   BIBTEX

Abstract

The primary goal of this essay is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. To this end, generalized phrase structure grammar (GPSG) linguistic theory is revised so that its power more closely matches the limited ability of an ideal speaker-hearer: GPSG Recognition is EXP-POLY time hard, while Revised GPSG Recognition is NP-complete. A second goal is to provide a theoretical framework within which to better understand the wide range of existing GPSG models, embodied in formal definitions as well as in implemented computer programs.

Categories

Keywords

Reprint years

DOI

10.1007/bf00627292

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,394

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

"Grammarless" phrase structure grammar.James Rogers - 1997 - Linguistics and Philosophy 20 (6):721-746.
A computational representation for generalised phrase-structure grammars.John D. Phillips - 1992 - Linguistics and Philosophy 15 (3):255 - 287.
Syntactic codes and grammar refinement.M. Kracht - 1995 - Journal of Logic, Language and Information 4 (4):359-380.
A note on the use of lamda conversion in generalized phrase structure grammars.Elisabet Engdahl - 1980 - Linguistics and Philosophy 4 (4):505 - 515.
The View from Declarative Syntax 1.Peter Sells - 2021 - In Nicholas Allott, Terje Lohndal & Georges Rey (eds.), A Companion to Chomsky. Wiley. pp. 243–266.
Head-driven phrase structure grammar: linguistic approach, formal foundations, and computational realization.Robert D. Levine & W. Detmar Meurers - 2005 - In Keith Brown (ed.), Encyclopedia of Language and Linguistics. Elsevier.
On Phrase Structure building and labeling algorithms: towards a non-uniform theory of syntactic structures.Diego Gabriel Krivochen - 2015 - Linguistic Review 32 (3):515-572.
Dynamic Concept Spaces in Computational Creativity for Music.René Mogensen - 2017 - In Vincent C. Müller (ed.), Philosophy and theory of artificial intelligence 2017. Berlin: Springer.
Logical Aspects of Computational Linguistics (6th international conference, LACL2011, Montpellier, France, June/July 2011 Proceedings).Sylvain Pogodalla & Jean-Philippe Prost (eds.) - 2011 - Springer.
German Temporal Semantics: Three-dimensional Tense Logic and a Gpsg Fragment.John A. Nerbonne - 2018 - Routledge Library Editions: Semantics and Semiology.

Analytics

Added to PP
2009-01-28

Downloads
50 (#438,312)

6 months
12 (#299,634)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Constructions on holiday.Jeffrey Lidz & Alexander Williams - 2009 - Cognitive Linguistics 20 (1).

Add more citations

References found in this work

Aspects of the Theory of Syntax.Noam Chomsky - 1965 - Cambridge, MA, USA: MIT Press.
Knowledge of Language: Its Nature, Origin, and Use.Noam Chomsky - 1986 - Prager. Edited by Darragh Byrne & Max Kölbel.
Generalized Phrase Structure Grammar.G. Gazdar, E. Klein, G. Pullum & I. Sag - 1987 - Linguistics and Philosophy 10 (3):389-426.
Direct parsing of ID/LP grammars.Stuart M. Shieber - 1984 - Linguistics and Philosophy 7 (2):135 - 154.

Add more references