Rewriting systems with limited distance permitting context

By restricting the permitting context symbols in a rewriting system to be within a specified distance from the symbol to be replaced, we strictly increase the generative power above that of rewriting systems where the context symbols can appear within arbitrary distances from the symbol to be replaced.     

Scattered context grammars generate any recursively enumerable language with two nonterminals

By showing that two nonterminals are sufficient, we present the optimal lower bound on the number of nonterminals of scattered context grammars being able to generate any recursively enumerable language.     

Regulated RNA rewriting: Modelling RNA editing with guided insertion

RNA editing is an important alternative genetic processing event that is known to take place in all higher eukaryotes. We study a model of string rewriting based on the sophisticated RNA editing mechanism found in trypanosome kinetoplasts. We demonstrate basic properties of three principal variants of this model which we show to form a strict hierarchy in terms of expressive power. We also present a method and software for simulating real biological RNA editing via this model and apply the theoretical results to suggest real biological constraints on this process.     

A strong pumping lemma for context-free languages

A context-free language is shown to be equivalent to a set of sentences describable by sequences of strings related by finite substitutions on finite domains, and vice-versa. As a result, a necessary and sufficient version of the Classic Pumping Lemma is established. This result provides a guaranteed method of proving that a language is not context-free when such is the case. An example is given of a language which neither the Classic Pumping Lemma nor Parikh's Theorem can show to be non-context-free, although Ogden's Lemma can. The main result also establishes {aⁿba^mn} as a language which is not in the Boolean closure of deterministic context-free languages.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.     

P-hardness of the emptiness problem for visibly pushdown languages

Visibly pushdown languages form a subclass of the context-free languages which is appealing because of its nice algorithmic and closure properties. Here we show that the emptiness problem for this class is not any easier than the emptiness problem for context-free languages, namely hard for deterministic polynomial time. The proof consists of a reduction from the alternating graph reachability problem.     

Extensions of sokolowski's theorem to prove languages are not context free or not regular

An extension of a theorem of Sokolowski's is given which is more generally applicable and illustrated by showing several languages are not context free. This is then modified to prove a similar kind of theorem for regular languages.     

Two undecidability results for chain code picture languages

It is undecidable whether or not two 1-retreat-bounded regular languages describe exactly the same set of pictures or they describe a picture in common.     

A Rewriting-based Framework for Web Sites Verification

In this paper, we develop a framework for the automated verification of Web sites which can be used to specify integrity conditions for a given Web site, and then automatically check whether these conditions are fulfilled. First, we provide a rewriting-based, formal specification language which allows us to define syntactic as well as semantic properties of the Web site. Then, we formalize a verification technique which obtains the requirements not fulfilled by the Web site, and helps to repair the errors by finding out incomplete information and/or missing pages. Our methodology is based on a novel rewriting-based technique, called partial rewriting, in which the traditional pattern matching mechanism is replaced by tree simulation, a suitable technique for recognizing patterns inside semistructured documents. The framework has been implemented in the prototype Web verification system Verdi which is publicly available.     

A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions.     

A note on equations for commutative regular languages

In this note we prove that the equations satisfied by one-letter regular languages are exactly those satisfied by commutative regular languages. This answers a problem raised by Arto Salomaa.     

Recursive functions of context free languages (II)

In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains. It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described. This paper is based on the Technical Report ISCAS-LCS-2k-03 (SAQ Report no.30): Recursive Functions Defined on Context Free Languages (I) August 2000 with minor revisions.     

Recursive functions of context free languages (I)

It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non-numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed. This paper is based on the Technical Report ISCAS-LCS-2k-03 (SAQ Report No. 30): Recursive Functions Defined on Context Free Languages (I), August 2000, with minor revisions.     

A framework to visualize equivalences between computational models of regular languages

We discuss how to increase and simplify the understanding of the equivalence relations between machine models and/or language representations of formal languages by means of the animation tool SAGEMoLiC. Our new educational tool permits the simulation of the execution of models of computation, as many other animation systems do, but its philosophy goes further than these of the usual systems since it allows for a true visualization of the key notions involved in the formal proofs of these equivalences. In contrast with the proposal of previous systems, our approach to visualize equivalence theorems is not a simple “step by step animation” of specific conversion algorithms between computational models and/or grammatical representations of formal languages, because we make emphasis on the key theoretical notions involved in the formal proofs of these equivalences.     

Recursive functions of context free languages (Ⅱ)——Validity of CFPRF and CFRF definitions

In this paper we proved that the function class CFRF and its proper subclass CFPRF are respectively the partial recursive functions and primitive recursive functions of context free languages (CFLs). Also we discussed the relation between them and recursive functions defined on other domains . It is indicated that the functions of natural numbers and/or symbol strings (words) are functions of CFLs. Several frequently used primitive recursive functions on words were given, including logical connectives, conditional expressions. Also the powerful operators (bounded maximization and minimization operators) for constructing primitive recursive functions were defined. Two important nontrivial algorithms, the characteristic function of arbitrary CFL and the parse function of CFL sentences were constructed. Based on them, the method for extending or restricting function domain was described.     

A characterization of (regular) circular languages generated by monotone complete splicing systems

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for monotone complete systems, which are finite circular splicing systems with rules of a simpler form. We show that a circular language L is generated by a monotone complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by monotone complete systems. We can also decide whether the language generated by a monotone complete system is regular. Finally, we point out that monotone complete systems have the same computational power as finite simple systems, an easy type of circular splicing system defined in the literature from the very beginning, when only one rule of a specific type is allowed. From our results on monotone complete systems, it follows that finite simple systems generate a class of languages containing non-regular languages, showing the incorrectness of a longstanding result on simple systems.