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)

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)

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge ofω-languages accepted by 1-counter Büchi automata is equivalent to the analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automatonand (...) a Büchi automatonsuch that: There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge gameW,L()); There exists a model of ZFC in which the Wadge gameW,L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge gameW,L()). (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)

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

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)

Based on the analysis of narrations in Free Indirect Discourse and the Historical Present, we argue that the grammatical notion of context of speech should be ramified into a Context of Thought and a Context of Utterance. Tense and person depend on the Context of Utterance, while all other indexicals are evaluated with respect to the Context of Thought. Free Indirect Discourse and the Historical Present are analyzed as special combinatorial possibilities that arise (...) when the two contexts are distinct, and exactly one of them is presented as identical to the physical point at which the sentence is articulated. (shrink)

In this paper I present a linguistic investigation of the literary style known as free indirect discourse within the framework of formal semantics. I will argue that a semantics for free indirect discourse involves more than a mechanism for the independent context shifting of pronouns and other deictic elements. My argumentation is fueled by literary examples of free indirect discourse involving what I call language shifts: -/- Most of the great flame-throwers were there and naturally, handling (...) Big John de Conquer and his works. How he had done everything big on earth, then went up tuh heben without dying atall. Went up there picking a guitar and got all de angels doing the ring-shout round and round de throne...that brought them back to Tea Cake. How come he couldn’t hit that box a lick or two? (Hurston 1937, Their Eyes Were Watching God) -/- Free indirect discourse combines elements of both, but it seems decidedly closer to direct discourse. I examine the reigning semantic analysis of free indirect discourse, a variant of the demonstrative account of direct discourse featuring “double context dependence” (Banfield 1982,Schlenker 2004). After showing that this type of account has fundamental difficulties with language shift data like (1), I close with a brief sketch of an alternative analysis based on “mixed quotation.”. (shrink)

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)

In this paper I present an overview of my research in the philosophy of language in mind over more than thirty years, from my early work on speech act theory to my current work on mental files. The unifying theme is context-dependence,both in language and thought. I distinguish several varieties of context-dependence and, along the way, provide tentative accounts of various phenomena: performative utterances, indexicals, modulation (metonymy and loose talk, free enrichment), de se thought, the content of (...) experiential states, and immunity to error through misidentification. (shrink)

The problem of teaching and learning of Russian language and literature in schools with native language of teaching related to the implementation of the principle of dialogue between cultures. The article draws on the results of the survey of graduates of the two high schools of Kazan: School #2 with teaching in Tatar language and school #37 with teaching in Russian-language. The results of the survey are associated with the problems of bilingualism, multiculturalism and bimentality. Graduates from Tatar language gymnasium (...) are bilingual and fluent in Russian and Tatar languages. 97% of graduates of Tatar gymnasium speak, read and write free in their native language and 96% in Russian. Bilingualism acts in this case like one of the manifestations of inter-ethnic interaction, a particular manifestation of biculturalism. In the National School dialogue of cultures passes through a system of parallel study of both Russian and Tatar languages and literatures: the formation of a bicultural, bilingual, bimental personality able to perceive not only the native culture, but also other culture as the native is taking place. (shrink)

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.

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)

Our self-conception derives mostly from our own experience. We believe ourselves to be conscious, rational, social, ethical, language-using, political agents who possess free will. Yet we know we exist in a universe that consists of mindless, meaningless, unfree, nonrational, brute physical particles. How can we resolve the conflict between these two visions? In _Freedom and Neurobiology_, the philosopher John Searle discusses the possibility of free will within the context of contemporary neurobiology. He begins by explaining the relationship (...) between human reality and the more fundamental reality as described by physics and chemistry. Then he proposes a neurobiological resolution to the problem by demonstrating how various conceptions of free will have different consequences for the neurobiology of consciousness. In the second half of the book, Searle applies his theory of social reality to the problem of political power, explaining the role of language in the formation of our political reality. The institutional structures that organize, empower, and regulate our lives-money, property, marriage, government-consist in the assignment and collective acceptance of certain statuses to objects and people. Whether it is the president of the United States, a twenty-dollar bill, or private property, these entities perform functions as determined by their status in our institutional reality. Searle focuses on the political powers that exist within these systems of status functions and the way in which language constitutes them. Searle argues that consciousness and rationality are crucial to our existence and that they are the result of the biological evolution of our species. He addresses the problem of free will within the context of a neurobiological conception of consciousness and rationality, and he addresses the problem of political power within the context of this analysis. A clear and concise contribution to the free-will debate and the study of cognition, _Freedom and Neurobiology_ is essential reading for students and scholars of the philosophy of mind. (shrink)

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages. ii) We define local languages, (...) a class of languages between free local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of "pumping lemmas", analogs for each local language L of the "uvxyz theorem" of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite "progressions" of words included in L, and they imply the decidability of various questions about L or L ∞ . iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals. We hope that these results are useful for a model-theoretic approach to the theory of formal languages. (shrink)

If one formulates Helmholtz’s ideas about perception in terms of modern-day theories one arrives at a model of perceptual inference and learning that can explain a remarkable range of neurobiological facts. Using constructs from statistical physics it can be shown that the problems of inferring what cause our sensory inputs and learning causal regularities in the sensorium can be resolved using exactly the same principles. Furthermore, inference and learning can proceed in a biologically plausible fashion. The ensuing scheme rests on (...) Empirical Bayes and hierarchical models of how sensory information is generated. The use of hierarchical models enables the brain to construct prior expectations in a dynamic and context-sensitive fashion. This scheme provides a principled way to understand many aspects of the brain’s organisation and responses. In this paper, we suggest that these perceptual processes are just one emergent property of systems that conform to a free-energy principle. The free-energy considered here represents a bound on the surprise inherent in any exchange with the environment, under expectations encoded by its state or configuration. A system can minimise free-energy by changing its configuration to change the way it samples the environment, or to change its expectations. These changes correspond to action and perception, respectively, and lead to an adaptive exchange with the environment that is characteristic of biological systems. This treatment implies that the system’s state and structure encode an implicit and probabilistic model of the environment. We will look at models entailed by the brain and how minimisation of free-energy can explain its dynamics and structure. (shrink)