In this paper we prove the Chomsky Conjecture (all languages recognized by the Lambek calculus are context-free) for both the full Lambek calculus and its product-free fragment. For the latter case we present a construction of context-free grammars involving only product-free types.

We examine the expressive power of probabilistic context free grammars (PCFGs), with a special focus on the use of probabilities as a mechanism for reducing ambiguity by filtering out unwanted parses. Probabilities in PCFGs induce an ordering relation among the set of trees that yield a given input sentence. PCFG parsers return the trees bearing the maximum probability for a given sentence, discarding all other possible trees. This mechanism is naturally viewed as a way of defining a new (...) class of tree languages. We formalize the tree language thus defined, study its expressive power, and show that the latter is beyond context freeness. While the increased expressive power offered by PCFGs helps to reduce ambiguity, we show that, in general, it cannot be decided whether a PCFG removes all ambiguities. (shrink)

We examine the expressive power of probabilistic context free grammars (PCFGs), with a special focus on the use of probabilities as a mechanism for reducing ambiguity by filtering out unwanted parses. Probabilities in PCFGs induce an ordering relation among the set of trees that yield a given input sentence. PCFG parsers return the trees bearing the maximum probability for a given sentence, discarding all other possible trees. This mechanism is naturally viewed as a way of defining a new (...) class of tree languages. We formalize the tree language thus defined, study its expressive power, and show that the latter is beyond context freeness. While the increased expressive power offered by PCFGs helps to reduce ambiguity, we show that, in general, it cannot be decided whether a PCFG removes all ambiguities. (shrink)

While Ç ´Ò¿ µ methods for parsing probabilistic context-free grammars (PCFGs) are well known, a tabular parsing framework for arbitrary PCFGs which allows for botton-up, topdown, and other parsing strategies, has not yet been provided. This paper presents such an algorithm, and shows its correctness and advantages over prior work. The paper finishes by bringing out the connections between the algorithm and work on hypergraphs, which permits us to extend the presented Viterbi (best parse) algorithm to an inside (...) (total probability) algorithm. (shrink)

fundamental rule” in an order-independent manner, such that the same basic algorithm supports top-down and Most PCFG parsing work has used the bottom-up bottom-up parsing, and the parser deals correctly with CKY algorithm (Kasami, 1965; Younger, 1967) with the difficult cases of left-recursive rules, empty elements, Chomsky Normal Form Grammars (Baker, 1979; Jeand unary rules, in a natural way.

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional (...) yield of an MSO-definable three-dimensional tree language. (shrink)

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order (...) operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy. (shrink)

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Abstract Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order (...) operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Abstract Categorial Hierarchy. (shrink)

Notice that this paper has not claimed that all natural languages are CFL's. What it has shown is that every published argument purporting to demonstrate the non-context-freeness of some natural language is invalid, either formally or empirically or both.18 Whether non-context-free characteristics can be found in the stringset of some natural language remains an open question, just as it was a quarter century ago.Whether the question is ultimately answered in the negative or the affirmative, there will be (...) interesting further questions to ask. If it turns out that natural languages are indeed always CFL's, it will be reasonable to ask whether this helps to explain why speakers apparently recognize so quickly whether a presented utterance corresponds to a grammatical sentence or not, and to associate structural and semantic details with it. It might also be reasonable to speculate about the explanation for the universally context-free character of the languages used by humans, and to wonder whether evolutionary biological factors are implicated in some way (Sampson (1979) could be read in this light). And naturally, it will be reasonable to pursue the program put forward by Gazdar (1981, in press) to see to what extent CFL-inducing grammatical devices can be exploited to yield insightful descriptions of natural languages that capture generalizations in revealing ways.If a human language that is not a CFL is proved to exist, on the other hand, a different question will be raised: give the non-context-free character of human languages in general, why has this property been so hard to demonstrate that it has taken over twenty-five years to bring it to light since the issue was first explicitly posed? If human languages do not have to be CFL's, why do so many (most?) of them come so close to having the property of context-freeness? And, since the CFL's certainly constitute a very broad class of mathematically natural and computationally tractable languages, what property of human beings or their communicative or cognitive needs is it that has caused some linguistic communities to reach beyond the boundaries of this class in the course of evolving a linguistic system?Either way, we shall be interested to see our initial question resolved, and further questions raised. One cautionary word should be said, however, about the implications (or lack of them) that the answer will have for grammatical studies. Chomsky has repeatedly stated that he does not see weak generative capacity as a theme of central importance in the theory of grammar, and we agree. It is very far from being the case that the recent resurgence of interest in exploring the potential of CF-PSG or equivalent systems will, or should, be halted dead in its tracks by the discovery (if it is ever forthcoming) that some natural language is not a CFL. In the area of parsing, for instance, it seems possible that natural languages are not only parsed on the basis of constituent structure such as a CF-PSG would assign, but are parsed as if they were finite state languages (see Langendoen (1975) and Church (1980) for discussion along these lines). That is, precisely those construction-types that figure in the various proofs that English is not an FSL appear to cause massive difficulty in the human processing system; the sentences crucial to the proofs are for the most part unprocessable unless they are extremely short (yet the arguments for English not being and FSL only go through if length is not an issue). This means that in practice properties of finite state grammars are still of great potential importance to linguistic theory despite the fact that they do not provide the framework for defining the total class of grammatical sentences. The same would almost certannly be true of CF-PSG's if they were shown to be inadequate in a similar sense. It is highly unlikely that the advances made so far in far in phrase structure description could be nullified by a discovery about weak generative capacity. Moreover, there are known to be numerous ways in which the power of CF-PSG's can be marginally enhanced to permit, for example, xx languages to be generated without allowing anything like the full class of recursively enumerable or even context-sensitive languages (see Hopcroft and Ullmann (1979), Chapter 14) for an introduction to this topic, noting especially Figure 14.7 on p. 393. The obvious thing to do if natural languages were ever shown not to be CFL's in the general case would be to start exploring such minimal enhancements of expressive power to determine exactly what natural languages call for in this regard and how it could be effectively but parsimoniously provided in a way that closely modelled human linguistic capacities.In the meantime, it seems reasonable to assume that the natural languages are a proper subset of the infinite-cardinality CFL's until such time as they are validly shown not to be. (shrink)

Proof assistants are software-based tools that are used in the mechanization of proof construction and validation in mathematics and computer science, and also in certified program development. Different such tools are being increasingly used in order to accelerate and simplify proof checking, and the Coq proof assistant is one of the most well known and used in large-scale projects. Language and automata theory is a well-established area of mathematics, relevant to computer science foundations and information technology. In particular, context- (...) class='Hi'>free language theory is of fundamental importance in the analysis, design, and implementation of computer programming languages. This work describes a formalization effort, using the Coq proof assistant, of fundamental results of the classical theory of contextfree grammars and languages. These include closure properties (union, concatenation, and Kleene star), grammar simplification (elimination of useless symbols, inaccessible symbols, empty rules, and unit rules), the existence of a Chomsky Normal Form for context-free grammars and the Pumping Lemma for context-free languages. The result is an important set of libraries covering the main results of context-free language theory, with more than 500 lemmas and theorems fully proved and checked. As it turns out, this is a comprehensive formalization of the classical context-free language theory in the Coq proof assistant and includes the formalization of the Pumping Lemma for context-free languages. The perspectives for the further development of this work are diverse and can be grouped in three different areas: inclusion of new devices and results, code extraction, and general enhancements of its libraries. (shrink)

We introduce _Interleave-Disjunction-Lock parallel multiple context-free grammars_ (IDL-PMCFG), a novel grammar formalism designed to describe the syntax of free word order languages that allow for extensive interleaving of grammatical constituents. Though interleaved constituents, and especially the so-called hyperbaton, are common in several ancient (Classical Latin and Greek, Sanskrit...) and modern (Hungarian, Finnish...) languages, these syntactic structures are often difficult to express in existing formalisms. The IDL-PMCFG formalism combines Seki et al.’s parallel multiple context-free grammars (...) (PMCFG) with Nederhof and Satta’s IDL expressions. We define the semantics of IDL-PMCFGs and study their expressivity, proving that IDL-PMCFG extends both PMCFG and IDL-CFG (context-free grammars equipped with IDL expressions) and that IDL-PMCFG parsing is \(\mathrm {NP}\) -hard. We then introduce COMPĀ, a programming language extending Ranta’s Grammatical Framework (GF) and built as a high-level front-end formalism to IDL-PMCFG for practical grammar development. We present a parsing algorithm for IDL-PMCFG inspired by earlier Earley-style PMCFG parsing algorithms and Nederhof and Satta’s IDL graphs and give a worst-case estimate of its complexity as a function of several metrics on IDL expressions, the size of the input and a new notion of the _G_-density of a language. (shrink)

This paper classifies a family of grammar formalisms that extendcontext-free grammar by talking about tuples of terminal strings, ratherthan independently combining single terminal words into larger singlephrases. These include a number of well-known formalisms, such as headgrammar and linear context-free rewriting systems, but also a new formalism,(simple) literal movement grammar, which strictly extends the previouslyknown formalisms, while preserving polynomial time recognizability.The descriptive capacity of simple literal movement grammars isillustrated both formally through a weak generative (...) capacity argument and ina more practical sense by the description of conjunctive cross-serialrelative clauses in Dutch. After sketching a complexity result and drawing anumber of conclusions from the illustrations, it is then suggested that thenotion of mild context-sensitivity currently in use, that depends on therather loosely defined concept of constant growth, needs a modification toapply sensibly to the illustrated facts; an attempt at such a revision isproposed. (shrink)

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.

The aim of UK-REACH (“The United Kingdom Research study into Ethnicity And COVID-19 outcomes in Healthcare workers”) is to understand if, how, and why healthcare workers (HCWs) in the United Kingdom (UK) from ethnic minority groups are at increased risk of poor outcomes from COVID-19. In this article, we present findings from the ethical and legal stream of the study, which undertook qualitative research seeking to understand and address legal, ethical, and social acceptability issues around data protection, privacy, and information (...) governance associated with the linkage of HCWs’ registration data and healthcare data. We interviewed 22 key opinion leaders in healthcare and health research from across the UK in two-to-one semi-structured interviews. Transcripts were coded using qualitative thematic analysis. Participants told us that a significant aspect of Big Data research in public health is varying drivers of mistrust—of the research itself, research staff and funders, and broader concerns of mistrust within participant communities, particularly in the context of COVID-19 and those situated in more marginalised community settings. However, despite the challenges, participants also identified ways in which legally compliant and ethically informed approaches to research can be crafted to mitigate or overcome mistrust and establish greater confidence in Big Data public health research. Overall, our research indicates that a “Big Data Ethics by Design” approach to research in this area can help assure (1) that meaningful community and participant engagement is taking place and that extant challenges are addressed, and (2) that any new challenges or hitherto unknown unknowns can be rapidly and properly considered to ensure potential (but material) harms are identified and minimised where necessary. Our findings indicate such an approach, in turn, will help drive better scientific breakthroughs that translate into medical innovations and effective public health interventions, which benefit the publics studied, including those who are often marginalised in research. (shrink)

While rules and exemplars are usually viewed as opposites, this paper argues that they form end points of the same distribution. By representing both rules and exemplars as (partial) trees, we can take into account the fluid middle ground between the two extremes. This insight is the starting point for a new theory of language learning that is based on the following idea: If a language learner does not know which phrase‐structure trees should be assigned to initial sentences, s/he allows (...) (implicitly) for all possible trees and lets linguistic experience decide which is the “best” tree for each sentence. The best tree is obtained by maximizing “structural analogy” between a sentence and previous sentences, which is formalized by the most probable shortest combination of subtrees from all trees of previous sentences. Corpus‐based experiments with this model on the Penn Treebank and the Childes database indicate that it can learn both exemplar‐based and rule‐based aspects of language, ranging from phrasal verbs to auxiliary fronting. By having learned the syntactic structures of sentences, we have also learned the grammar implicit in these structures, which can in turn be used to produce new sentences. We show that our model mimicks children’s language development from item‐based constructions to abstract constructions, and that the model can simulate some of the errors made by children in producing complex questions. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for (...) string and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

The classification of grammars that became known as the Chomsky hierarchy was an exploration of what kinds of regularities could arise from grammars that had various conditions imposed on their structure. Intersubstitutability is closely related to the way different levels on the Chomsky hierarchy correspond to different kinds of memory. This chapter deals with the general concept of a string‐rewriting grammar, which provides the setting in which the Chomsky hierarchy can be formulated. An unrestricted rewriting grammar works with (...) a specified set of nonterminal symbols, and specified set of terminal symbols. From the very outset there were doubts about about whether context‐free grammars (CFGs) could form the basis of a theory of natural language syntax. The grammar's rewrite rules correspond to the automaton's transitions. Chomsky argued that even if the generative capacity of CFGs turned out to be sufficient for English, the resulting grammars would be unreasonably complex. (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)

This paper defines the grammar class of sequentially indexed grammars. Sequentially indexed grammars are the result of a change in the index stack handling mechanism of indexed grammars [Aho68, Aho69]. Sequentially indexed grammars are different from linear indexed grammars [Gaz88]. Like indexed languages, sequentially indexed languages are a fully abstract language class. Unlike indexed languages, sequentially indexed languages allow polynomial parsing algorithms. We give a polynomial algorithm for parsing with sequentially indexed gramamrs that is an extension of the Earley (...) algorithm for parsing with context free grammars. (shrink)

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

A number of criticisms of a recent paper byare made. (1) In attempting to assess the observational adequacy of story grammars, they state that a context‐free grammar cannot handle discontinuous elements; however, they do not show that such elements occur in the domain to which the grammars apply. Further, they do not present adequate evidence for their claim that there are acceptable stories not accounted for by existing grammars and that the grammars will accept nonstories such as (...) procedures. (2) They state that it has been proven that under natural conditions children cannot learn transformational grammars, which is a misrepresentation of the learnability proofs which have been offered. (3) Most important, they take an unduly narrow approach to story understanding by claiming that people only understand story content and do not have knowledge of story structure which is useful in comprehension or memory. Counterevidence from the literature is cited which indicates that such knowledge is both useful and used, and a number of methods for assessing the psychological adequacy of structural models are discussed. (shrink)

Lambek categorial grammars is a class of formal grammars based on the Lambek calculus. Pentus proved in 1993 that they generate exactly the class of context-free languages without the empty word. In this paper, we study categorial grammars based on the Lambek calculus with the permutation rule LP. Of particular interest is the product-free fragment of LP called the Lambek-van Benthem calculus LBC. Buszkowski in his 1984 paper conjectured that grammars based on the Lambek-van Benthem calculus (LBC-grammars (...) for short) generate exactly permutation closures of context-free languages. In this paper, we disprove this conjecture by presenting a language generated by an LBC-grammar that is not a permutation closure of any context-free language. Firstly, we introduce an ad-hoc modification of vector addition systems called linearly-restricted branching vector addition systems with states and additional memory (LRBVASSAMs for short) and prove that the latter are equivalent to LBC-grammars. Then we construct an LRBVASSAM that generates a non-semilinear set and thus disprove Buszkowski’s conjecture. Since Buszkowski’s conjecture is false, not so much is known about the languages generated by LBC-grammars or by LP-grammars. The equivalence of LRBVASSAMs and LBC-grammars allows us to establish a number of their properties. We show that LP-grammars generate the same class of languages as LBC-grammars; that is, removing product from LP does not decrease expressive power of corresponding categorial grammars. We also prove that this class of languages is closed under union, intersection, concatenation, and Kleene plus. (shrink)

We generalize intuitionistic tense logics to the multi-modal case by placing grammar logics on an intuitionistic footing. We provide axiomatizations for a class of base intuitionistic grammar logics as well as provide axiomatizations for extensions with combinations of seriality axioms and what we call "intuitionistic path axioms". We show that each axiomatization is sound and complete with completeness being shown via a typical canonical model construction.

We present a rendering of some common grammatical formalisms in terms of evolving algebras. Though our main concern in this paper is on constraint-based formalisms, we also discuss the more basic case of context-free grammars. Our aim throughout is to highlight the use of evolving algebras as a specification tool to obtain grammar formalisms.

The equivalence of (classical) categorial grammars and context-free grammars, proved by Gaifman [4], is a very basic result of the theory of formal grammars (an essentially equivalent result is known as the Greibach normal form theorem [1], [14]). We analyse the contents of Gaifman's theorem within the framework of structure and type transformations. We give a new proof of this theorem which relies on the algebra of phrase structures and exhibit a possibility to justify the key construction used (...) in Gaifman's proof by means of the Lambek calculus of syntactic types [15]. (shrink)

Classical categorial grammars are the grammars introduced by Ajdukiewicz [1] and formalized by Bar-Hillel [2], Bar-Hillel et al. [3]. In [3] there is proved the weak equivalence of CCG’s and context-free grammars [6]. In this note we characterize the strong generative capacity of finite and rigid CCG’s, i.e. their capacity of structure generation. These results are more completely discussed in [4], [5].

This paper examines feature selection for log linear models over rich constraint-based grammar (HPSG) representations by building decision trees over features in corresponding probabilistic context free grammars (PCFGs). We show that single decision trees do not make optimal use of the available information; constructed ensembles of decision trees based on different feature subspaces show signifi- cant performance gains (14% parse selection error reduction). We compare the performance of the learned PCFG grammars and log linear models over the (...) same features. (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)

This paper contributes to the semantic typology of dependent indefinites, by accounting for the distribution and interpretation of the Romanian indefinite vreun. It is shown that its occurrences are restricted to negative polarity and a subset of modal contexts. More specifically, the study of its behavior in intensional environments reveals that vreun is systematically incompatible with non-epistemic operators, a restriction we capture by proposing a novel empirical generalization (‘the epistemic constraint’). To account for the observed pattern, we adopt the unitary (...) approach to polarity in Chierchia (Logic in Grammar: polarity, free choice and intervention, 2013a; in: Fălăuş (ed.) Alternatives in semantics, 2013b) and derive the properties of vreun from its obligatory association with alternatives. Its distributional restrictions are argued to follow from the interplay between the types of alternatives it activates (scalar and subdomain alternatives), the way these alternatives are factored into meaning (via an independently motivated mechanism of exhaustification) and the lexical semantics of the operators in the context of occurrence. We propose that the epistemic constraint arises from the lexicalization of an inference (anti-total variation) that non-epistemic operators can never satisfy. (shrink)

Two axiomatizations of the nonassociative and commutative Lambek syntactic calculus are given and their equivalence is proved. The first axiomatization employs Permutation as the only structural rule, the second one, with no Permutation rule, employs only unidirectional types. It is also shown that in the case of the Ajdukiewicz calculus an analogous equivalence is valid only in the case of a restricted set of formulas. Unidirectional axiomatizations are employed in order to establish the generative power of categorial grammars based on (...) the nonassociative and commutative Lambek calculus with product. Those grammars produce CF-languages of finite degree generated by CF-grammars closed with respect to permutations. (shrink)

Minimalist grammars (MGs) and multiple context-free grammars (MCFGs) are weakly equivalent in the sense that they define the same languages, a large mildly context-sensitive class that properly includes context-free languages. But in addition, for each MG, there is an MCFG which is strongly equivalent in the sense that it defines the same language with isomorphic derivations. However, the structure-building rules of MGs but not MCFGs are defined in a way that generalizes across categories. Consequently, MGs (...) can be exponentially more succinct than their MCFG equivalents, and this difference shows in parsing models too. An incremental, top-down beam parser for MGs is defined here, sound and complete for all MGs, and hence also capable of parsing all MCFG languages. But since the parser represents its grammar transparently, the relative succinctness of MGs is again evident. Although the determinants of MG structure are narrowly and discretely defined, probabilistic influences from a much broader domain can influence even the earliest analytic steps, allowing frequency and context effects to come early and from almost anywhere, as expected in incremental models. (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)

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)

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)

Back in the 1980’s, the class of mildly context-sensitive formalisms was introduced so as to capture the syntax of natural languages. While the languages generated by such formalisms are constrained by the constant-growth property, the most well-known and used ones—like tree-adjoining grammars or multiple context-free grammars—generate languages which verify the stronger property of being semilinear. In, the operation of IO-substitution was created so as to exhibit mildly-context sensitive classes of languages which are not semilinear. In the (...) present article, we extend the notion of semilinearity, and characterize the Parikh image of the languages in IO, the closure of a class L of semilinear languages under IO-substitution, as universally-semilinear. Based on this result and on the work of Fischer on macro-grammars, we then show that IO is not closed under inverse homomorphism when L is closed under inverse homomorphism, and encompasses the class of regular languages. This result proves that IO is not a full AFL, where \ denotes the class of multiple context-free languages, closing an open question in Bourreau et al.. More importantly, our proof gives an insight into the relation between the non-closure under inverse homomorphism of \}\) and how IO-substitution breaks semilinearity. (shrink)

The computation of scalar implicatures is sometimes costly relative to basic meanings. Among the costly computations are those that involve strengthening `some' to `not all' and strengthening inclusive disjunction to exclusive disjunction. The opposite is true for some other cases of strengthening, where the strengthened meaning is less costly than its corresponding basic meaning. These include conjunctive strengthenings of disjunctive sentences (e.g., free-choice inferences) and exactly-readings of numerals. Assuming that these are indeed all instances of strengthening via implicature/exhaustification, the (...) puzzle is to explain why strengthening sometimes increases costs while at other times it decreases costs. I develop a theory of processing costs that makes no reference to the strengthening mechanism or to other aspects of the derivation of the sentence's form/meaning. Instead, costs are determined by domain-general considerations of the grammar's output, and in particular by aspects of the meanings of ambiguous sentences and particular ways they update the context. Specifically, I propose that when the hearer has to disambiguate between a sentence's basic and strengthened meaning, the processing cost of any particular choice is a function of (i) a measure of the semantic complexity of the chosen meaning and (ii) a measure of how much relevant uncertainty it leaves behind in the context. I measure semantic complexity with Boolean Complexity in the propositional case and with semantic automata in the quantificational case, both of which give a domain-general measure of the minimal representational complexity needed to express the given meaning. I measure relevant uncertainty with the information-theoretic notion of entropy; this domain-general measure formalizes how `far' the meaning is from giving a complete answer to the question under discussion, and hence gives an indication of how much representational complexity is yet to come. Processing costs thus follow from domain-general considerations of current and anticipated representational complexity. The results might also speak to functional motivations for having strengthening mechanisms in the first place. Specifically, exhaustification allows language users to use simpler forms than would be available without it to both resolve relevant uncertainties and convey complex meanings. (shrink)

A defining assumption in the debate on contextual influences on truth-conditional content is that such content is often incompletely determined by what is specified in linguistic form. The debate then turns on whether this is evidence for positing a more richly articulated logical form or else a pragmatic process of free enrichment that posits truly unarticulated constituents that are unspecified in linguistic form. Questioning this focus on semantics and pragmatics, this article focuses on the independent grammatical dimensions of the (...) problem. Against the background of a principled account of the different ways in which the lexicon and the grammar, respectively, determine aspects of propositional meaning, and an uncontentious notion of content, nothing turns out to be ‘missing’ in grammatical expressions in order for them to encode complete propositional thoughts. As this predicts, when putatively hidden constituents are made overt or are otherwise added, propositions result that are systematically different from the thoughts originally expressed. Context, while potentially affecting lexically specified aspects of meaning, never affects grammar-determined ones, suggesting a specific role for grammar in the normal cognitive mode. (shrink)

This paper extends the Earley parsing algorithm for context free languages [3] to the case of sequentially indexed languages. Sequentially indexed languages are related to indexed languages [1, 2]. The difference is that parallel processing of index stacks is replaced by sequential processing [4].

The task of inducing grammar structures has received a great deal of attention. The reasons why researchers have studied are different; to use grammar induction as the first stage in building large treebanks or to make up better language models. However, grammar induction has inherent computational complexity. To overcome it, some grammar induction algorithms add new production rules incrementally. They refine the grammar while keeping their computational complexity low. In this paper, we propose a new (...) efficient grammar induction algorithm. Although our algorithm is similar to algorithms which learn a grammar incrementally, our algorithm uses the graphical EM algorithm instead of the Inside-Outside algorithm. We report results of learning experiments in terms of learning speeds. The results show that our algorithm learns a grammar in constant time regardless of the size of the grammar. Since our algorithm decreases syntactic ambiguities in each step, our algorithm reduces required time for learning. This constant-time learning considerably affects learning time for larger grammars. We also reports results of evaluation of criteria to choose nonterminals. Our algorithm refines a grammar based on a nonterminal in each step. Since there can be several criteria to decide which nonterminal is the best, we evaluate them by learning experiments. (shrink)

On a traditional view, the semantics of natural language makes essential use of a context parameter, i.e. a set of coordinates that represents the situation of speech. In classical semantic frameworks, this parameter plays two key roles: first, context contributes to determining the content of utterance; second, it is crucial for defining logical consequence. I point out that recent empirical proposals about context shift in natural language (in particular, context-shifting semantics in the style of Anand and (...) Nevins 2004) are incompatible with the traditional view of context. At the same time, there is increasing cross-linguistic support for this brand of context shift. Hence I suggest that context has no place in semantic theory proper. We should revert back to so-called multiple-indexing frameworks that were developed by Montague and others, and relegate context to the postsemantic stage. (shrink)