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)

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)

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.

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)

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)

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)

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.

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 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 (...) class='Hi'>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 (...) class='Hi'>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)

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)

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)

Involutive Nonassociative Lambek Calculus is a nonassociative version of Noncommutative Multiplicative Linear Logic, but the multiplicative constants are not admitted. InNL adds two linear negations to Nonassociative Lambek Calculus ; it is a strongly conservative extension of NL Logical aspects of computational linguistics. LNCS, vol 10054. Springer, Berlin, pp 68–84, 2016). Here we also add unary modalities satisfying the residuation law and De Morgan laws. For the resulting logic InNLm, we define and study phase spaces. We use them to prove (...) the cut elimination theorem for a one-sided sequent system for InNLm, introduced here. Phase spaces are also employed in studying auxiliary systems InNLm, assuming the k-cyclic law for negation. The latter behave similarly as Classical Nonassociative Lambek Calculus, studied in de Groote and Lamarche :355–388, 2002) and Buszkowski. We reduce the provability in InNLm to that in InNLm. This yields the equivalence of type grammars based on InNLm with -free) context-free grammars and the PTIME complexity of InNLm. (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)

Negative polarity is one of the more elusive aspects of linguistics and a subject which has been gaining in importance in recent years. Written from within the well-defined theoretical framework of Generalized Quantifiers, the three main areas considered in this study are collocations, polarity items and multiple negations. In this mature piece of research, van der Wouden takes into account, not only semantic and syntactic considerations, but also to a large extent, pragmatic ones illustrating a wide array of linguistic (...) approaches. (shrink)

The books’ goal is to answer the question: Do the weaknesses of value-free economics imply the need for a paradigm shift? The author synthesizes criticisms from different perspectives (descriptive and methodological). Special attention is paid to choices over time, because in this area value-free economics has the most problems. In that context, the enriched concept of multiple self is proposed and investigated. However, it is not enough to present the criticisms towards value-free economics. For scientists, (...) a bad paradigm is better than no paradigm. Therefore, the author considers whether value-based economics with normative approaches such as economics of happiness, capability approach, libertarian paternalism, and the concept of multiple self can be the alternative paradigm for value-free economics. This book is essential reading to everyone interested in the current state of economics as a discipline. (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.

Are free will and determinism compatible? Philosophical focus on this deceptively simple `compatibility question' has historically been so pervasive that the entire free will debate is now standardly framed in its terms - that is, as a dispute between compatibilists, who answer the question affirmatively, and incompatibilists, who respond in the negative. This dissertation, in contrast, adopts a position that I call `descriptive variantism,' according to which prevailing notions of free will exhibit significant aspects of both compatibilism (...) and incompatibilism. My formulation and defense of this position provides a framework for considering several important issues that cannot be adequately addressed on the traditional conception of the free will debate. The theoretical advantages of descriptive variantism become apparent, I argue, only after adopting needed refinements to the compatibility question itself. As it stands, this question conflates at least two distinct issues: whether free will, as ordinarily understood, does in fact conflict with determinism, and whether free will should be taken to involve such a conflict. The vast majority of work in this area, I maintain, implies that (a) the shared notion of free will exemplified in everyday usage conforms exclusively to either compatibilism or incompatibilism, and (b) the (singular) position suggested by this shared notion constitutes the most adequate response to the compatibility question. This is a mistake: it ignores several other possibilities, among them the prospect that multiple `shared notions' are implicated in the complex network of judgments, attitudes, and social practices related to free will. Having reformulated various aspects of the free will debate in ways that address these issues, I go on to argue that no single account of free will can underwrite the broad range of phenomena associated with this notion. Most importantly, I maintain that contextual features, especially those related to abstraction and concreteness, engender significantly different notions of free will: abstract contexts tend to elicit judgments and other behaviors conducive to incompatibilism, while concreteness often promotes tendencies best captured by compatibilist theories. I support these empirical claims primarily by drawing out the conceptual implications of recent experimental work on these topics in a variety of disciplines, including philosophy, psychology, and neuroscience, and defend my interpretation against alternative accounts that purport to `explain away' the contextual differences exhibited in the experimental data. If these claims are correct, then the fundamental conflicts inherent in prevailing notions of free will have the potential to manifest themselves in some highly problematic ways. For example, criminal laws enacted in abstract contexts may presuppose constraints on free agency deeply at odds with those implicitly adopted by jurors evaluating concrete violations of these laws. I attempt to make some preliminary progress on these vexing, but vital, issues by suggesting that revision towards compatibilism represents an initially appealing method of resolving some of these practical difficulties. Importantly, though, this suggestion is tentative, particularly insofar as the extent to which such revision is ultimately desirable, feasible, or even psychologically possible remains unclear. Further consideration of these issues thus constitutes an important avenue for future research. (shrink)

Mary Kalantzis was from 2006 to 2016 Dean of the College of Education at the University of Illinois, Urbana-Champaign. Bill Cope is a Professor in the College of Education at the University of Illinois, Urbana-Champaign. They are co-authors of multiple books including Making Sense: Reference, Agency, and Structure in a Grammar of Multimodal Meaning (Cambridge, forthcoming), New Learning: Elements of a Science of Education (Cambridge, 2008, 2012), Literacies (Cambridge 2012, 2016) and e-Learning Ecologies (2017).

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)

We consider the Lambek calculus, or noncommutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an$\omega $-rule, and prove that the derivability problem in this calculus is$\Pi _1^0$-hard. This solves a problem left open by Buszkowski (2007), who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek (...) grammar with unique type assignment, without Lambek’s nonemptiness restriction imposed (cf. Safiullin, 2007). (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)

Cognitive Science, Volume 46, Issue 2, February 2022.

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)

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.

This chapter summarizes research on free will. Progress has been made by discarding outmoded philosophical notions in favor of exploring how ordinary people understand and use the notion of free will. The concept of responsible autonomy captures many aspects of layperson concepts of free will, including acting on one's own (i.e., not driven by external forces), choosing, using reasons and personal values, conscious reflection, and knowing and accepting consequences and moral implications. Free will can thus be (...) understood as form of volition (action control) that evolved to enable people to live in cultural societies. Much work has shown that belief in free will (as opposed to disbelief) is associated with actions that are conducive to functioning well in culture, including helpfulness, restraint of aggression, learning via counterfactual analysis, thinking for oneself, effective job performance, and appropriate gratitude. Belief in free will increases in response to misdeeds by others, thus emphasizing the link to personal responsibility. Research on volition indicates that self-regulation, intelligent reasoning, decision making, and initiative all deplete a (common) limited energy source, akin to the folk notion of willpower and linked to the body's glucose supplies. Free will is thus not an absolute or constant property of persons but a variable, fluctuating capability—one that is nonetheless highly adaptive for individuals and society. -/- The notion that people have free will has been invoked in multiple contexts. Legally and morally, it explains why people can be held responsible for their actions. Theologically, it was used to explain why a supposedly kind and omniscient god would send most of the people he created to hell (Walker, 1964). Yet, for such an important concept, there remains wide-ranging disagreement and confusion over its existence and its nature. For example, philosophers still debate whether humans truly have free will and, if so, under what conditions human volition deserves to be considered free (Kane, 2011). In psychology, most theorists believe that humans engage in self-control, rational choice, planning, initiative, and related acts of volition. The debate is not whether these things occur but merely whether these should be called free will. -/- This chapter will provide an overview of recent psychology experiments concerned with free will. There are three main and quite distinct sets of problems, each with associated lines of research. The first is concerned with how people understand the idea of free will. The second concerns the causes and consequences of believing in free will. The third focuses on the actual volitional processes that guide human action. (shrink)

We argue that the extant evidence for Stoic logic provides all the elements required for a variable-free theory of multiple generality, including a number of remarkably modern features that straddle logic and semantics, such as the understanding of one- and two-place predicates as functions, the canonical formulation of universals as quantified conditionals, a straightforward relation between elements of propositional and first-order logic, and the roles of anaphora and rigid order in the regimented sentences that express multiply general propositions. (...) We consider and reinterpret some ancient texts that have been neglected in the context of Stoic universal and existential propositions and offer new explanations of some puzzling features in Stoic logic. Our results confirm that Stoic logic surpasses Aristotle’s with regard to multiple generality, and are a reminder that focusing on multiple generality through the lens of Frege-inspired variable-binding quantifier theory may hamper our understanding and appreciation of pre-Fregean theories of multiple generality. (shrink)

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].

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.

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)

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)