We show the existence of a high r. e. degree bounding only joins of minimal pairs and of a high2 nonbounding r. e. degree. MSC: 03D25.

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)

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)

This paper deals with the interpretation and distribution of universal Free Choice (FC) items, such as English FC any or Spanish cualquiera. Crosslinguistically, universal FC items can be characterized as follows. First, they have a restricted distribution. Second, they express freedom of choice: the sentence You can take any card conveys the information that the addressee is free to pick whichever card she chooses. Under standard assumptions, the truth conditions of sentences like You can take any (...) card are taken to be captured by formalizations in which a universal quantifier ranging over individuals has wide scope over the possibility modal. The crucial observation that informs the account in this paper is that this type of formalization cannot capture the freedom of choice component. I will argue that in order to derive the right interaction between possibility modals and FC items, we need to add an exclusiveness condition to the standard wide scope paraphrases. The same proposal that guarantees freedom of choice will automatically account for the distribution restrictions of FC items. The formal implementation of this proposal is cast in the Hamblin semantics proposed in Kratzer and Shimoyama (Indeterminate phrases: The view from Japanese, 2002). (shrink)

A universally free logic is a system of quantification theory, with or without identity, whose theses remain logically true if the domain of quantification is empty and some of the singular terms present in the language do not denote existing objects. In the West, logics satisfying and ones satisfying were developed starting in the 1950s. But Stanisław Jaśkowski preceded all this work by some twenty years: his paper “On the Rules of Supposition in Formal Logic” of 1934 (...) can be regarded as containing, at least implicitly, the first universally free logic. The system proposed there is an inclusive logic as it is, and a straightforward extension of it is also free. (shrink)

How does one formalize the structure of structures necessary for the foundations of physics? This work is an attempt at conceptualizing the metaphysics of pregeometric structures, upon which new and existing notions of quantum geometry may find a foundation. We discuss the philosophy of pregeometric structures due to Wheeler, Leibniz as well as modern manifestations in topos theory. We draw attention to evidence suggesting that the framework of formal language, in particular, homotopy type theory, provides the conceptual building (...) blocks for a theory of pregeometry. This work is largely a synthesis of ideas that serve as a precursor for conceptualizing the notion of space in physical theories. In particular, the approach we espouse is based on a constructivist philosophy, wherein ``structureless structures'' are syntactic types realizing formal proofs and programs. Spaces and algebras relevant to physical theories are modeled as type-theoretic routines constructed from compositional rules of a formal language. This offers the remarkable possibility of taxonomizing distinct notions of geometry using a common theoretical framework. In particular, this perspective addresses the crucial issue of how spatiality may be realized in models that link formal computation to physics, such as the Wolfram model. (shrink)

A wide-ranging history of the intellectual developments that produced the modern idea of the algorithm. Bringing together the histories of mathematics, computer science, and linguistic thought, Language and the Rise of the Algorithm reveals how recent developments in artificial intelligence are reopening an issue that troubled mathematicians long before the computer age. How do you draw the line between computational rules and the complexities of making systems comprehensible to people? Here Jeffrey M. Binder offers a compelling tour of four (...) visions of universal computation that addressed this issue in very different ways: G. W. Leibniz's calculus ratiocinator; a universal algebra scheme Nicolas de Condorcet designed during the French Revolution; George Boole's nineteenth-century logic system; and the early programming language ALGOL, whose name is short for algorithmic language. These episodes show that symbolic computation has repeatedly become entangled in debates about the nature of communication. To what extent can meaning be controlled by individuals, like the values of a and b in algebra, and to what extent is meaning inevitably social? By attending to this long-neglected question, we come to see that the modern idea of the algorithm is implicated in a long history of attempts to maintain a disciplinary boundary separating technical knowledge from the languages people speak day to day. Machine learning, in its increasing dependence on words, now places this boundary in jeopardy, making its stakes all the more urgent to understand. The idea of the algorithm is a levee holding back the social complexity of language, and it is about to break. This book is about the flood that inspired its construction. (shrink)

Pictorial free perception reports are sequences in comics or film of one unit that depicts an agent who is looking, and a following unit that depicts what they see. This paper proposes an analysis in possible worlds semantics and event semantics of such sequences. Free perception sequences are implicitly anaphoric, since the interpretation of the second unit refers to the agent depicted in the first. They are argued to be possibly non-extensional, because they can depict hallucination or mis-perception. (...) The semantics proposed here employs an account of anaphora using discourse referents, a formalized possible worlds semantics for pictorial narratives, and, to model the epistemic consequences of perceptual events, the event alternative construction from dynamic epistemic logic. In intensional examples, the second unit depicting what is seen is analyzed as embedded. It is argued that a semantics for embedding where the attitudinal state of the depicted agent is required to entail the semantic content of the picture attributes too much information to the agent. This is addressed with a model of normal looking, and a semantics for the embedding construction that uses existential quantification over alternatives, rather than universal quantification. (shrink)

Category theory is often treated as an algebraic foundation for mathematics, and the widely known algebraization of ZF set theory in terms of this discipline is referenced as “categorical set theory” or “set theory for category theory”. The method of algebraization used in this theory has not been formulated in terms of universal algebra so far. In current paper, a _universal algebraic_ method, i.e. one formulated in terms of universal algebra, is presented and used for algebraization of a (...) ground mereological system described as “quantitative” (QMS) and of the standard set theories built upon it. The QMS is algebraized by using abelian generalized groups (AGGs) generalizing both abelian groups and Boolean algebras. To algebraize set theory, the AGG are enriched with operators to produce _extensional algebras_ (EA) of Tarskian “Boolean algebras with operators” type. EAs explicate the intuition of set theory’ universes (of discourse). The axiomatic set theory presented in this paper, named _extension theory_, previously went through an intuitive phase of development during its use by the author in computer science projects, where it served as the basis for development of a foundational data science framework and an extensional model of natural languages also outlined here. (shrink)

In this paper, constructions of free algebras corresponding to multiplicative classical linear logic, its affine variant, and their extensions with -contraction () are given. As an application, the cardinality problem of some one-variable linear fragments with -contraction is solved.

This is a thesis in formal semantics. It consists of two parts corresponding to the distinction, due to Richard Montague, between universal grammar and specific semantic theories. The first part concerns universal grammar and is intended to provide a precise and unified conceptual framework within which different theories of formal semantics can be represented and compared. ;The second part of the thesis is concerned with intensional logic, i.e., with the logical analysis of discourse involving so called (...) oblique contexts. These contexts are characterized by the apparent failure of certain classically valid principles of substitutivity. Two kinds of reactions among logicians to the appearance of oblique contexts in natural languages are distinguished: (1) the intensional point of view, according to which oblique contexts are seen as genuine counterexamples to classical logic and to the related semantical principle of extensionality: the principle that the denotation of an expression is a function of the denotations of its parts; and (2) the extensional point of view, according to which the conflict between oblique contexts and classical logic is only apparent. The extensional point of view therefore calls for analyses of oblique contexts that preserve the laws of classical logic and the principle of extensionality. In this thesis, we are concerned with the precise formulation of and comparison between different programs for the formal semantic representation of oblique contexts. In Chapter 5, we are concerned with Church's program of representing oblique contexts within a formal language whose semantics is fully extensional and based on Frege's distinction between sense and denotation. The ambiguity between the "direct" and "indirect" denotation of an expression A is avoided by letting A be replaced in oblique contexts by an expression which denotes A's ordinary sense. We provide a possible-worlds semantics for a version of Church's formal language with the following features: (i) Objectual quantification into oblique constructions is accounted for. The treatment of quantification requires for each entity x an essence of x, by which we mean a sense which determines x in those worlds in which x exists and is undefined in all other worlds. (ii) The variables range over actually existing entities only. It is allowed that entities of certain types are contingent, i.e., the same entity may exist in one world and fail to exist in other worlds. (iii) In order to combine a proper treatment of the cross-world identification of functions with varying domains, partial functions are allowed. (iv) Senses are allowed to be partially defined. For example, the sense of a proper name is undefined in a world in which the denotation of the name does not exist. (v) Senses of functions from objects of type a to objects of type b are identified with functions from senses of objects of type a to senses of objects of type b. In Chapters 6 and 7, we pursue the Russellian Alternative in intensional semantics, where a sense/denotation distinction is avoided. Apparent failures of substitutivity principles for singular terms are explained along the lines of Russell's theory of definite descriptions. Failures of substitutivity of coextensional sentences and predicates are explained by Russell's doctrine that sentences and predicate denote propositions and propositional functions , respectively. Russellian semantics is fully extensional in the sense that the Russellian denotation of a designator is a function of the Russellian denotations of its parts. In Chapter 6, a theory of Russellian propositions is developed within set theory. This theory is then applied in Chapter 7 to the task of providing a set-theoretic semantics for Russellian type theory. (shrink)

Zaionc, M., λ-Definability on free algebras, Annals of Pure and Applied Logic 51 279-300. A λ-language over a simple type structure is considered. There is a natural isomorphism which identifies free algebras with nonempty second-order types. If A is a free algebra determined by the signature SA = [α1,...,αn], then by a type τA we mean τ1,...,τn→0 where τi=0αi→0. It can be seen that closed terms of the type τA reflex constructions in the algebra A. Therefore (...) any term of the type n→τA defines some n-ary mapping in algebra A. The problem is to characterize λ-definable mappings in any free algebra. It is proved that the set of λ-definable operations is the minimal set that contains constant functions and projections and is closed under composition and limited recursion. This result is a generalization of the result of Schwichtenberg and Statman which characterize the λ-definable functions over the natural number type →, i.e algebra [1, 0], as well as of the result of Zaionc for λ-definable word operations over type n→, i.e algebra [1,...,1,0], and of the results about λ-definable tree operations , i.e in algebra [2, 0]. Some of the examples in Section 5 are based on a publication of Zaionc. (shrink)

We give inequational and equational axioms for semirings with a fixed-point operator and formally develop a fragment of the theory of context-free languages. In particular, we show that Greibach’s normal form theorem depends only on a few equational properties of least pre-fixed points in semirings, and eliminations of chain and deletion rules depend on their inequational properties . It follows that these normal form theorems also hold in non-continuous semirings having enough fixed points.

Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with |M| elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M₁, N),...,p(Mh, N), where M₁,...,Mh are fixed "template" models and |N| grows to infinity? In (...) this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density. (shrink)

Medieval Arabic algebra is a good example of an artificial language.Yet despite its abstract, formal structure, its utility was restricted to problem solving. Geometry was the branch of mathematics used for expressing theories. While algebra was an art concerned with finding specific unknown numbers, geometry dealtwith generalmagnitudes.Algebra did possess the generosity needed to raise it to a more theoretical level—in the ninth century Abū Kāmil reinterpreted the algebraic unknown “thing” to prove a general result. But mathematicians had no (...) motive to rework their theories in algebraic form. Because it offered no advantage over geometry, algebra remained a practical art in both the Islamic world and in Europe until the scientific uphevals of the 17th–18th centuries. (shrink)

The paper sets out to offer an alternative to the function/argument approach to the most essential aspects of natural language meanings. That is, we question the assumption that semantic completeness (of, e.g., propositions) or incompleteness (of, e.g., predicates) exactly replicate the corresponding grammatical concepts (of, e.g., sentences and verbs, respectively). We argue that even if one gives up this assumption, it is still possible to keep the compositionality of the semantic interpretation of simple predicate/argument structures. In our opinion, compositionality (...) presupposes that we are able to compare arbitrary meanings in term of information content. This is why our proposal relies on an ‘intrinsically’ type free algebraic semantic theory. The basic entities in our models are neither individuals, nor eventualities, nor their properties, but ‘pieces of evidence’ for believing in the ‘truth’ or ‘existence’ or ‘identity’ of any kind of phenomenon. Our formal language contains a single binary non-associative constructor used for creating structured complex terms representing arbitrary phenomena. We give a finite Hilbert-style axiomatisation and a decision algorithm for the entailment problem of the suggested system. (shrink)

This paper sketches or signals some ideas, results, and proposals connected with the theoretical issues related to the categorial approach to language which originated from the first author and which form the basis for further research by the second author. The main aims are the following: 1) to bring into common use some Polish ideas concerned with classical categorial grammar; 2) to take into consideration a universal and simultaneously formal-logical perspective; 3) to consider Peirce's well-known differentiation of (...) linguistic objects, i.e. their twofold ontological status as tokens and types and, according to this, to consider the biaspectual formalization of language dealing with the two main orientations in the controversy between nominalism and Platonism; 4) to characterize language according to Frege's ontological canons, according to which each expression of language corresponds to its denotation. All of these factors make possible not only the syntactic characterization of language but also the introduction of syntactic and semantic definitions of a true expression and its denotation. These notions correspond here to the old classical, but not necessarily standard, understanding of semantic concepts. The paper is divided into four sections: the first contains a brief characterization of the categorial approach to syntax; the second presents two strains of this approach; the third touches on certain general semantic issues connected with the notion of truth; and the last gives some final remarks. (shrink)

In this paper, we propose an extension of free pregroups with lower bounds on sets of pregroup elements. Pregroup grammars based on such pregroups provide a kind of an algebraic counterpart to universal quantification over type-variables. In particular, we show how our pregroup extensions can be used for pregroup grammars expressing natural-language coordination and extraction.

Hypersequents are a natural generalization of ordinary sequents which turn out to be a very suitable tool for presenting cut-free Gentzent-type formulations for diverse logics. In this paper, an alternative way of formulating hypersequent calculi (by introducing meta-variables for formulas, sequents and hypersequents in the object language) is presented. A suitable category of hypersequent calculi with their morphisms is defined and both types of fibring (constrained and unconstrained) are introduced. The introduced morphisms induce a novel notion of translation (...) between logics which preserves metaproperties in a strong sense. Finally, some preservation features are explored. (shrink)

Some algebraic structures of the set of all effects are investigated and summarized in the notion of a(weak) orthoalgebra. It is shown that these structures can be embedded in a natural way in lattices, via the so-calledMacNeille completion. These structures serve as a model ofparaconsistent quantum logic, orthologic, andorthomodular quantum logic.

In this article I deal with the notion of observation, from a phenomenologically motivated point of view, and its representation mainly by means of the formal language of quantum mechanics. In doing so, I have taken the notion of observation in two diverse contexts. In one context as a notion related with objects of a logical-mathematical theory taken as registered facts of phenomenological perception ( Wahrnehmung ) inasmuch as this phenomenological idea can also be linked with a process (...) of measurement on the quantum-mechanical level. In another context I have taken it as connected with a notion of temporal constitution basically as it is described in E. Husserl’s texts on the phenomenology of temporal consciousness. Given that mathematical objects as formal-ontological objects can be thought of as abstractions of perceptual objects by means of categorial intuition, the question is whether and under what theoretical assumptions we can, in principle, include quantum objects in abstraction in the class of formal-ontological objects and thus inquire on the limits of their description within a formal-axiomatical theory. On the one hand, I derive an irreducibility on the level of individuals taken in formal representation as syntactical atoms-substrates without any further content and on the other hand a transcendental subjectivity of consciousness objectified as a self-constituted temporal unity upon which it is ultimately grounded the possibility of generation of an abstract predicative universe of discourse. (shrink)

. The deep structural properties of a quantum information theoretic approach to formal languages and universal computation, as well as those of the topology problem of defining the presentation of the Mapping Class Group of a smooth, compact manifold are shown to be grounded in the common categorical features of the two problems.

Mereotopology is an extension of mereology with some relations of topological nature like contact. An algebraic counterpart of mereotopology is the notion of contact algebra which is a Boolean algebra whose elements are considered to denote spatial regions, extended with a binary relation of contact between regions. Although the language of contact algebra is quite expressive to define many useful mereological relations and mereotopological relations, there are, however, some interesting mereotopological relations which are not definable in it. Such are, (...) for instance, the relation of n-ary contact, internal connectedness and some others. To overcome this disadvantage, we introduce a generalisation of contact algebra, replacing the contact with a binary relation between finite sets of regions and a region, satisfying some formal properties of Tarski consequence relation. The obtained system is called sequent algebra, considered as an algebraic counterpart of a new mereotopology. We develop the topological representation theory for sequent algebras showing in this way certain correspondence between point-free and point-based models of space. As a by-product, we show how one logical relation in nature notion, Tarski consequence relation, may have also certain spatial meaning. (shrink)

• languages as sets of strings and early transformational grammar • interpreted languages as sets of string-meaning pairs • Montague in ‘Universal Grammar’: There is in my opinion no important theoretical difference between natural languages and the artificial languages of logicians; indeed I consider it possible to comprehend the syntax and semantics of both kinds of languages within a single natural and mathematically precise theory.

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)

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.

In this paper I introduce a broader context, and sketch an integrated account with the purpose of examining the significance of Neurath’s attention to logic in early works and subsequent positions. The specific attention to algebraic logic is important in integrating his own interest in mathematics and combining, since Leibniz, the ideals of a universal language and of a calculus of reasoning. The interest in universal languages constitutes a much broader, so-called tradition of pasigraphy that extended beyond (...) philosophical projects. I argue that Neurath’s works can be embedded in a richer intellectual landscape that includes developments in logic and their local reception in Vienna, and that his attention to logic developed a sustained symbolic standpoint – with semiotic and typographic expressions –; that specific aspects of the work in algebraic logic became a standard and a resource in subsequent work often thought independent, while its value was steadily challenged by the separate goal of empirical theorizing and practical application in social domains – including in the areas of economics, history and visual communication –; that, in particular, the presentation of systems of algebraic logic by Neurath’s sources such as Stanley Jevons and Schröder was not isolated from discussions of political economy; and finally that some of his positions in matters of language, unity and epistemology in the articulation of logical empiricism and its debates are better understood in terms of shared but diversified acquaintance with pasigraphy, formal standards and logical projects. (shrink)

We carry out a systematic study of decidability for theories of real vector spaces, inner product spaces, and Hilbert spaces and of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list turn out to be decidable while the theories for list are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic.We find that the purely (...) class='Hi'>universal and purely existential fragments of the theory of normed spaces are decidable, as is the ∀∃ fragment of the theory of metric spaces. These results are sharp of their type: reductions of Hilbertʼs 10th problem show that the ∃∀ fragments for metric and normed spaces and the ∀∃ fragment for normed spaces are all undecidable. (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)

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)

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)

What makes our utterances mean what they do? In this work I formulate and justify a structural constraint on possible answers to this key question in the philosophy of language, and I show that accepting this constraint leads naturally to the adoption of an algebraic formalization of truth-theoretic semantics. I develop such a formalization, and show that applying algebraic methodology to the theory of meaning yields important insights into the nature of language. ;The constraint I propose is, roughly, (...) this: the meaning of an utterance of a natural language sentence is derived from the place of that sentence within a system that includes other sentences, and is structured in virtue of primitive semantic facts about complete sentences. This constraint calls for a formal semantics program where the meaning of natural language sentences is represented by an appropriate assignment of the elements of an algebraic structure to sentences, an assignment that represents facts concerning complete sentences. I call the above constraint 'The Algebraic Thesis', and the corresponding formal semantics program 'Algebraic Semantics.' ;I introduce AT by carving it out of the holistic views of language of Quine and Davidson, and I show that it is independent of other important features of these philosophers' views. I then argue for AT, taking into account recent work by Brandom, Dummett, Fodor and Lepore, Gaifman and Perry. In developing Algebraic Semantics I present structures of two basic types: Boolean algebras and cylindric algebras; these structures are construed in the context of AT in a novel way: they are treated as applying to classes of sentences as numbers apply to physical objects in measurement. Applying algebraic methodology to formal semantics and to the theory of meaning, I develop these results: ; An account of the semantics of necessity and possibility that avoids both Quine's dismissal of these notions and their reduction by David Lewis to quantification over possible worlds; ; The application of the model-theoretic notion of expansion to capture the process of our learning progressively more of the meaning of expressions in our first languages. (shrink)

ABSTRACTTo some extent, the early twentieth century revival of universal languages was the work of logicians and mathematicians. Pioneers of modern logic such as Frege, Russell and Peano wanted to overcome the diversity and deficiencies of natural languages. Through the rigour of formal logic, they aimed at providing scientific thinking with a reliable medium free from the ambiguity and inconsistencies of ordinary language. This article shows some interconnections between modern logic and the search for a common (...) tongue that would unite scientists and people of all nations. The French mathematician and philosopher Louis Couturat is a key figure in understanding the interplay between these two movements. Through his work in composing the Ido language as an alternative to Esperanto, Couturat gave a new life to the Leibnizian idea of a universal characteristics. In addition, his multifaceted work provides a valuable insight into some political implications of early analytic philosophy. (shrink)

This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

Gödel logic is the extension of intuitionistic logic by the linearity axiom. Symmetric Gödel logic is a logical system, the language of which is an enrichment of the language of Gödel logic with their dual logical connectives. Symmetric Gödel logic is the extension of symmetric intuitionistic logic. The proof-intuitionistic calculus, the language of which is an enrichment of the language of intuitionistic logic by modal operator was investigated by Kuznetsov and Muravitsky. Bimodal symmetric Gödel logic is (...) a logical system, the language of which is an enrichment of the language of Gödel logic with their dual logical connectives and two modal operators. Bimodal symmetric Gödel logic is embedded into an extension of Gödel–Löb logic, the language of which contains disjunction, conjunction, negation and two modal operators. The variety of bimodal symmetric Gödel algebras, that represent the algebraic counterparts of bimodal symmetric Gödel logic, is investigated. Description of free algebras and characterization of projective algebras in the variety of bimodal symmetric Gödel algebras is given. All finitely generated projective bimodal symmetric Gödel algebras are infinite, while finitely generated projective symmetric Gödel algebras are finite. (shrink)

First order formulas in a relational signature can be considered as operations on the relations of an underlying set, giving rise to multisorted algebras we call first order algebras. We present universal axioms so that an algebra satisfies the axioms iff it embeds into a first order algebra. Importantly, our argument is modular and also works for, e.g., the positive existential algebras and the quantifier-free algebras. We also explain the relationship to theories, and indicate how to add in (...) function symbols. (shrink)

In the first section of this paper I present a well known objection to meaning holism, according to which holism is inconsistent with natural language being learnable. Then I show that the objection fails if language acquisition includes stages of partial grasp of the meaning of at least some expressions, and I argue that standard model theoretic semantics cannot fully capture such stages. In the second section the above claims are supported through a review of current research into (...) language acquisition. Finally, in the third section it is argued that contemporary algebraic logical systems consist in a superior formal vehicle through which to capture stages of partial grasp of meaning; this claim is supported by concrete examples. (shrink)

We introduce new algebraic and topological semantics for inquisitive logic. The algebraic semantics is based on special Heyting algebras, which we call inquisitive algebras, with propositional valuations ranging over only the ¬¬-fixpoints of the algebra. We show how inquisitive algebras arise from Boolean algebras: for a given Boolean algebra B, we define its inquisitive extension H(B) and prove that H(B) is the unique inquisitive algebra having B as its algebra of ¬¬-fixpoints. We also show that inquisitive algebras determine Medvedev’s logic (...) of finite problems. In addition to the algebraic characterization of H(B), we give a topological characterization of H(B) in terms of the recently introduced choice-free duality for Boolean algebras using so-called upper Vietoris spaces (UV-spaces). In particular, while a Boolean algebra B is realized as the Boolean algebra of compact regular open elements of a UV-space dual to B, we show that H(B) is realized as the algebra of compact open elements of this space. This connection yields a new topological semantics for inquisitive logic. (shrink)

My aim in this note is to shed light on ways of interpreting Kant’s Formula of Universal Law (FUL), by looking at relevant similarities and differences between Pauline Kleingeld and Mark Timmons. I identify both their readings as a formal interpretation of Kant’s FUL, in contrast to the substantive interpretations that favor a robust conception of rational agency as a necessary requirement for moral deliberation. I highlight the benefits that arise from Kleingled’s interpretation in showing the immediacy involved (...) in the volitional self-contradiction when universalizing a maxim. Alongside Timmons, I address a question as to whether Kleingeld’s interpretation is completely free from at least a minimal set of assumptions about practical deliberation more broadly, that seem to play a role in generating the volitational self-contradiction she is defending. I close by raising some skeptical worries about the capacity of this kind of contradiction to translate into a moral judgment triggering action. (shrink)