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.

This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.

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 extend to spiking neural P systems a notion investigated in the “standard” membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by “marking” it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language. In all proofs we try to keep the size of used systems (number of neurons, of rules in each neuron, of spikes consumed or removed by rules) as small as possible.

We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the chop of two regular languages. We also prove non-closure of that language family under Boolean operations and closure under reversal. Further, the representation of a regular language as the chop of two regular expressions can be exponentially more succinct than its regular expression. By considering the chop of two linear context-free languages we already obtain language families that have non-semi-decidable problems such as emptiness or finiteness.

In this note we present a simple condition upon which a formal grammar produces a context-free language. Fil: Badano, Mariana. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina Fil: Vaggione, Diego Jose. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina

For a given finitely generated group [Formula: see text], the type of languages that are accepted by [Formula: see text]-automata is determined by the word problem of [Formula: see text] for most of the classical types of languages. We observe that the only exceptions are the families of context-sensitive and recursive languages. Thus, in general, to ensure that the language accepted by a [Formula: see text]-automaton is in the same classical family of languages as the word problem of [Formula: see text], some restriction must be imposed on the [Formula: see text]-automaton. We show that restricting to [Formula: see text]-automata without [Formula: see text]-transitions is sufficient for this purpose. We then define the pullback of two [Formula: see text]-automata and use this construction to study the closure properties of the family of languages accepted by [Formula: see text]-automata without [Formula: see text]-transitions. As a further consequence, when [Formula: see text] is the product of two groups, we give a characterization of the family of languages accepted by [Formula: see text]-automata in terms of the families of languages accepted by [Formula: see text]- and [Formula: see text]-automata. We also give a construction of a grammar for the language accepted by an arbitrary [Formula: see text]-automaton and show how to get a context-sensitive grammar when [Formula: see text] is finitely generated with a context-sensitive word problem and the [Formula: see text]-automaton is without [Formula: see text]-transitions.

The current named entity recognition (NER) is mainly based on joint convolution or recurrent neural network. In order to achieve high performance, these networks need to provide a large amount of training data in the form of feature engineering corpus and lexicons. Chinese NER is very challenging because of the high contextual relevance of Chinese characters, that is, Chinese characters and phrases may have many possible meanings in different contexts. To this end, we propose a model that leverages a pre-trained and bi-directional encoder representations-from-transformers language model and a joint bi-directional long short-term memory (Bi-LSTM) and conditional random fields (CRF) model for Chinese NER. The underlying network layer embeds Chinese characters and outputs character-level representations. The output is then fed into a bidirectional long short-term memory to capture contextual sequence information. The top layer of the proposed model is CRF, which is used to take into account the dependencies of adjacent tags and jointly decode the optimal chain of tags. A series of extensive experiments were conducted to research the useful improvements of the proposed neural network architecture on different datasets without relying heavily on handcrafted features and domain-specific knowledge. Experimental results show that the proposed model is effective, and character-level representation is of great significance for Chinese NER tasks. In addition, through this work, we have composed a new informal conversation message corpus called the autonomous bus information inquiry dataset, and compared to the advanced baseline, our method has been significantly improved.

It is Chomsky’s great achievement that he instituted rationalism such as linguistic creativity and innateness in linguistics. Based on uniformity and rapidity of language acquisition (or growth), he established species-specific innate Universal Grammar (UG), the faculty of language. However, Chomsky proposed that UG results from mutations. This mutation theory, in relevance to UG consisting of external and internal, or free merge, cannot provide an adequate explanation for language acquisition. Nor is Chomsky’s merge-mutation theory powerful enough to explain abstract structures such as phonological and syntactic structures of English as well as other languages. More importantly, this theory would be repeatedly refuted by many biologists’ claim that mutations hardly add new, complex and specified information. To these fallacies of Chomsky’s merge-mutation theory, an adequate answer is “intelligent design” consisting of irreducible and specified complexity. Intelligent design proposes that human beings are designed with some species-specific biological endowments different from those of other animals, which in turn have their own pre-programmed behaviors. Only human beings are designed with UG as we can see by the numerous cases that Chomsky suggested.

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 forbidding and enforcing paradigm was introduced by Ehrenfeucht and Rozenberg as a way to define families of languages based on two sets of boundary conditions. Later, a variant of this paradigm was considered where an fe-system defines a single language. We investigate this variant further by studying fe-systems in which both the forbidding and enforcing sets are finite and show that they define regular languages. We prove that the class of languages defined by finite fe-systems is strictly between the strictly locally testable languages and the class of locally testable languages.

A Szilard language is a language theoretical tool used to describe the derivation process in a formal grammar or grammar system. We investigate computational resources used by (alternating) Turing machines to accept Szilard languages of Chomsky grammars, regulated grammars and grammar systems. The results are related to the circuit complexity classes NC1 and NC2. The paper is a survey of the most important complexity results in the field, but it also brings several new insights into the parallel complexity of Szilard languages of grammar systems. We focus on parallel communicating grammar systems (PCGSs) with context-free components, and we prove that the class of Szilard languages of centralized (returning or non-returning) PCGSs is included in NC1.

Language sciences have long maintained a close and supposedly necessary coupling between the infinite productivity of the human language faculty and recursive grammars. Because of the formal equivalence between recursion and non-recursive iteration; recursion, in the technical sense, is never a necessary component of a generative grammar. Contrary to some assertions this equivalence extends to both center-embedded relative clauses and hierarchical parse trees. Inspection of language usage suggests that recursive rule components in fact contribute very little, and likely nothing significant, to linguistic creativity. Further than this, if the productivity of human language is considered as not rigidly bound, but not infinite, then the need for any sort of iteration in generative grammars vanishes and can be replaced with a Non-iterative Explicit Alternatives Rule grammar. The knock-on effects of dispensing with recursive (or any iterative) grammar components are: that language diversity can simply be based on rule and lexicon combinatorics with no potentially infinite dimensions derived from recursive or iterative components of rules; the oddity of a vast, multiply-infinite competence set of `grammatical but unacceptable' productions is gone; and the development of a language faculty based on rules that eschew iterative rule components avoids any need for explaining `special' mechanisms. On the broader front of searching for the mechanisms of mind, our analysis can be similarly applied to the proposals for a recursive basis for mind as an explanation for humanity's great leap forward.

HighlightsLanguage composition has not obtained enough attention, is still not well-understood, and associated terminology is confusing.OO techniques and concepts are powerful enough to implement all types of language compositions.Several small examples of different types of language composition are shown using easy to understand DSLs. In this paper, it is shown that inheritance, a core concept from object-oriented programming, is a possible solution for realizing composition of computer languages. Language composability is a property of language descriptions, which can be further classified into informal (language syntax and semantics are hard-coded in compiler/interpreter) and formal language descriptions (syntax and semantics are formally specified with one of several formal methods for language definition). However, language composition is much easier to achieve with declarative formal language descriptions into which the notion of inheritance is introduced. Multiple attribute grammar inheritance, as implemented in the language implementation system LISA, can assist in realizing all of the different types of language compositions identified in Erdweg et al. (2012). Different examples are given throughout the paper using an easy to understand domain-specific language that describes simple robot movement.

grammars are neglected resources in language processor implementations. In the most favourable case they are used to format first-class program representations. In the worst case they serve as a temporary interface between compiler phases. But they can enable so much more âAe certainly in teaching.In this presentation we report on a long-running experiment (>5 y.) to develop a language interpreter that is maximally supported by an extensible (abstract) grammar. The context of the experiment is an advanced course on Programming Language Engineering (http://soft.vub.ac.be/PLE). The reference language is a simplified variation on Scheme, so: no objects in this story.In this course abstract grammars serve as backbone for material ranging from formal language specifications to low-level implementation with an eye for optimisation. In order to do so, we require that an instance of an abstract grammar be first class, and that all of its attributes should be setable and getable from within any program that is associated with this instance. Depending on the level of detail at which its semantics are captured in the abstract grammar, this regulates the depth at which the program can reflect over its specification. Nothing new here, this is lisp and s-expressions, only more so.A central idea to this notion of a rich abstract grammar, is a unified memory model. At a basic level no distinction is made between stacks, heaps, frames c and if the interpretation strategy is based on a transformation into continuation passing style (as is the case here), structures resulting from lambda-lifting should be considered. However, the most interesting extensions to the abstract grammar are related to optimisations: tail call optimisation, inlining, prevalent function call patterns, &c.This approach proved to be an interesting setting to expose graduate students to the vagaries low level language processor implementations. But it has also been suitable as a platform for sophisticated experiments with optimisations for language interpreters.

Formal Language Theory for Security (LangSec) applies the tools of theoretical computer science to the problem of protocol design and analysis. In practice, most results have focused on protocol design, showing that by restricting the complexity of protocols it is possible to design parsers with desirable and formally verifiable properties, such as correctness and equivalence. When we consider existing protocols, however, many of these were not subjected to formal analysis during their design, and many are not implemented in a manner consistent with their formal documentation. Determining a grammar for such protocols is the first step in analyzing them, which places this problem in the domain of grammatical inference, for which a deep theoretical literature exists. In particular, although it has been shown that the higher level categories of the Chomsky hierarchy cannot be generically learned, it is also known that certain subcategories of that hierarchy can be effectively learned. In this paper, we summarize some theoretical results for inferring well-known Chomsky grammars, with special attention to context-free grammars (CFGs) and their generated languages (CFLs). We then demonstrate that, despite negative learnability results in the theoretical regime, we can use long short-term memory (LSTM) networks, a type of recurrent neural network (RNN) architecture, to learn a grammar for URIs that appear in Apache HTTP access logs for a particular server with high accuracy. We discuss these results in the context of grammatical inference, and suggest avenues for further research into learnability of a subgroup of the context-free grammars.

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.

This work describes a formalization effort, using the Coq proof assistant, of fundamental results related to the classical theory of context-free 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. This is probably the most comprehensive formalization of the classical context-free language theory in the Coq proof assistant done to the present date, and includes the important result that is the formalization of the Pumping Lemma for context-free languages.

The first part of this article gives a brief overview of the four levels of the Chomsky hierarchy, with a special emphasis on context-free and regular languages. It then recapitulates the arguments why neither regular nor context-free grammar is sufficiently expressive to capture all phenomena in the natural language syntax. In the second part, two refinements of the Chomsky hierarchy are reviewed, which are both relevant to the extant research in cognitive science: the mildly context-sensitive languages (which are located between context-free and context-sensitive languages), and the sub-regular hierarchy (which distinguishes several levels of complexity within the class of regular languages).

The main idea of paper is to present a new proposal for a formal languages useful in modeling of many type of processes such as: economic, computing, social, biological, etc. Our approach is developed to describe computational models that can be implemented using established concepts such as different implementations of automata, etc.. The paper describes how is defined the new language based on developed rules and its grammar, upon which is build a computational model for optimal decision making in case of a process control. Verification and validatation of the proposed theory is supported by an experimental implementation that aim to optimize a generic flow in a economic process based on automaton described by proposed formal language.

The traditional conception of language is that it is, in Aristotle's phrase, sound with meaning. The sound-meaning correlation is, furthermore, unbounded, an elementary fact that came to be understood as of great significance in the 17th century scientific revolution. In contemporary terms, the internal language (I-language) of an individual consists, at the very least, of a generative process that yields an infinite array of structured expressions, each interpreted at two interfaces, the sensory-motor interface (sound, sign, or some other sensory modality) for externalization and the conceptual-intentional interface for thought and planning of action. The earliest efforts to address this problem, in the 1950s, postulated rich descriptive apparatus—in different terms, rich assumptions about the genetic component of the language faculty, what has been called “universal grammar” (UG). That seemed necessary to provide for a modicum of descriptive adequacy. Also, many puzzles were discovered that had passed u...

We discuss the computational complexity of context-free languages, concentrating on two well-known structural properties---immunity and pseudorandomness. An infinite language is REG-immune (resp., CFL-immune) if it contains no infinite subset that is a regular (resp., context-free) language. We prove that (i) there is a context-free REG-immune language outside REG/n and (ii) there is a REG-bi-immune language that can be computed deterministically using logarithmic space. We also show that (iii) there is a CFL-simple set, where a CFL-simple language is an infinite context-free language whose complement is CFL-immune. Similar to the REG-immunity, a REG-primeimmune language has no polynomially dense subsets that are also regular. We further prove that (iv) there is a context-free language that is REG/n-bi-primeimmune. Concerning pseudorandomness of context-free languages, we show that (v) CFL contains REG/n-pseudorandom languages. Finally, we prove that (vi) against REG/n, there exists an almost 1-1 pseudorandom generator computable in nondeterministic pushdown automata equipped with a write-only output tape and (vii) against REG, there is no almost 1-1 weakly pseudorandom generator computable deterministically in linear time by a single-tape Turing machine., A4, 23 pages, 10 pt. A complete revision of the initial version that was posted in February 2009

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

Quotients and factors are important notions in the design of various computational procedures for regular languages and for the analysis of their logical properties. We propose a new representation of regular languages, by linear systems of language equations, which is suitable for the following computations: language reversal, left quotients and factors, right quotients and factors, and factor matrices. We present algorithms for the computation of all these notions, and indicate an application of the factor matrix to the computation of solutions of a particular language reconstruction problem. The advantage of these algorithms is that they all operate only on linear systems of language equations, while the design of the same algorithms for other representations often require translation to other representations.

This article follows a generative approach to language, which argues that language is in part organized by rules and conditions which are specific to language. In Chomsky (Syntactic Structures, 1957), which is the foundational statement of generative linguistics, an example of a language specific rule was the ›transformational rule‹. This means that language may also be subject to other modes of organization, including linear concatenation, or counting, or rules of sequential ordering, which are not specific to language: these are the ›non-linguistic‹ modes of organization of language. In this article I identify some of the non-linguistic modes of organization as they appear in poetic language, and suggest that many aspects of poetic language must in fact be seen as non-linguistic in this sense. This violates a widely-stated hypothesis held by many linguists (at least since Sapir) who work on poetry, that poetic language is a development of the rules or conditions or processes of non-poetic (ordinary) language: this is the ›development hypothesis‹.

In this paper we present a constraint satisfaction approach to the pragmatic control of the language generation process in dialogue systems. After a brief problem statement providing motivational background for a constraint satisfaction approach to context sensitive language generation, a theoretical framework designed and implemented in part by the authors (in the context of several research and development projects) will be argued for in concise manner. Particularly, the way in which constraints influence the generation of context-sensitive, relevant utterances in simultaneous interaction with several human speakers will be considered in detail, providing a computational framework for handling “pragmatic” aspects, such as the degree of illocutionary force, semantic ellipsis, or lexical selection of concessive connectors. Then, limiting cases of our approach will be pointed out, showing in what measure by acting on the constraints we can enlarge these limits.

Tree controlled grammars are context-free grammars where the associated language only contains those terminal words which have a derivation where the word of any level of the corresponding derivation tree belongs to a given regular language. In this paper, we consider first as control sets such regular languages which can be represented by finite unions of monoids. We show that the corresponding hierarchy of tree controlled languages collapses already at the second level. Second, we restrict the number of states allowed in the accepting automaton of the regular control language. We prove that the associated hierarchy has at most five levels.

We consider two complementary operations: Hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: Hairpin completion, in: Proc. Transgressive Computing, 2006, pp. 216–228] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.

FALGOL (Formal ALGOrithmic Language) is a fundamental theoretical model of high-level operational languages with unrestricted program object hierarchy. This model formalizes binding, assignment, substitution, and recursion; moreover, the principle of dynamic binding is implemented in the model in contrast to other formal systems of this sort, which makes FALGOL appropriate to specify the most difficultly formalized concepts in modern object programming languages.

We present a novel approach to computing the context-sensitive flow of values through procedures and data structures. Our approach combines and extends techniques from two seemingly disparate areas: polymorphic subtyping and interprocedural dataflow analysis based on context-free language reachability. The resulting technique offers several advantages over previous approaches: it works directly on higher-order programs; provides demand-driven interprocedural queries; and improves the asymptotic complexity of a known algorithm based on polymorphic subtyping fromO(n8) toO(n3) for computing all queries. For intra-procedural flow restricted to equivalence classes, our algorithm yields linear inter-procedural flow queries.

A word w over a finite alphabet @S is n-collapsing if for an arbitrary deterministic finite automaton A=, the inequality |@d(Q,w)|@?|Q|-n holds provided that |@d(Q,u)|@?|Q|-n for some word [email protected][email protected]^+ (depending on A). We prove that the property of n-collapsing is algorithmically recognizable for any given positive integer n. We also prove that the language of all n-collapsing words is context-sensitive.

The number of transitions required by a nondeterministic finite automaton (NFA) to accept a regular language is a natural measure of the size of that language. There has been a significant amount of work related to the trade-off between the number of transitions and other descriptional complexity measures for regular languages. In this paper, we consider the effect of language operations on the number of transitions required to accept a regular language. This work extends previous work on descriptional complexity of regular language operations, in particular, under the measures of deterministic state complexity, nondeterministic state complexity and regular expression size.

In this paper, we explore the use of proportional analogy reasoning to address the problem of language transfer, that is the production of an utterance in a defined target language, given another in the source language. The application we focused on is the transfer of requests in a natural language (French) into commands in a formal language (bash). We introduce a hybrid approach which parallelly uses formal analogy in the language domain and in the more general word sequences domain in order to separately tackle linguistic and parametric variations. On the observation that parametric variations are the most unpredictable, we also apply analogy to automatically extend the available data by generating new requests from the existing ones. Our approach is language independent, it was designed with the help of analogical reasoning to be as generic as possible.

In this paper we explore possibilities of recursive regular expression construction. Such expressions can contain other expressions as a fundamental element, even recursively contain themselves. We call such expressions higher order functions. A recursive automaton can be constructed from it. We present such automata and show, that they may have infinite states and are able to accept context-free grammars. Higher order nondeterminism is explored as a direct result of higher order regular expressions.

Formal Language Theory for Security (LANGSEC) has proposed that formal language theory and grammars be used to define and secure protocols and parsers. The assumption is that by restricting languages to lower levels of the Chomsky hierarchy, it is easier to control and verify parser code. In this paper, we investigate an alternative approach to inferring grammars via pattern languages and elementary formal system frameworks. We summarize inferability results for subclasses of both frameworks and discuss how they map to the Chomsky hierarchy. Finally, we present initial results of pattern language learning on logged HTTP sessions and suggest future areas of research.

Every context-free grammar can be transformed into an equivalent one in the Chomsky normal form by a sequence of four transformations. In this work on formalization of language theory, we prove formally in the Agda dependently typed programming language that each of these transformations is correct in the sense of making progress toward normality and preserving the language of the given grammar. Also, we show that the right sequence of these transformations leads to a grammar in the Chomsky normal form (since each next transformation preserves the normality properties established by the previous ones) that accepts the same language as the given grammar. As we work in a constructive setting, soundness and completeness proofs are functions converting between parse trees in the normalized and original grammars.

Chomsky's theory of Universal Grammar (UG) is introduced to explain children's rapid convergence on the grammar of their local language. A system of innate principles and parameters guides children's acquisition of language. Children are shown to misset certain parameters causing them to hypothesize properties not observed in the language of the community. Children's temporary missteps are put aright with input from the surrounding language. The misset parameters are predicted by the theory of UG but not anticipated by usage-based theories of language acquisition.

We propose two computational models - one of a language within context based on systemic functional linguistic theory and one of context-sensitive language understanding. The model of a language within context called the Semiotic Base characterizes contextual, semantic, lexicogrammatical, and graphological aspects of input texts. The understanding process is divided into shallow and deep analyses. Shallow analysis consists of morphological and dependency analyses and word concept and case relation assignment, mainly by existing natural language processing tools and machine-readable dictionaries. Results are used to detect the contextual configuration of input text in contextual analysis. This is followed by deep analyses of lexicogrammar, semantics, and concepts, conducted by referencing a subset of resources related to the detected context. Our proposed models have been implemented in Java and verified by integrating them into such applications as dialog-based question-and-answer (Q&A).

We give "syntactic" characterizations of context-sensitive languages (CSLs) in terms of some restricted models of symport/antiport P systems. These are the first such characterizations of CSLs in terms of P systems. In particular, we show the following for any language L over a binary alphabet: (1) Let m be any integer ≥ 1. Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with m membranes and multiple number of symbols (objects). Moreover, holding the number of membranes at m, there is an infinite hierarchy in computational power (within the class of binary CSLs) with respect to the number of symbols. (2) Let s be any integer ≥ 14. Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with s symbols and multiple number of membranes. Moreover, holding the number of symbols at s, there is an infinite hierarchy in computational power with respect to the number of membranes. (Similar results hold for languages over an alphabet of k ≥ 2 symbols.) Thus (1) and (2) say that in order for the restricted symport/antiport P systems to accept all binary CSLs, at least one parameter (either the number of symbols or the number of membranes) must grow. These are the first results of their kind in the P systems area. They contrast a known result that (unrestricted) symport/antiport P systems with s ≥ 2 symbols and m ≥ 1 membranes accept (or generate) exactly the recursively enumerable sets of numbers even for s + m = 6. We also note that previous characterizations of formal languages in the membrane computing literature are mostly for the Parikh images of languages.Variations of our model yield characterizations of regular languages, languages accepted by one-way log n space-bounded Turing machines, and recursively enumerable languages.

Many functions on context-free languages can be expressed in the form of the least fixed point of a function whose definition mimics the grammar of the given language. Examples include the function returning the length of the shortest word in a language, and the function returning the smallest number of edit operations required to transform a given word into a word in a language. This paper presents the basic theory that explains when a function on a context-free language can be defined in this way. It is shown how the theory can be applied in a methodology for programming the evaluation of such functions. Specific results include a novel definition of a regular algebra focusing on the existence of so-called “factors”, and several constructions of non-trivial regular algebras. Several challenging problems are given as examples, some of which are old and some of which are new.