Search

Ambiguity plays an important role in checking the relevances of formalism for natural language processing. As contextual grammars were shown to be an appropriate description for natural languages, analyzing syntactic ambiguity of contextual grammars deserves a special attention. The levels of ambiguity of internal contextual grammars are defined depending on the information used for describing a derivation. In this paper, we continue the study on ambiguity of internal contextual grammars which was investigated in [3] and [13]. We achieve solutions to the following open problems addressed in the above papers. For each (i,j) ∈{(2,1),(1,0),(0,1)}, are there languages which are inherently i-ambiguous with respect to grammars with arbitrary selector, but j-ambiguous with respect to grammars with finite selector?

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.

The scope of an expression is the domain within which its interpretation can impact that of others. This domain often coincides with the expression's sister constituent in syntax, but research in the past two decades has uncovered many cases where it does not. The latter cases may require semantic innovations. It turns out that different operators have different scoping and binding abilities. At least three classes emerge: unmodified indefinites, distributive universals, and counting quantifiers. Existential scope and distributive scope are distinguished, and E-type anaphora and covariance with situations are added to traditional bound variable and coreferential readings.

The serious study of descriptions begins with the theories of Bertrand Russell, who held that definite and indefinite descriptions are both devices of quantification. The present article begins by providing the historical background to Russell's mature theory of descriptions, a detailed overview of the theory, and a brief account of contemporary implementations of Russell's views. Criticisms of Russell's approach are then considered, as are alternative approaches. In particular, singular term theories of definite descriptions and ambiguity theories of both definite and indefinite descriptions are described, as are recent nonquantificational approaches to indefinites.

The article starts with Aristotle's definition of the subject as a major characteristic of the notion ‘clause.’ It considers the parallel between logic before Frege and grammar before Chomsky's 1981 Extended Projection Principle (EPP). The EPP defines subject as a canonical underlying configuration. This fits into a configurational view of grammar. Alternatively, the subject may be defined as selection from a hierarchy of theta roles. This relates to the same diversity of constructions by means of interpretative rules. The article further discusses simple and more complex cases, such as infinitival complements and predicative adjuncts and it mentions the respective problems. The theta-hierarchy does not fit with nonreferential (dummy) subjects and the EPP does not fit with nonconfigurational languages. The typology of grammar suggests that some type of subjecthood is present in most languages, but certain languages identify subject marking with systematic topic marking. Arguably, a subset of topic-oriented languages functions without a notion ‘subject.’

In the normal course of events, children manifest linguistic competence equivalent to that of local adults in just a few years. Children can produce and understand novel sentences, they can judge that certain strings of words are true or false, and so on. Yet experience appears to dramatically underdetermine the competence children so rapidly achieve, even given optimistic assumptions about children’s nonlinguistic capacities to extract information and form generalizations on the basis of statistical regularities in the data they receive. These considerations underlie various (more specific) poverty-of-stimulus arguments for the innate specification of linguistic principles. But in our view, certain features of nativist arguments have not yet been fully appreciated. We focus here on three (related) kinds of poverty-of-stimulus argument, each of which has been supported by the findings of psycholinguistic investigations of child language.

Cognitive processes are often attributed to statistical or symbolic general-purpose mechanisms. Here we show that some spontaneous generalizations are driven by specialized, highly constrained symbolic operations. We explore how two types of artificial grammars are acquired, one based on repetitions and the other on characteristic relations between tones ("ordinal" grammars). Whereas participants readily acquire repetition-based grammars, displaying early electrophysiological responses to grammar violations, they perform poorly with ordinal grammars, displaying no such electrophysiological responses. This outcome is problematic for both general symbolic and statistical models, which predict that both types of grammars should be processed equally easily. This suggests that some simple grammars are acquired using perceptual primitives rather than general-purpose mechanisms; such primitives may be elements of a "toolbox" of specialized computational heuristics, which may ultimately allow constructing a psychological theory of symbol manipulation.

We link generative dependency grammars meeting natural modularity requirements with underspecified semantics of Discourse Plans intended to account for exactly those meaning components that grammars of languages mark for. We complete this link with a natural compilation of the modular dependency grammars into strongly equivalent efficiently analysed categorial dependency grammars.

In this paper, we define Dependency Structure Grammars (DSG), which are rewriting rule grammars generating sentences together with their dependency structures, are more expressive than CF-grammars and non-equivalent to mildly context-sensitive grammars. We show that DSG are weakly equivalent to Categorial Dependency Grammars (CDG) recently introduced in [6,3]. In particular, these dependency grammars naturally express long distance dependencies and enjoy good mathematical properties.

The capacity to generate a limitless range of meaningful expressions from a finite set of elements differentiates human language from other animal communication systems. Rule systems capable of generating an infinite set of outputs (“grammars”) vary in generative power. The weakest possess only local organizational principles, with regularities limited to neighboring units. We used a familiarization/discrimination paradigm to demonstrate that monkeys can spontaneously master such grammars. However, human language entails more sophisticated grammars, incorporating hierarchical structure. Monkeys tested with the same methods, syllables, and sequence lengths were unable to master a grammar at this higher, “phrase structure grammar” level.

The recent results of the research into construction of syntactic pattern recognition-based expert systems are presented. The model of syntactic pattern recognition has been defined with the use of GDPLL(k) grammars and parsers, and the model has been successfully applied as an efficient tool for inference support in several expert systems. Nevertheless, one of the main problems of practical application of GDPLL(k) grammars consists in difficulties in defining the grammar from the sample of a pattern language. In the paper we present the first achievement in the field of grammatical inferencing of GDPLL(k) grammars: an algorithm of automatic construction of a GDPLL(k) grammar from a so-called polynomial specification of the language.

Relation grammars (RGs) are introduced as a possible general framework for specifying the syntax of visual languages and, more generally, of multi-dimensional languages. A formal definition of relation grammars is given. Two examples of applications on graphs are shown. RG formalism is compared to conventional context-free grammars. RGs are used to describe the syntax of horizontal lines and statechart graphs using picture processing grammars and picture layout grammars, respectively. >

Unrestricted text analysis requires an accurate syntactic analysis but structural ambiguity is one of the most difficult problems to resolve. Researchers have tried different approaches to obtain the correct syntactic structure from analyzed sentences but no successful results have been obtained. Two different approaches have traditionally applied to syntactic analysis: constituent grammars and dependency grammars. We propose a model for syntactic analysis and disambiguation combining lexical dependencies and semantic proximity. Lexical dependencies are applied by means of a government pattern dictionary following the dependency approach. The semantic proximity is introduced by means of semantic closeness among constituents. Examples are given to illustrate the method's contributions.

In this article we present data from two sets of experiments designed to investigate how children and adult speakers of English and Kannada (Dravidian) interpret scopally ambiguous sentences containing numerally quantified noun phrases and negation (e.g. Donald didn't find two guys). We use this kind of sentence as a way to find evidence in children's linguistic representations for the hierarchical structure and the abstract relations defined over these structures (in particular, the relation of c-command) that linguists take to be at the core of grammatical knowledge. Specifically, we uncover the existence of systematic differences in the way that children and adult speakers resolve these ambiguities, independent of the language they speak. That is, while adults can easily access either scope interpretation, 4-year-old children display a strong preference for the scopal interpretation of the quantified elements which corresponds to their surface syntactic position. Crucially, however, we show that children's interpretations are constrained by the surface hierarchical relations (i.e. the c-command relations) between these elements and not by their linear order. Children's non-adult interpretations are therefore informative about the nature of the syntactic representations they entertain and the rules they use to determine the meaning of a sentence from its structure.

One important function of syntactic analysis of speech is the assignment of thematic roles to noun phrases. Thematic roles of noun-phrases in canonical sentences are assigned in “default” orderings (e.g. Agent Object Recipient in English for the canonical sentence “John gave the ball to Mary.”). This ordering is transformed in non-canonical sentences (e.g. “The ball was given to Mary by John.”), whose thematic role assignment is guided, in part, by function items (e.g. prepositions “to” and “by”). Agrammatic patients are impaired in the syntactic comprehension of non-canonical sentences. It is not clear whether this is due to a failure to process function items, a failure to assign thematic roles, or both. We have recently studied artificial grammar learning in a recurrent network model in which serial surface structure, and abstract transformational rules are represented by separate systems. We now examine the behavior of this dual system model in syntactic comprehension of canonical and non-canonical sentences. Function items are represented by the “surface” system and guide the application of transformational rules that are represented by the “abstract” system. After learning the structural regularities of the target language, the model predicts that failure in either of these systems, i.e. in the representation of function items or in the representation of syntactic knowledge will impair syntactic comprehension. The model also predicts that the expression of these impairments should not be restricted to performance with natural grammars but should also be manifest in artificial grammar conditions. With respect to this second prediction, we have recently confirmed that agrammatic patients indeed fail to process non-canonically ordered sentences both in natural and artificial grammars. In the artificial grammar sequences, this failure is purely related to application of the transformation, as no function items are involved in the task. The relevance of these results to current linguistic theory will be discussed.

It has long been assumed in linguistics that bound variable interpretations of pronouns are possible (only) when a quantified expression c-commands the pronoun. In two studies in which readers’ eye movements were recorded, we examined the processing of pronouns bound by universal quantifiers. Experiment 1 compared examples where the quantifier c-commands the pronoun (‘Every British soldier thought he killed an enemy soldier’) with examples where it doesn’t (‘Every British soldier aimed and then he killed an enemy soldier’). Although there were no first pass differences, re-reading time showed that both quantifier examples took longer to read than nonquantified controls (‘The old British soldier. . . ’), but there was no special penalty in examples when the quantifier failed to c-command the pronoun. Experiment 2 investigated intersentential binding (telescoping): ‘John Frederick/Each executive/Every executive went home. He broiled a steak. He ate dinner. Then he watched television.’ Second pass and total reading times in the region containing the first pronoun were longer for quantified examples than name examples. But there was no indication that telescoping is tightly restricted, for example, to contexts with ‘each’ or to discourses describing stereotypical events composed of predictable subevents. The results suggest that bound variable interpretations are more generally and more readily available than is often assumed. They fit well with Bosch’s (1983) attempt to limit pronoun occurrences to just two types: anaphoric referential pronouns and syntactic agreement pronouns. On this view, ‘bound variable’ interpretations without c-command are really anaphoric pronouns with inferred antecedents. This view is discussed along with the challenges it faces.

This paper proposes a restatement of the Leftness Condition on quantifier binding in configurational terms in the framework of Kayne's (1994) Antisymmetry Theory. The Leftness Condition is reduced to an anti-c-command condition whereby a syntactic constituent that depends on a variable for its denotation cannot asymmetrically c-command that variable. It is argued that this condition also constrains denotational equality between two R-expressions that independently denote the same referent, thus subsuming Principle C. This proposal yields a unified account of strong, weak, weakest, and secondary crossover. I also take into account Culicover & Jackendoff's (1995) argument that binding is sensitive to Conceptual Structure superiority; I argue that in the framework of Representational Modularity (Jackendoff 1997) CS-superiority, asymmetric c-command, and PF precedence may correlate in virtue of correspondence rules. This suggests that the syntactic component may be thought of as mediating between the inherently linear nature of PF and the inherently recursive nature of Conceptual Structure.

Our aim in this paper is to show that Chomsky's Minimalist Program brings in a new way to conceive the Language Faculty and, thus, the Universal Grammar as well. Therefore, it opens up a whole range of possibilities for the language acquisition field. Explanations have to be motivated by virtual conceptual necessity: either through bare output conditions imposed by the interfaces, or through economy conditions of the computational system. Our point is that it should work likewise for language acquisition. If economy conditions play a role in the Language Faculty, then they must be important for the language acquisition process. If interface levels are essential for the Language Faculty, then they must play a role in the acquisition process as well. In order to pinpoint such issues we will discuss some evidence from the asymmetry between the child's initial production of subject and object in different languages. Our guiding hypothesis is that the basic syntactic relation that is privileged by the child acquiring a language is c-command. O que se quer discutir neste artigo é como o Programa Minimalista chomskyano deve ser entendido como uma nova forma de concepção da Faculdade da Linguagem e, portanto, da GU. Nesse sentido, a conseqüência é que abre novas possibilidades para a área de aquisição da linguagem. Sua base está em que qualquer pressuposto tem que ser conceitualmente motivado (virtual conceptual necessity). Tudo que se propõe, ou se justifica em termos das condições externas dadas pelas interfaces, ou por condições de economia previstas para o sistema computacional. Assim, se as condições de economia do sistema computacional são relevantes para que a Faculdade da Linguagem opere otimizadamente, então devem ter um papel também na aquisição. Se os níveis de interface são essenciais para a Faculdade da Linguagem, então pressupõe-se que tenham um papel importante no processo de aquisição. Para ilustrar esses pontos traremos algumas evidências da assimetria que se verifica na produção inicial de crianças entre o sujeito e o objeto em diferentes línguas. Nossa hipótese é que a representação lingüística pela qual a criança se guia no processo de aquisição é a de unidade de comando.

Phrase structure grammars, in which non-terminal symbols on the left side of a production can be rewritten by the string on the right side, together with their Chomsky hierarch classification, are familiar to computer scientists. But, these gramamars are most effective only to generate, and parse, strings. In this report, we introduce a new kind of grmmar in which the right side of the production is simply appended to the intermediate structure in such a way that the left side becomes its "neighborhood" in the new structure. This permits the grammatical definition of many different kinds of "n-dimensional" discrete structures. Several examples are given. Moreover, these grammars yield a formal theory grounded in antimatroid closure spaces. For example, we show that restricted neighborhood expansion grammars capture the essence of finite state and context free phrase structure grammars.

A number of researchers have proposed applications of Girard's Linear Logic [7] to computational linguistics. Most have focused primarily on the connection between linear logic and categorial grammars. In this work we show how linear logic can be used to provide an attractive encoding of phrase structure grammars for parsing structures involving unbounded dependencies. The resulting grammars are closely related to Generalized Phrase Structure Grammars [4, 5]. As part of the presentation we show how a variety of issues, such as island and coordination constraints can be dealt with in this model.

The notion of mild context-sensitivity was formulated in an attempt to express the formal power which is both necessary and sufficient to define the syntax of natural languages. However, some linguistic phenomena such as Chinese numbers and German word scrambling lie beyond the realm of mildly context-sensitive formalisms. On the other hand, the class of range concatenation grammars provides added power w.r.t. mildly context-sensitive grammars while keeping a polynomial parse time behaviour. In this report, we show that this increased power can be used to define the above-mentioned linguistic phenomena with a polynomial parse time of a very low degree.

Formal grammars have been widely used for the formal description of visual languages and for the implementation of general lexical analyzers, parsers, semantic analyzers, syntax-driven visual programming environments, etc. This chapter analyzes the formalism ofsymbol relation grammarsand compares its features with the ones of other existing models. In this formalism each sentence is composed of a set ofsymbol occurrencesrepresenting visual elementary objects, which are related through a set of binaryrelational items.The main feature of symbol relation grammars is the uniform way they use context-free productions to rewrite symbol occurrences as well as relational items. The clearness and uniformity of the derivation process for symbol relation grammars allows syntactic tree structures to be easily defined as a natural extension of the traditional syntactic trees of context-free string grammars. The main application of these structures is to extend well established techniques of syntactic and semantic analysis to the case of symbol relation grammars and prove properties of their derivation process.

Results of computational complexity exist for a wide range of phrase structure-based grammar formalisms, while there is an apparent lack of such results for dependency-based formalisms. We here adapt a result on the complexity of ID/LP-grammars to the dependency framework. Contrary to previous studies on heavily restricted dependency grammars, we prove that recognition (and thus, parsing) of linguistically adequate dependency grammars is NP-complete.

When introducing various classes of contextual grammars, one can use the same style as for the Chomsky grammars, starting with the more complex grammars and particularizing the definition in order to obtain the simpler classes. One can also use the opposite strategy, starting from simpler grammars. Here we shall adopt an intermediate strategy, introducing first the class of grammars which is most used in this book.