Search

We study grammatical counterparts of concepts of welfare economics as Pareto optimum and Pareto sets. As targets, we consider the numbers of nonterminals and productions of a grammar. For a context-free grammar G = (N,T, P, S), we set p(G) = (card(N), card(P)). We say that the pair (m, n) is a Pareto optimum for L if there is a context-free grammar G with L(G) = L and p(G) = (m, n) and there is no context-free grammar G' with L(G') = L, p(G') = (m',n'), and either m' < m and n' ≤ n or n' < n and m' ≤ m. The Pareto set P(L) of L is the set of all Pareto optima of L. We give some properties of Pareto optimal pairs and present a method to determine the Pareto set. Furthermore, we show that, for each natural number m, there is a language whose Pareto set has exactly m elements. [ABSTRACT FROM AUTHOR]

We continue the research on the generative capacity of contextual grammars where contexts are adjoined around whole words (externally) or around subwords (internally) which belong to special regular selection languages. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We investigate the computational capacity of contextual grammars with strictly locally testable selection languages and compare those families to families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages. With these results, also an open problem regarding ordered and non-counting selection languages is solved. [ABSTRACT FROM AUTHOR]

For a regular language L , let Var (L) be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers k 1 , k 2 , ... , k n and an n -ary regularity preserving operation f , let the range g f Var (k 1 , k 2 , ... , k n) be the set of all numbers k such that there are regular languages L 1 , L 2 , ... , L n with Var (L i) = k i for 1 ≤ i ≤ n and Var (f (L 1 , L 2 , ... , L n)) = k. We show that, for the circular shift operation Circ , g Circ Var (n) is infinite for all n , and we completely determine the set g Circ Var (2). Moreover, we give a precise range for the left right quotient and a partial result for the left quotient. Furthermore, we add some values to the range for the operation intersection which improves the result of [2]. [ABSTRACT FROM AUTHOR]

In an external contextual grammar with selection, contexts are associated with selection languages, and the context (u , v) can be wrapped around a word w if and only if w belongs to the selection language associated with (u , v). In the papers [1] , [3] , [4] , and [6] , some hierarchies are presented if selection languages are taken from subregular language families, defined by automata-theoretic and combinatorial properties, codes, and ideals. In this paper we merge and complete the hierarchies. [ABSTRACT FROM AUTHOR]

In this paper, we continue the research on accepting networks of evolutionary processors where the filters belong to several special families of regular languages. We consider families of codes or ideals and subregular families which are defined by restricting the resources needed for generating or accepting them (the number of states of the minimal deterministic finite automaton accepting a language of the family as well as the number of non-terminal symbols or the number of production rules of a right-linear grammar generating such a language). We insert the newly defined language families into the hierachy of language families obtained by using as filters languages of other subregular families (such as ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, combinational, finite, monoidal, nilpotent, or commutative languages). [ABSTRACT FROM AUTHOR]

Let a s c (L) be the minimal number of accepting states which is sufficient for deterministic finite automata to accept L. For a number n ≥ 1 and an n -ary regularity preserving operation ∘, we define g ∘ a s c (m 1 , m 2 , ... , m n) as the set of all integers r such that there are n  languages L i , 1 ≤ i ≤ n , with a s c (L i) = m i for  1 ≤ i ≤ n and a s c (∘ (L 1 , L 2 , ... , L n)) = r. In this paper, we study these sets for the operations union, catenation, star, complement, set-subtraction, and intersection where we restrict to unary or finite or unary and finite languages L i . [ABSTRACT FROM AUTHOR]

For a closure operation c and an involution i defined on a language family L , we define N c , i L (L) as the number of languages which can be obtained from L by repeated applications of c and i. The orbit O L (c , i) of c and i is defined as the set of all these numbers. We determine the orbit for some classical language theoretic closure operators and the involution complement. We show that complement and reversal behave very different with respect to some special closure operators. Moreover, we prove that, for an arbitrary closure operator and reversal, some "small" numbers cannot be avoided in the orbit. [ABSTRACT FROM AUTHOR]

In this paper, we approach the problem of accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013. [ABSTRACT FROM AUTHOR]

We introduce the inner palindromic closure as a new operation ♠, which consists in expanding a factor u to the left or right by a non-empty word v such that vu or uv, respectively, is a palindrome of minimal length. We investigate several language theoretic properties of the iterated inner palindromic closure ♠*(w) = Ui≥0 ♠i(w) of a word w. [ABSTRACT FROM AUTHOR]

We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular languages. Essentially, we prove that the hierarchy of language families obtained from conditional Lindenmayer systems with subregular conditions is almost identical to the hierarchy of families of subregular languages. [ABSTRACT FROM PUBLISHER]

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational power. [ABSTRACT FROM AUTHOR]

Abstract: Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols. [Copyright &y& Elsevier]

In this paper, we study networks of evolutionary processors where the filters are chosen as special regular sets. We consider networks where all the filters belong to a set of languages that are accepted by deterministic finite automata with a fixed number of states. We show that if the number of states is bounded by two, then every recursively enumerable language can be generated by such a network. If the number of states is bounded by one, then not all regular languages but non-context-free languages can be generated. [ABSTRACT FROM AUTHOR]

A symbol a is called active in an L system G if there is a rule a → υ with a ≠ υ in some table of G. By AcX(L) we denote the number of active symbols necessary to generate L by L systems of type X. For two types X and Y of L systems such that the corresponding languages families $\mathcal{L}(X)$ and $\mathcal{L}(Y)$ satisfy $\mathcal{L}(X)\, \subset \,\mathcal{L}(Y)$, we say that Y is more efficient than X, if there is a sequence of languages $L_n \, \in \,\mathcal{L}(X)$, n ≥ 1, such that AcX(Ln) ≥ n and AcY(Ln) ≤ k for some constant k. In this paper we shall show that the inclusion $\mathcal{L}(X)\, \subset \,\mathcal{L}(Y)$ implies that Y is more efficient than X. Analogous results are presented for some modifications of the measure of active symbols. [ABSTRACT FROM AUTHOR]

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. We present some results on the power of such grammars where we restrict the regular languages to some known subclasses of the family of regular languages. [ABSTRACT FROM AUTHOR]

A cyclic unary regular language is a regular language over a unary alphabet that is represented by a cyclic automaton. We propose a similarity measure for cyclic unary regular languages by modifying the Jaccard similarity coefficient and the Sørensen coefficient to measure the level of overlap between such languages. This measure computes the proportion of strings that are shared by two or more cyclic unary regular languages and is an upper bound of the Jaccard coefficient and the Sørensen coefficient. By using such similarity measure, we define a dissimilarity measure for cyclic unary regular languages that is a semimetric distance. Moreover, it can be used for the non-cyclic case. [ABSTRACT FROM AUTHOR]

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes. [ABSTRACT FROM AUTHOR]

We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect to language-theoretic operations. For given numbers c_1, c_2, .., c_n and an n-ary operation τ on language, we discuss the range of Var (τ(L_1,L_2,..L_n)) where for 1 &les;i&les;n, L_i is a context-free language with Var (L_i) = c_i. The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets. [ABSTRACT FROM AUTHOR]

We define cooperating distributed grammar systems with start and stop conditions which are based on the competence of a component on the current sentential form. We distinguish six different types of competence conditions which result in 18 types of grammar systems. We summarize the results on the generative power known from the literature (where they are sometimes not related to competence) and determine the power of some further grammar systems. [ABSTRACT FROM AUTHOR]

In this paper we examine context-free cooperating distributed (CD) grammar systems where the cooperation protocol is based on the competence (capability) of the component grammars in rewriting. We study the power of a derivation mode where every component is allowed to start the generation only if it has a prescribed level of competence and it is allowed to finish the work if it is not competent anymore. The competence level of a component on a string is the number of different nonterminals in this word that can be rewritten by the production set of the grammar. We show that if the prescribed level of competence of the grammar to start the derivation is equal to k or is at least k , for some natural number k ≥ 2, then these CD grammar systems are as powerful as the ET0L systems with random context conditions. If this competence level is exactly one, or at least one, or it is at most k , where k ≥ 2, then the class of ET0L languages is determined by these constructions. [ABSTRACT FROM AUTHOR]

We formalize the hairpin inverted repeat excision, which is known in ciliate genetics as an operation on words and languages by defining $\mathcal{HI} (w, P)$ as the set of all words xαyRαRz where w = xαyαRz and the pointer α is in P. We extend this concept to language families which results in families $\mathcal{HI} ({\mathcal L}_1, {\mathcal L}_2)$. For ${\mathcal L}_1$ and ${\mathcal L}_2$ be the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families $\mathcal{HI} ({\mathcal L}_1, {\mathcal L}_2)$ and compare these families with those of the Chomsky hierarchy. Furthermore, we present the status of decidability of the membership problem, emptiness problem and finiteness problem for the families $\mathcal{HI} ({\mathcal L}_1, {\mathcal L}_2)$. [ABSTRACT FROM AUTHOR]

Abstract: Evolutionary systems have been introduced by Csuhaj-Varjú and Mitrana (Acta Inform. 36 (2000) 913) who proved that two context-sensitive or three context-free components are sufficient to obtain all recursively enumerable languages. We improve these results by showing that two context-free components are sufficient to generate all recursively enumerable languages. Furthermore, we study the power of systems with one component. [Copyright &y& Elsevier]

We discuss external contextual grammars with choice where the choice language belongs to a family of subregular languages. We determine the hierarchy of language families of contextual languages which is obtained by the use of nilpotent, combinational, definite, regular suffix closed, and regular commutative languages as choice languages. [ABSTRACT FROM AUTHOR]

We define the number of productions and the number of symbols as measures of descriptional complexity for tabled interactionless Lindenmayer systems and their special cases. We investigate the decrease of the descriptional complexities if we go from a family to another one which has a larger generative capacity. [ABSTRACT FROM AUTHOR]