Search

Arguments facilitate humans to deliver their ideas. The outcome of the discussion heavily relies on the validity of the argument. If an argument is well-composed, it is more effective to grasp the core idea behind the argument. To grade the argument, machines can be utilized by decomposing into semantic label components. In natural language processing, multiple language models are available to perform this task. It is divided into context-free and contextual models. The majority of previous studies used hand-crafted features to perform argument component classification, while state of the art language models utilize machine learning. The majority of these language models ignore the context in an argument. This research paper aims to analyze whether by including the context in the classification process may improve the accuracy of the language model which will enhance the argumentation mining process as well. The same document corpus is fed into several language models. Word2Vec and GLoVe represent the context free models, while BERT and ELMo as context sensitive language models. Accuracy and time from each model are then compared to determine the importance of context. The result shows that contextual language models are proven to be able to boost classification accuracy by approximately 20%. However, time comes as a cost where contextual models require longer training and prediction time. The benefit from the increase in accuracy outweighs the burden of time. Thus, as a contextual task, argumentation mining is suggested to use contextual model where context must be included to achieve promising results.

Computing with molecules is at the center of complex natural phenomena, where the information contained in ordered sequences of molecules is used to implement functionalities of synthesized materials or to interpret the environment, as in Biology. This uses large macromolecules and the hindsight of billions of years of natural evolution. But, can one implement computation with small molecules? If so, at what levels in the hierarchy of computing complexity? We review here recent work in this area establishing that all physically realizable computing automata, from Finite Automata (FA) (such as logic gates) to the Linearly Bound Automaton (LBA, a Turing Machine with a finite tape) can be represented/assembled/built in the laboratory using oscillatory chemical reactions. We examine and discuss in depth the fundamental issues involved in this form of computation exclusively done by molecules. We illustrate their implementation with the example of a programmable finite tape Turing machine which using the Belousov-Zhabotinsky oscillatory chemistry is capable of recognizing words in a Context Sensitive Language and rejecting words outside the language. We offer a new interpretation of the recognition of a sequence of chemicals representing words in the machine's language as an illustration of the “Maximum Entropy Production Principle” and concluding that word recognition by the Belousov-Zhabotinsky Turing machine is equivalent to extremal entropy production by the automaton. We end by offering some suggestions to apply the above to problems in computing, polymerization chemistry, and other fields of science.

We investigate the complexity of deciding whether a given regular language can be expressed by a deterministic regular expression. Our main technical result shows that deciding if the language of a given regular expression (or, non-deterministic finite automaton) can be defined by a deterministic regular expression is PSPACE-complete. The problem becomes EXPSPACE-complete if the input language is represented as a regular expression with counters and NL-hard if the input language is given by a minimal deterministic finite automaton.

The interest in language evolution by various disciplines, such as linguistics, computer science, biology, etc., makes language evolution models an active research topic and many models have been defined in the last decade. In this work, an overview of computational methods and grammars in language evolution models is given. It aims to introduce readers to the main concepts and the current approaches in language evolution research. Some of the language evolution models, developed during the decade 2003---2012, have been described and classified considering both the grammatical representation (context-free, attribute, Christiansen, fluid construction, or universal grammar) and the computational methods (agent-based, evolutionary computation-based or game theoretic). Finally, an analysis of the surveyed models has been carried out to evaluate their possible extension towards multimodal language evolution.

Using string kernels, languages can be represented as hyperplanes in a high dimensional feature space. We discuss the language-theoretic properties of this formalism with particular reference to the implicit feature maps defined by string kernels, considering the expressive power of the formalism, its closure properties and its relationship to other formalisms. We present a new family of grammatical inference algorithms based on this idea. We demonstrate that some mildly context-sensitive languages can be represented in this way and that it is possible to efficiently learn these using kernel PCA. We experimentally demonstrate the effectiveness of this approach on some standard examples of context-sensitive languages using small synthetic data sets. ispartof: Machine Learning vol:82 issue:3 pages:351-373 status: published

We give a new discretization of behaviors of timed automata. In this discretization, timed languages are represented as sets of words containing action symbols, a clock tick symbol 1, and two delay symbols δ − (negative delay) and δ + (positive delay). Unlike the region construction, our discretization commutes with intersection. We show that discretizations of timed automata are, in general, context-sensitive languages over Σ ∪ {1,δ + ,δ −, and give a class of automata that equals the class of languages that are discretizations of timed automata, and show that their emptiness problem is decidable.

In this paper we present a simple model of communication. We assume that communication takes place between two agents. Each agent has a private and subjective knowledge state. The knowledge of both agents is partial, finite, and represented in a computational way. We investigate how ideas can be transferred from one agent to the other one, in spite of the subjective nature of the knowledge of both participants. Posing the problem in this way, it can be seen that mechanisms for context-dependent interpretation are a prerequisite for succesfull communication.

Comparative studies of language are difficult because few language precursors are recognized. In this paper we propose a framework for designing experiments that test for structural and semantic patterns indicative of simple or complex grammars as originally described by Chomsky. We argue that a key issue is whether animals can recognize full recursion, which is the hallmark of context-free grammar. We discuss limitations of recent experiments that have attempted to address this issue, and point out that experiments aimed at detecting patterns that follow a Fibonacci series have advantages over other artificial context-free grammars. We also argue that experiments using complex sequences of behaviors could, in principle, provide evidence for fully recursive thought. Some of these ideas could also be approached using artificial life simulations, which have the potential to reveal the types of evolutionary transitions that could occur over time. Because the framework we propose has specific memory and computational requirements, future experiments could target candidate genes with the goal of revealing the genetic underpinnings of complex cognition.

In recent years, the study of formal semantics and formal pragmatics has grown tremendously showing that core aspects of language meaning can be explained by a few principles. These principles are grounded in the logic that is behind - and tightly intertwined with - the grammar of human language. In this book, some of the most prominent figures in linguistics, including Noam Chomsky and Barbara H. Partee, offer new insights into the nature of linguistic meaning and pave the way for the further development of formal semantics and formal pragmatics. Each chapter investigates various dimensions in which the logical nature of human language manifests itself within a language and/or across languages. Phenomena like bare plurals, free choice items, scalar implicatures, intervention effects, and logical operators are investigated in depth and at times cross-linguistically and/or experimentally. This volume will be of interest to scholars working within the fields of semantics, pragmatics, language acquisition and psycholinguistics.

The following article is concerned with the problem of language diversity within the framework of Radical Minimalism (Krivochen 2011, 2012). How can the diversity and variation of languages be explained? For Noam Chomsky, language faculty in the narrow sense (FLN) is nothing but an “‘organ of the body,’ along with other cognitive systems. Our analysis of human language builds on Chomsky’s (1995, 2005, 2010) minimalist assumption that the design of language is grounded in conceptual necessity. Adopting this idea, we expect to find three factors that interact to determine (I-) languages attained: genetic endowment (the topic of Universal Grammar), experience, and principles that are language- or even organism-independent.” (Chomsky 2005:1). In the present article we provide some ideas about how generative research based on Radical Minimalism can contribute on a par with the typology of languages to a more profound and sound exploration of language variation. The scope of the paper is to compare the distribution of adverbs within the three domains of the clause in Czech and German. The aim of this paper is to show that the feature-based theory of adverb licensing is not able to handle the problem of adverb order variation. Instead, a more parsimonious approach based on the Theory of Radical Minimalism will be chosen. The paper is organized as follows: After some remarks on the role of Universal Grammar, Variation and Typology in section 1, section 2 introduces the theoretical background by introducing the principles and the core of Radical Minimalism, e.g. free unbounded merge, asymmetric c-command and the restrictions within the clause structure composition. In section 3, the distribution of adverbs in the middle field is discussed for Czech and German. In the last part, we introduce the so-called Late Adjunction Hypothesis that results in similar effects to the Early Spell-Out model argued for in our paper.

Membrane computing is a branch of natural computing which abstracts computing models from the structure and the functioning of the living cell. The main ingredients of membrane systems, called P systems, are (i) the membrane structure, which consists of a hierarchical arrangements of membranes which delimit compartments where (ii) multisets of symbols, called objects, evolve according to (iii) sets of rules which are localised and associated with compartments. By using the rules in a nondeterministic/deterministic maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from one membrane to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. Membrane systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology gives way to a practical bio-realization. In this paper we survey some interesting and fundamental complexity issues such as universality vs. nonuniversality, determinism vs. nondeterminism, membrane and alphabet size hierarchies, characterizations of context-sensitive languages and other language classes and various notions of parallelism.

Short version of hal-00149109. The original publication is available at www.springerlink.com.; International audience; Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural family of canonical infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another family of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-family of linearly bounded graphs.

International audience; In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs.

International audience; Decidability of non-structural subtype entailment is a long-standing open problem in programming language theory. In this paper, we apply automata theoretic methods to characterize the problem equivalently by using regular expressions and word equations. This characterization induces new results on non-structural subtype entailment, constitutes a promising starting point for further investigations on decidability, and explains for the first time why the problem is so difficult. The difficulty is caused by implicit word equations that we make explicit.

International audience; This paper shows that the traces of rational graphs coincide with the context-sensitive languages.; Cet article établit que les traces des graphes rationnels sont les langages contextuels.

Mildly context sensitive grammar formalisms such as multi-component TAGs and linear context free rewrite systems have been introduced to capture the full complexity of natural languages. We show that, in a formal sense, Old Georgian can be taken to provide an example of a non-semilinear language. This implies that none of the aforementioned grammar formalisms is strong enough to generate this language.

International Conference on Pattern Recognition (ICPR), 1996, Viena (Austria), Automatic generation of models from a set of positive and negative samples and a-priori knowledge (if available) is a crucial issue for pattern recognition applications. Grammatical inference can play an important role in this issue since it can be used to generate the set of model classes, where each class consists on the rules to generate the models. In this paper we present the process of learning context dependent bidimensional objects from outdoors images as context sensitive languages. We show how the process is conceived to overcome the problem of generalizing rules based on a set of samples which have small differences due to noisy pixels. The learned models can be used to identify objects in outdoors images irrespectively of their size and partial occlusions. Some results of the inference procedure are shown in the paper.

In this paper the context-splittable normal form for rewriting systems defining Church–Rosser languages is introduced. Context-splittable rewriting rules look like rules of context-sensitive grammars with swapped sides. To be more precise, they have the form uvw→uxw with u,v,w being words, v being nonempty and x being a single letter or the empty word. It is proved that this normal form can be achieved for each Church–Rosser language and that the construction is effective. Some interesting consequences of this characterization are given, too.

If G is a grammar such that in each non-context-free rule of G, the right side contains a string of terminals longer than any terminal string appearing between two nonterminals in the left side, then the language generated by G is context free. Six previous results follow as corollaries of this theorem.

In 1988 the Church–Rosser languages were introduced by McNaughton et al. as those languages that are recognized by finite, length-reducing and confluent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by other types of string-rewriting systems. To honour Robert McNaughton's original contribution we call the resulting families of languages McNaughton families. Here it is shown that the concept of McNaughton families is as powerful as the notion of Turing machine or the notion of phrase-structure grammar. We investigate the relationships between the various McNaughton families, obtaining an extensive hierarchy of classes that includes many well-known language and complexity classes as well as some new classes. Further, we consider some closure and non-closure properties for those McNaughton families that are contained in the class of context-free languages, and we address the complexity of the fixed and the general membership problems for these families.

In this paper we propose a Chomsky-Schutzenberger type characterization of k-poly-slender context-free languages, as the homomorphical image of an intersection of a Dyck language and a (2k + 1)-poly-slender regular language. A stronger result is provided, namely the homomorphism and the Dyck language are determined irrespective of the given poly-slender context-free language, when considering the family of all poly-slender context-free languages. A similar characterization is obtained for Parikh slender context-free languages.

We define a density of a given language S in a given language L as an asymptotic probability that a randomly and uniformly chosen word of length n from L belongs to S. There are languages for which densities do not exist. We show that a problem of checking whether one regular language has a density in another regular language is decidable.

A connection is established between formal language theory and mathematical analysis by associating the symbols of strings of a language with the digits of expansions of points in the unit interval. A language is made to correspond to a particular subset of the unit interval, and the dimension of a language is defined as the Hausdorff dimension of this subset. It is shown that the dimension of a language is less than or equal to its channel capacity, and it is shown that a statement involving the dimension of a language can be added to a list of criteria developed by Brainerd and Knode (1972) for determining that a language is not recognizable by a finite automaton.

This paper continues the investigation into k-parallel rewritting begun in (Gonczarowski/Shamir, 1985) and (Gonczarowski/Warmuth, 1985). This rewritting mechanism is a generalization of context-free rewriting; instead of applying a single production (or, alternatively, arbitrarily many productions) at each derivation step, exactly k productions are applied. In the works mentioned above, polynomial dynamic programming algorithms were presented which require constant k and propagating grammars. We solve the various membership problems left open in (Gonczarowski/Warmuth, 1985), for arbitrary grammars, using Scheduling Theory. We develop various kinds of pumping, obtaining bounds on the sizes of k-derivations and k-derivation forests. A polynomial dynamic programming membership algorithm is presented for arbitrary (i.e., possibly nonpropagating) grammars, for fixed k. If k is a variable of the problem, then membership is in NP and, hence, by (Gonczarowski/Warmuth, 1985), NP-complete. For unary alphabets, the latter problem is polynomial. Similarly, membership is polynomial in the size of k if only k is variable.

Given a regular language L we construct a pure context-free grammar G such that L is pure context-free if and only if L = L(G). Since the problem “L = L(G)?” is decidable for a regular language L and a pure context-free grammar G, it is decidable whether a regular language is pure context-free.

The definitions of a piecewise deterministic zero Lindenmayer (PWD0L) scheme and system are given, and dynamical properties of such systems are introduced. Harrison (1994) showed that given an arbitrary finite alphabet A, the emptiness problem is undecidable for the class of languages which are intersections of a D0L language and a context-sensitive language. This result is used to prove that many dynamical properties of PWD0L systems(such as finiteness, periodicity, etc) are in general undecidable over a two-member context-sensitive partition of A ∗ . The idea of a morphic equivalence relation on A ∗ (A is finite) is defined and the idea of a finite morphic refinement is introduced. Harrison (1994) showed that every regular language and its complement is refined by a finite partition which is induced by a morphic congruence. Using this theorem, it is shown that dynamical properties such as finiteness and periodicity are in general decidable for RWD0L systems (i.e. a PWD0L system over a finite partition of A ∗ made up of all regular languages).

Multi-axiom grammars (MAG) are alternatives to single-axiom context free grammars (CFG) and all-axiom algebraic grammars (AG) for programming language specification. Neither phrase recognition nor algebraic mechanisms for language processing are supported by CFGs. AGs support algebraic mechanisms for language processing but specify a smaller class of languages. MAGs avoid these limitations. This paper describes a new parsing algorithm developed on this basis which recognizes any phrase in the language. Moreover, it does so by distributing the parsing task among a collection of smaller parsers which handle well-defined layers of the language in a piping manner. These language-layers are determined by the algebraic properties of the MAGs and are described in the paper. Basic definitions are given for multi-axiom grammar and language as well as for algebraic notions of subgrammar, primitive subgrammar, quotient grammar, and grammar/language layer. Algorithms are described to stratify a programming language into a hierarchy of layers, to construct parsers for each layer analogous to LR construction, and to accomplish the overall task of multi-layered parsing in pipeline fashion based on a tokenization which occurs between the language layers. This pipeline parallel process is a model for high speed, left-to-right language translation.

It is known that nonregular languages can be accepted by finite state probabilistic automata. For many years it was not known whether a finite state probabilistic automaton existed that would accept a context sensitive language that is not context free. Such a finite state probabilistic automaton is constructed.

In this paper we formulate the problem, and start an investigation of the complexity of recognizing fault tolerance of syntax, or in other words, of formal language. The research on this problem is motivated by the growing interest to methods of estimation of quality of software systems – a user language is a part of such systems, and its reliability towards syntactic errors is a feature of its quality. We analyse the computational complexity of recognizing one type of such fault tolerance towards a fixed number of errors: a language is fault-tolerant iff any set of replacements of characters within the fixed number in any string in the language produces a string not in the language; a grammar defining the language produces a string not in the language; a grammar defining the language (the syntax) is supposed to be given as input. The property of this kind of fault tolerance is shown to be algorithmically undecidable even for context-free languages. But for nondeterministic finite-automaton languages it is shown to be recognizable in time polynomial in the size of the automaton representing an input language and exponential in the number of errors. In the concluding part of the paper wider views on the problem of fault tolerance of syntax are briefly discussed.

This paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. It demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. In addition, it proves analogous results for unordered scattered context grammars. Some consequences of these results are derived and open problems formulated.

Random context grammars belong to the class of context-free grammars with regulated rewriting. Their productions depend on context that may be randomly distributed in a sentential form. Context is classified as either permitting or forbidding, where permitting context enables the application of a production and forbidding context inhibits it. We concentrate on non-erasing grammars that use forbidding context only. We show that they are strictly weaker than the non-erasing random context grammars and prove a shrinking lemma for their languages.

The class of growing context-sensitive languages (GCSL) was proposed as a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Growing context-sensitive languages and their deterministic counterpart called Church–Rosser languages (CRL) complement the Chomsky hierarchy in a natural way, as the classes filling the gap between context-free languages and context-sensitive languages. They possess characterizations by a natural machine model, length-reducing two-pushdown automata (lrTPDA). We introduce a lower bound technique for lrTPDAs. Using this technique, we prove the conjecture of McNaughton, Narendran and Otto that the set of palindromes is not in CRL. As a consequence we obtain that CFL∩coCFL as well as UCFL∩coUCFL are not included in CRL, where UCFL denotes the class of unambiguous context-free languages; this solves an open problem posed by Beaudry, Holzer, Niemann and Otto. Another corollary is that CRL is a strict subset of GCSL∩coGCSL.

The structure generating function of a language enumerates the number of distinct words contained in the language with respect to their length. Given any language generated unambiguously by a grammar with context-free control language or generated n-unambiguously by a state grammar with context-free control language or generated unambiguously by a tuple grammar with contextfree control language, a method is described which yields a system of equations, whose unique solution is the structure generating function.