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 (...) decidable. (shrink)

This chapter focuses on the frameworks of Head‐Driven Phrase Structure Grammar (HPSG) as it developed from Generalized Phrase Structure Grammar (GPSG), and Lexical‐Functional Grammar (LFG). Declarative frameworks are not generative, as they do not ‘generate’ anything in the sense of the preceding paragraph. Pullum refers to that kind of approach as Generative‐Enumerative Syntax and differentiates it from Model‐Theoretic Syntax: GPSG, HPSG, and LFG essentially fall in the latter category. It describes some key (...) aspects of declarative frameworks, and the motivation for them. The chapter considers how declarative frameworks instantiate a view of Generative Grammar directly inspired by Noam Chomsky's early work, but without the procedural component. It presents some of the core design features which motivate declarative frameworks, and explores how syntactic phenomena are factorized and formalized in declarative frameworks, with a view to comparison with Minimalist Program analyses. (shrink)

The paper presents a system for construction classification representing multiple levels of specification, such as grammatical functions, grammatically reflected actants, and lexical semantics, aligned with a compositional system of sign combination mediating between a construction perspective and a valence perspective. The system uses a feature structure formalism based on Head-Driven Phrase Structure Grammar but with essential elements from Lexical Functional Grammar, and has as implementation background large scale HPSG grammars. While on the one extreme being (...) able to encode word level selection in multi-word patterns, the system on the other provides a compact format for construction specification, allowing for cross-language comparison both in construction and valence frame inventories. Pivotal in these capacities as well as in sign formalization in general are the grammatical functions. The paper motivates the usefulness of the various functionalities and illustrates the way in which they work together in a formally uniform system. (shrink)

Head-driven phrase structure grammar (HPSG) is one of the most prominent theories employed in deep parsing of natural language. Many linguistic theories are arguably best formalized in extensions of modal or dynamic logic (Keller, Feature logics, infinitary descriptions and grammar, 1993; Kracht, Linguistics Philos 18:401–458, 1995; Moss and Tiede, In: Blackburn, van Benthem, and Wolther (eds.) Handbook of modal logic, 2006), and HPSG seems to be no exception. Adequate extensions of dynamic logic have not been studied (...) in detail, however; the most important aspect is the reference to sets of substructures. In this paper, an adequate extension is identified, and some important results are established: Satisfiability is highly undecidable, and model checking is shown to be in EXPTIME and PSPACE-hard. A fragment with polynomial time model checking procedures is identified; it is shown to cover considerable fragments of HPSG. (shrink)

Building on the success of the bestselling first edition, the second edition of this textbook provides a comprehensive and accessible introduction to the major issues in Principles and Parameters syntactic theory, including phrase structure, the lexicon, case theory, movement, and locality conditions. Includes new and extended problem sets in every chapter, all of which have been annotated for level and skill type. Features three new chapters on advanced topics including vP shells, object shells, control, gapping and ellipsis and (...) an additional chapter on advanced topics in binding. Offers a brief survey of both Lexical-Functional Grammar and Head-Driven Phrase Structure Grammar. Succeeds in strengthening the reader's foundational knowledge, and prepares them for more advanced study. Supported by an instructor's manual and online resources for students and instructors, available at www.blackwellpublishing.com/carnie. (shrink)

I will explore possibilities for formulating linguistic semantics in terms of records and record types of the kind used in recent developments of Martin-L¨of type theory (Betarte, 1998, Betarte and Tasistro, 1998, Coquand, Pollock and Takeyama, 2003, Tasistro, 1997). I will suggest that they give us the tools to develop a theory which includes aspects of Montague semantics, using the lambda calculus1, Discourse Representation Theory (DRT)2, situation semantics3 and Head-Driven Phrase Structure Grammar (HPSG)4 in a single theory. (...) I will also argue that formulating these theories in terms of record types may provide us not only with a unified approach but also with certain improvements over the individual theories. (shrink)

An examination of the evidence for and the theoretical implications of a universal word order constraint, with data from a wide range of languages. This book presents evidence for a universal word order constraint, the Final-over-Final Condition (FOFC), and discusses the theoretical implications of this phenomenon. FOFC is a syntactic condition that disallows structures where a head-initial phrase is contained in a head-final phrase in the same extended projection/domain. The authors argue that FOFC is a linguistic universal, not (...) just a strong tendency, and not a constraint on processing. They discuss the effects of the universal in various domains, including the noun phrase, the adjective phrase, the verb phrase, and the clause. The book draws on data from a wide range of languages, including Hindi, Turkish, Basque, Finnish, Afrikaans, German, Hungarian, French, English, Italian, Romanian, Arabic, Hebrew, Mandarin, Pontic Greek, Bagirmi, Dholuo, and Thai. FOFC, the authors argue, is important because it is the only known example of a word order asymmetry pertaining to the order of heads. As such, it has significant repercussions for theories connecting the narrow syntax to linear order. (shrink)

This paper addresses a phenomenon in which certain word-parts can be omitted. The evidence shows that the full range of data cannot be captured by a sublexical analysis, since the phenomena can be observed both in phrasal and in lexical environments. It is argued that a form of deletion is involved, and that the phenomena—lexical or otherwise—are subject to the same phonological, semantic, and syntactic constraints. In the formalization that is proposed, all of the above constraints are cast in a (...) parallel and declarative fashion, in the framework of Head-Driven Phrase Structure Grammar (Pollard and Sag Head-driven phrase structure grammar, 1994), since the various levels of linguistic description are locally and simultaneously available. Building on recent accounts of ellipsis, this paper proposes a unified and general account of word-part ellipsis and phrasal ellipsis. (shrink)

The paper investigates an elliptical construction, Clarification Ellipsis, that occurs in dialogue. We suggest that this provides data that demonstrates that updates resulting from utterances cannot be defined in purely semantic terms, contrary to the prevailing assumptions of existing approaches to dynamic semantics. We offer a computationally oriented analysis of the resolution of ellipsis in certain cases of dialogue clarification. We show that this goes beyond standard techniques used in anaphora and ellipsis resolution and requires operations on highly structured, linguistically (...) heterogeneous representations. We characterize these operations and the representations on which they operate. We offer an analysis couched in a version of Head-Driven Phrase Structure Grammar combined with a theory of information states (IS) in dialogue. We sketch an algorithm for the process of utterance integration in IS which leads to grounding or clarification. The account proposed here has direct applications to the theory of attitude reports, an issue which is explored briefly in the concluding remarks of the paper. (shrink)

We offer a computational analysis of the resolution of ellipsis in certain cases of dialogue clarification. We show that this goes beyond standard techniques used in anaphora and ellipsis resolution and requires operations on highly structured, linguistically heterogeneous representations. We characterize these operations and the representations on which they operate. We offer an analysis couched in a version of Head-Driven Phrase Structure Grammar combined with a theory of information states (IS).

We show that Kubota and Levine’s characterization of the HPSG-based theory of non-constituent coordination proposed in Yatabe Proceedings of the 7th International Conference on Head-Driven Phrase Structure Grammar, CSLI, Stanford, pp 325–344, 2001) and later works is inaccurate, and that the theory in question does not require any ad hoc mechanisms to account for the long-known fact that right-node raising and left-node raising can affect semantic interpretation. In the course of demonstrating this, we fill in some details (...) of this HPSG-based theory that were left unspecified in the previous literature, and we also present novel accounts of split-antecedent relative clauses and of respectively interpretation that are consistent with the theory. Furthermore, we argue that the phenomenon of summative agreement may provide a reason to prefer this theory over CG-based theories like Kubota and Levine’s. (shrink)

I argue that the ability to compute phrase structure grammars is indicative of a particular kind of thought. This type of thought that is only available to cognitive systems that have access to the computations that allow the generation and interpretation of the structural descriptions of phrase structure grammars. The study of phrase structure grammars, and formal language theory in general, is thus indispensable to studies of human cognition, for it makes explicit both the (...) unique type of human thought and the underlying mechanisms in virtue of which this thought is made possible. (shrink)

We sketch an axiomatic reformalization of Generalized Phrase StructureGrammar (GPSG) – a definition purely within the language ofmathematical logic of the theory GPSG embodies. While this treatment raisesa number of theoretical issues for GPSG, our focus is not thereformalization itself but rather the method we employ. The model-theoreticapproach it exemplifies can be seen as a natural step in the evolution ofconstraint-based theories from their grammar-based antecedents. One goal ofthis paper is to introduce this approach to a broader audience (...) and todemonstrate its application to an existing theory. As such, it joins agrowing literature of similar studies. Prior studies, however, have had anumber of weaknesses – they generally offer little in the way ofconcrete examples of the advantages the approach has to offer, theytypically ignore significant portions of the theories they address, and, byfully abstracting away from the notion of grammar mechanism, they largelyabandon the possibility of establishing meaningful complexity results. Thesecond goal of the paper is to address these issues. Our thrust is to sketchthe reformalization sufficiently to illustrate the way in which it capturesFeature Specification Defaults (FSDs) and the Exhaustive Constant PartialOrdering (ECPO) property. Our definition of FSDs is considerably simplifiedrelative to the original formalization and is free of the procedural flavorthat has led some to assume that FSDs are inherently dynamic. Our treatmentof ECPO uncovers a gap in its definition in the context of partialcategories that has heretofore gone unnoticed. We offer these as ademonstration of the kind of insight that a model-theoretic reinterpretationcan bring to an existing theory. Further, since these are the types ofproperties that prior studies in this genre have failed to address, FSDs andECPO provide a means for us to explore the limitations of these approachesand to offer ways of overcoming them. Finally, the logical framework weemploy has a well defined generative capacity – definability in thisframework characterizes strong context-freeness in a particular sense. Thus,despite being more abstract than its constraint-based predecessors, themodel-theoretic approach, as exemplified here, can offer stronger complexityresults than are typically available in the constraint-based framework. (shrink)

In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars (SPGs) defined by Chomsky are equivalent in a certain sense to Bar-Hillel's bidirectional categorial grammars (BCGs). On the other hand, Cohen [3] proves the equivalence of the latter ones to what the calls free categorial grammars (FCGs). They are closely related to Lambek's syntactic calculus which, in turn, is based on the idea due to Ajdukiewicz [1]. For the reasons which will be discussed in the (...) last section, Cohen's proof seems to be at least incomplete. This paper yields a direct proof of the equivalence ofFCGs andSPGs. (shrink)

In this paper, we shall present a generalization of phrase structure grammar, in which all functional categories have type restrictions, that is, their argument types are specific domains. In ordinary phrase structure grammar, there is just one universal domain of individuals. The grammar does not make a distinction between verbs and adjectives in terms of domains of applicability. Consequently, it fails to distinguish between sentences like every line intersects every line, which is well (...) typed, and every line intersects every point, which is ill typed.Our generalization relates to ordinary phrase structure grammar in the same way as the higherlevel constructive type theory of Martin-Löf relates to the simple type theory of Church . Simple type theory has been used in linguistics and related with phrase structure grammar, especially in the tradition based on the work of Montague .Our definition of the grammar will be more formal than Montague's in the sense that we shall use a formal metalanguage, that of constructive type theory, for defining both the object language and its interpretation. The grammar, both syntax and semantics, is thus readily implementable in the type-theoretical proof system ALF . Inside type theory, a distinction can be made between the object language and the model, in other words, between syntactic and semantic types. It will turn out that the object language cannot be defined independently of the model, as in ordinary Tarski semantics. This is a direct consequence of introducing the typing restrictions.The grammar presented here can be seen as a formal linguistic elaboration of the work presented in Ranta 1991 and 1994. The organization of generative grammar as categorial grammar followed by sugaring should now look more familiar to the linguist, as the grammatical formalism on which sugaring operates is no longer full type theory but a set of phrase structure trees. (shrink)

In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars dened by Chomsky are equivalent in a cer- tain sense to Bar-Hillel's bidirectional categorial grammars . On the other hand, Cohen [3] proves the equivalence of the latter ones to what he calls free categorial grammars . They are closely related to Lambek's syntactic calculus which is, in turn, based on the idea due to Ajdukiewicz [1]. For some reasons, Cohen's proof seems to be at (...) least in- complete. Here, I give a short outline of the direct proof of the equivalence between SF G's and F CG's. (shrink)

Some modifications are suggested to recent (1985) generalised phrase-structure grammar which make the formalism more suitable to computational use, and at the same time provide a clear and elegant redefinition for parts of the formalism which are standardly complex and ill-defined. It is shown how the feature-instantiation principles can be represented as explicit rules in a format similar to metarules, and how a grammar of four parts, immediate-dominance rules, linear-precedence rules, metarules, and these new propagation rules, (...) can be used to produce the ordinary GPSG analyses of English. Methods of computational implementation are discussed, in particular it is suggested that the parts of the grammar are most conveniently interpreted as instructions as to how to produce a set of context-free phrase-structure rules which can be used with a simple left-corner parser. (shrink)

The restrictive grammatical format suggested in GPSG provides an extremely interesting alternative to transformational approaches to grammar. However, we have seen that the way the grammar is currently organized, it will in certain cases fail to give the correct interpretation to sentences with displaced constituents. Whenever a left or rightward displaced constituent contains an element that can stand in an anaphoric relation with some other element in the sentence, i.e. contains a quantifier or a pronoun, the semantic rules (...) as given do not provide the intended reading. It should be made clear, however, that this shortcoming pertains to one particular type of GPSG, namely one whose interpretation procedures make use of lambda abstraction. The problematic cases addressed here do not by themselves invalidate the syntactic framework of a GPSG. It seems quite plausible that one could construct a semantics that does not depend on lambda conversion, in which case the problem addressed in this note is presumably no longer relevant. One such proposal is put forward in Cooper (forthcoming) where a non-movement syntax is combined with interpretation procedures that do not involve translation into a lambda calculus. (shrink)

Unsupervised grammar induction systems commonly judge potential constituents on the basis of their effects on the likelihood of the data. Linguistic justifications of constituency, on the other hand, rely on notions such as substitutability and varying external contexts. We describe two systems for distributional grammar induction which operate on such principles, using part-of-speech tags as the contextual features. The advantages and disadvantages of these systems are examined, including precision/recall trade-offs, error analysis, and extensibility.

In Pollard and Sag (1987) and Pollard and Sag (1994:Ch. 1–8), the subcategorized arguments of a head are stored on a single ordered list, the subcat list. However, Borsley (1989) argues that there are various defi- ciencies in this approach, and suggests that the unified list should be split into separate lists for subjects, complements, and specifiers. This proposal has been widely adopted in what is colloquially known as HPSG3 (Pollard and Sag (1994:Ch. 9) and other recent work in HPSG). (...) Such a move provides in HPSG an analog of the external/internal argument distinction generally adopted in GB, solves certain technical problems such as allowing prepositions to take complements rather than things identical in subcat list position to subjects, and allows recognition of the special features of subjects which have been noted in the LFG literature, where keyword grammatical relations are used. In HPSG3, it is these valence features subj, comps and spr whose values are ‘cancelled off’ (in a Categorial Grammar-like manner) as a head projects a phrase. A lexical head combines with its complements and subject or specifier (if any) according to the lexically inherited specification, as in (1). (shrink)

We argue that an adequate treatment of verb phrase anaphora must depart in two major respects from the standard approaches. First of all, VP anaphors cannot be resolved by simply identifying the anaphoric VP with an antecedent VP. The resolution process must establish a syntactic/semantic parallelism between larger units that the VPs occur in. Secondly, discourse structure has a significant influence on the reference possibilities of VPA. This influence must be accounted for. We propose a treatment which meets (...) these requirements. It builds on a discourse grammar which characterizes discourse cohesion by means of a syntactic/semantic matching procedure which recognizes parallel structures in discourse. It turns out that this independently motivated procedure yields the resolution of VPA as a side effect. (shrink)

For the most part, the papers collected in this volume stern from presentations given at a conference held in Tucson over the weekend of May 31 through June 2, 1985. We wish to record our gratitude to the participants in that conference, as well as to the National Science Foundation and the University of Arizona SBS Research Institute for their financial support. The advice we received from Susan Steele on organizational matters proved invaluable and had many felicitous consequences for the (...) success of the con­ ference. We also would like to thank the staff of the Departments of Linguistics of the University of Arizona and the University of Massachusetts at Amherst for their help, as weIl as a number of individuals, including Lin Hall, Kathy Todd, and Jiazhen Hu, Sandra Fulmer, Maria Sandoval, Natsuko Tsujimura, Stuart Davis, Mark Lewis, Robin Schafer, Shi Zhang, Olivia Oehrle-Steele, and Paul Saka. Finally, we would like to express our gratitude to Martin Scrivener, our editor, for his patience and his encouragement. Vll INTRODUCTION The term 'categorial grammar' was introduced by Bar-Rillel as a handy way of grouping together some of his own earlier work and the work of the Polish logicians and philosophers Lesniewski and Ajdukiewicz, in contrast to approaches to linguistic analysis based on phrase structure grammars. (shrink)

We argue that an adequate treatment of verb phrase anaphora must depart in two major respects from the standard approaches. First of all, VP anaphors cannot be resolved by simply identifying the anaphoric VP with an antecedent VP. The resolution process must establish a syntactic/semantic parallelism between larger units that the VPs occur in. Secondly, discourse structure has a significant influence on the reference possibilities of VPA. This influence must be accounted for.We propose a treatment which meets these (...) requirements. It builds on a discourse grammar which characterizes discourse cohesion by means of a syntactic/semantic matching procedure which recognizes parallel structures in discourse. It turns out that this independently motivated procedure yields the resolution of VPA as a side effect. (shrink)

A comparison of African grammars written in French, and bilingual Franco-African or Franco-Caribbean dictionaries, allows us to discern a common myth concerning “family” ties between French and African Languages.Missionaries consider two means of conversion: by the introduction of the God-Word to his children, which predetermines the foreign society to be encountered; the other demands an ethno- graphic study (to discover the meaning of language) in oral societies (African, Caribbean) to whom an alphabetical language is superimposed (with Latin characters). This effort (...) of transcription presupposes the harmonious compatibility of all oral languages with French. Thus the missionaries breathe the Word and transcendence into the colonies in order to recover in “Word incarnate”, instrument and symbol for the conversion process. (The theologian would speak here of the “verticality of transcendence”.) But the missionary enterprise meets with the resistances of written language and of foreign societies endowed with complex structures and syntaxes. Thus, the so-called “verticality” crumbles along with missionary hopes, resulting in a trite approximate translation which could be characterized as “horizontal”. (shrink)