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)

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)

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 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)

[1]. Recently renewed interest in non transformational approaches to syntax [2] suggests that it might be well to take another look at categorial grammars, since they seem to have been neglected largely because they had been shown to be equivalent to context free phrase structure grammars in weak generative capacity and it was believed that such grammars were incapable of describing natural languages in a natural way. It is my purpose here to sketch a theory of grammar (...) which represents a generalization of categorial grammars of the sort invented by Ajdukiewicz (1935) and further elaborated especially by Bar Hillel (1953) and Lambek (1961). (shrink)

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)

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)

I should like to express my gratitude to my supervisor, Professor H. Schultink, whose criticisms and careful reading helped me to improve considerably upon the clarity of exposition while I wrote this study, and whose seemingly innocent requests to elaborate confronted me time and again with the need of revising or abandoning ideas I thought stood on firm ground. His support, and Dr. M. C. van den Toom's gratefully acknowl edged willingness to read and evaluate the manuscript enabled me to (...) present this work as a thesis in the University of Utrecht. In more than one way, lowe a debt to Albert Kraak, Professor of Linguistics in the University of Nijmegen. His inspiring enthusiasm awakened my interest in linguistics when I was a student of his. He in troduced me to transformational grammar at a time when it seemed almost improper to talk about it, and the stimulating experience of writing a book on Dutch syntax together with him taught me invaluable lessons. I should also like to thank my friend and colleague Henk Verkuyl, to gether with whom I prepared an article on the subject of measuring duration in Dutch. Without our stimulating discussions on the subject, the fourth chapter of this study could never have been written in the present form. I am also indebted to him for criticisms and helpful suggestions. At an early stage I profited greatly from discussions with Pieter A. M. (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)

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

A recent hypothesis in empirical brain research on language is that the fundamental difference between animal and human communication systems is captured by the distinction between finite-state and more complex phrase-structure grammars, such as context-free and context-sensitive grammars. However, the relevance of this distinction for the study of language as a neurobiological system has been questioned and it has been suggested that a more relevant and partly analogous distinction is that between non-adjacent and adjacent dependencies. Online memory resources (...) are central to the processing of non-adjacent dependencies as information has to be maintained across intervening material. One proposal is that an external memory device in the form of a limited push-down stack is used to process non-adjacent dependencies. We tested this hypothesis in an artificial grammar learning paradigm where subjects acquired non-adjacent dependencies implicitly. Generally, we found no qualitative differences between the acquisition of non-adjacent dependencies and adjacent dependencies. This suggests that although the acquisition of non-adjacent dependencies requires more exposure to the acquisition material, it utilizes the same mechanisms used for acquiring adjacent dependencies. We challenge the push-down stack model further by testing its processing predictions for nested and crossed multiple non-adjacent dependencies. The push-down stack model is partly supported by the results, and we suggest that stack-like properties are some among many natural properties characterizing the underlying neurophysiological mechanisms that implement the online memory resources used in language and structured sequence processing. (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)

An approach to argument macrostructure -- The dialectical nature of argument -- Toulmin's problematic notion of warrant -- The linked-convergent distinction, a first approximation -- Argument structure and disciplinary perspective : the linked-convergent versus multiple-co-ordinatively compound distinctions -- The linked-convergent distinction, refining the criterion -- Argument structure and enthymemes -- From analysis to evaluation.

Since a human language consists of an infinite number of sentences, it cannot be adequately described by enumeration. Hence, as Chomsky wrote in the first paragraph of his first book, Syntactic Structures, an adequate description of a language is approached through the specification of a generative device that will generate and structurally describe all the sentences of a language. And since generative devices form a hierarchy in terms of descriptive power, the basic question of grammar is what is the (...) minimum of power needed to generate human languages. What this book does is describe the Chomsky hierarchy in a very clear and accessible way. Finite state grammars are shown to be equivalent in generative power to regular phrase structure grammars. After context free, and context sensitive phrase structure grammars, one finds at the top of the hierarchy transformational grammars, which Kimball has shown to be weakly equivalent to a universal phrase structure grammar, i.e., one in which rules can delete items. This last equivalence allows one to appreciate the central problem in current grammatical theory: that the "standard theory" of Aspects of the Theory of Syntax allows so much power for the construction of grammars that solutions become arbitrary and non-empirical, and hence the problem is to find a principled minimization of the power of transformational grammars. This is a clear, up-to-date, and elegant little book. One admirably suitable as a comparatively undemanding introduction to the abstract theory of grammar, or as a way of brushing-up on the subject.—J.L. (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.

Recent developments in the semantics of natural language seem to lead to a genuine synthesis of ideas from linguistics and logic, producing novel concepts and questions of interest to both parent disciplines. This book is a collection of essays on such new topics, which have arisen over the past few years. Taking a broad view, developments in formal semantics over the past decade can be seen as follows. At the beginning stands Montague's pioneering work, showing how a rigorous semantics can (...) be given for complete fragments of natural language by creating a suitable fit between syntactic categories and semantic types. This very enterprise already dispelled entrenched prejudices concerning the separation of linguistics and logic. Having seen the light, however, there is no reason at all to stick to the letter of Montague's proposals, which are often debatable. Subsequently, then, many improvements have been made upon virtually every aspect of the enterprise. More sophisticated grammars have been inserted (lately, lexical-functional grammar and generalized phrase structure grammar), more sensitive model structures have been developed (lately, 'partial' rather than 'total' in their com position), and even the mechanism of interpretation itself may be fine-tuned more delicately, using various forms of 'representations' mediating between linguistic items and semantic reality. In addition to all these refinements of the semantic format, descriptive coverage has extended considerably. (shrink)

Research in linguistic semantics may be roughly divided into two broad traditions. Students concerned with lexical fields and lexical domains ('lexical semanticists') have interested themselves in the paradigmatic relations of contrast that obtain among related lexical items and the substantive detail of how particular lexical items map to the nonlinguistic objects they stand for. 'Formal semanticists' (those who study the combinatorial properties of word meanings) have been mostly unconcerned with these issues, concentrating rather on how the meanings of individual words, (...) whatever their internal structure may be and however they may be paradigmatically related to one another, combine into the meanings of phrases and sentences (and recently, to some extent, texts). (shrink)

Basic syntactic analysis refers to sentence-level syntactic analysis. In the process of developing the Mat Link English–Chinese machine translation system, the Generalized Maximum Likelihood Ratio algorithm was improved, and a basic English syntax analyzer for English–Chinese translation was designed and implemented. The analyzer approves the structure of the analysis table with a variety of export products, introduces the character mapping function to realize the automatic recognition of the sentence boundary, uses the children of the same level to describe (...) the grammatical structure of the sentence, and realizes the proverb from the original sentence to the target sentence stage conversion. Finally, through the analysis of example sentences, the design concept and working process of the basic grammar are explained. (shrink)

The tradition of Lughz and muʿammā in Arab poetry has an important place. Ibn al-Fāriḍ (d. 632/1235) is a divine love poet that lived in the Ayyubids period. He is an important point in the process of change and transformation of Arabic poetry language. This research aims to carry out a theoretical and anecdotal examination of the Lughzes in Ibn al-Fāriḍ’s Dīwān. The work explains, firstly, the concept of Lughz in terms of conceptual content and theoretical structure and summarizes (...) its own method to be applied in solving and evaluating Lughzes in ten articles. The paper indicates whether the Lughzes in Dīwānhave a theoretical structure or not. In this context, it distinguishes the Lughzes from the number of layers, simple and compound structure maintenance. It examines the theoretical and functional contributions of the tahsīl, takmīl, tashīland tazyīlmethods, the stages of the establishment and the solution of the Lughzes.Abstract: Abū Hafs Sharafuddīn Omar b. Ali al-Hamavī al-Mısrī (d. 632/1235) known as the king of lovers, and called Ibn al-Fārid, is a divine love poet that lived in Egypt during the Ayyubids period (1171-1462). He is an important figure in the process of change and transformation of poetry language in Arabic literature. The lughz and muʿammā (enigma, enigmetic speech, allusion, inversion riddle, poetry puzzle, synecdoche and metaphoric language) means a word pointing to a name or something by symbol and sign. Numerous books have been written about lughzes. These include Arabic poetry, Persian poetry, Classical Turkish poetry, Arabic grammar, Islamic law, hadith, mathematics and inheritance law. The lughz and muʿammā have some linguistic features related to phonetics, statistical linguistics, morphology, lexicology, grammar, syntax, semantics and prosody. This tradition has an important place in Arabic poetry. The research aims to carry out a theoretical and anecdotal examination of the lughzes and muʿammās in Ibn al-Fārız’s Dīwān. The paper explains, firstly, the concept of lughz in terms of conceptual content and theoretical structure. The article summarizes its own method to be applied in analyzing and evaluating lughzes within ten items. The research examines the series of lughzes in Dīwānand divides them into parts according to the original question in the riddles. This work examines the secondary lughzes given in the details of poems in solution parts. The paper indicates whether the lughzes in Dīwānhave a theoretical structure or not. In this context, the research examines lughzes in terms of language and structure, especially in terms of the processes of establishment and solution. This paper categorizes the lughzes according to the number of layers and to whether they have a simple or compound structure. This paper examines the theoretical and functional contributions of the amal al-tahsīlī, amal al-takmīlī, amal al-tashīlī and amal al-tazyīlī methods in the stages of the establishment and the solution of the lughzes. The work applies the theoretical perspectives of these methods to each lughz. The research also examines the contribution of these four methods to the lughzes.There are many lughzes in Ibn al-Fārid’s poems. In Ibn al-Fārid’s Dīwān, in general, fifty-four things are asked. Fifty-one of them are words. Three of them are verbs. One of the verbs is in the order structure and two in the past tense. His lughzes have a theoretical and methodical structure. In terms of organizational structure, lughzes are generally multi-layered, intricate, compound and integrated. Composite lughzes are multi-layered, simple poems are single-layered. Approximately twenty words are asked in the lughzes. These words are always in the first layer of lughz, whether simple or compound. Thirty-seven words in the lughz are secondary lughz with an auxiliary and complementary nature. They are located between the second and sixth layers. Seventeen of the lughzes asked in the auxiliary nature are located in the second layer, thirteen in the third layer, five in the fourth layer, one in the fifth layer and one in the sixth layer. One of the lughzes is six-layered, one of them are five-layered, four of them are four-layered, eight are three-layered, four are double-layered and three are single-layered. According to this, the majority of lughzes in Ibn al-Fārid’s poems are in the unified form and multilayered.The lughzes are formed in terms of word, composition, phrase, grammar and meaning levels. The lughzes have both lexical and semantic characteristics. Ibn al-Fārid uses the configuration (amal al-tahsīlī), completion (amal al-takmīlī), facilitation (amal al-tashīlī) and addition (amal al-tazyīlī) methods to design the lughzes. The structure in the lughzes is shaped by these methods. The words in his lughzes constitute eleven categories, consisting of names, acts and noun verbs. The answers of the questions asked in the poems consist in general of prophet names, surah names, tribal names, administrator’s surnames, letters, cities, animals, food and drink names, attributes and actions. Verbs are in the past time or order form. Some of the lughzes in Ibn al-Fārid’s poems are built in an extraordinary style beyond being interesting. Not all the sentences used in couplets are part of the lughzes. These elements are mentioned in order to complete the lughzes in terms of rhythm and meaning. To be able to solve the lughzes of Ibn al-Fārid, one must be knowledgeable about the language and narrative features of Arabic and Islamic culture, as well as subjects such as the Quran, Sufism, abjad calculation, mathematics, geometry, geography, biology, botany and zoology. His poems contributes to the development and transformation of Arabic poetry. (shrink)

We argue in this article that many common adverbial phrases generally taken to signal a discourse relation between syntactically connected units within discourse structure instead work anaphor- ically to contribute relational meaning, with only indirect dependence on discourse structure. This allows a simpler discourse structure to provide scaffolding for compositional semantics and reveals multiple ways in which the relational meaning conveyed by adverbial connectives can interact with that associated with discourse structure. We conclude by sketching out (...) a lexicalized grammar for discourse that facilitates discourse interpretation as a product of compositional rules, anaphor resolution, and inference. (shrink)