Deterministic Lindenmayer languages,nonterminals and homomorphisms

Lindenmayer systems are a class of parallel rewriting systems originally introduced to model the growth and development of filamentous organisms. Families of languages generated by deterministic Lindenmayer systems (i.e., those in which each string has a unique successor) are investigated. In particular, the use of nonterminals, homomorphisms, and the combination of these are studied for deterministic Lindenmayer systems using one-sided context (D1Ls) and two-sided context (D2Ls). Languages obtained from Lindenmayer systems by the use of nonterminals are called extensions. Typical results are: The closure under letter-to-letter homomorphism of the family of extensions of D1L languages is equal to the family of recursively enumerable languages, although the family of extensions of D1L languages does not even contain all regular languages. Let P denote the restriction that the system does not rewrite a letter as the empty word. The family of extensions of PD2L languages is equal to the family of languages accepted by deterministic linear bounded automata. The closure under nonerasing homomorphism of the family of extensions of PD1L languages does not even contain languages like {a₁,a₂,?, a_n}¹--{λ}, n?2 . The closure of the family of PD1L languages under homomorphisms which map a letter either to itself or to the empty word is equal to the family of recursively enumerable languages. Strict inclusion results follow from necessary conditions for a language to be in one of the considered families. By stating the results in their strongest form, the paper contains a systematic classification of the effect of nonterminals, letter-to-letter homomorphisms, nonerasing homomorphisms and homomorphisms for all the basic types of deterministic Lindenmayer systems using context.     

On input-revolving deterministic and nondeterministic finite automata

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.     

The Boolean closure of linear context-free languages

Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to a certain level, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.     

模糊树自动机语言的封闭性

给出了[Σ-]代数、[Σ-]树、模糊[Σ-]树自动机、模糊[Σ-]树自动机行为的定义。引入了模糊树自动机语言的并、交、连接和Kleene闭包运算,证明了在这些运算下模糊树自动机语言的封闭性。     

State complexity of basic operations on suffix-free regular languages

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.     

正规语言闭包运算的Petri网构造方法

Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。     

Operator precedence and the visibly pushdown property

Floyd?s operator precedence grammars and languages (FG, FL) are a classical subclass of deterministic context-free (DCF) grammars and languages. We prove that several recently introduced language families motivated by the needs of model checking and of specifying XML-like languages are proper subsets of FL. The main cases considered include visibly pushdown languages (VPL) and balanced languages (BALAN), which are characterized by restricted precedence relations. FL have all the closure properties available for regular languages and generally viewed as necessary for application to model checking: reversal, prefixing and suffixing, concatenation, Kleene star, and boolean operations. All but the last results are new, and some require complex proofs, due to the necessary changes of syntax structure. Thus FL are the largest known subfamily of DCF having the same closure properties as VPL. FG, unlike VPL grammars, which are intended for abstract syntax modelling, are structurally adequate to specify real programming languages.     

Inverse star, borders, and palstars

A language L is closed if L=L^?. We consider an operation on closed languages, L−?, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L−? is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.     

Le cylindre des langages linéaires

Define a cylinder to be a family of languages which is closed under inverse homomorphisms and intersection with regular sets. A number of well-known families of languages are cylinders:

—CFL, the family of context-free languages, is a principal cylinder, i.e. the smallest cylinder containing a languageL _O described in [6].

—the family of deterministic context-free languages is proved to be a nonprincipal cylinder in [7].

—the family of unambiguous context-free languages is a cylinder: to prove that it is not principal seems to be a very hard problem.

In this paper we prove that Lin, the family of linear context-free languages, is a nonprincipal cylinder. This is achieved in the standard way by exhibiting a sequence of languages S_n, n∈N, such that Lin is the union of all the principal cylinders generated by these languages and is not the union of any finite number of these cylinders. This leaves open the problem raised by Sheila Greibach of whether there exists a languageL such that every linear context-free language is the image ofL in some inverse gsm mapping.     

Composition and orbits of language operations: finiteness and upper bounds

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independent of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations.     

Comparing language operations

A procedure for comparing language operations is formulated and used to study some general algebraic properties of such operations as well as the interrelationships of some specific well known operations. The comparison scheme is used to partition the family of all language operations into a collection of equivalence classes that forms an upper semilattice, When full semi-AFL operations are used as a basis of comparison, the Min and Max operations are shown to be in the same class as relative complementation and reside above the class containing Kleene closure. This gives the result that any complementation closed full semi-AFL is a full AFL closed under Min and Max.This paper was supported in part by the National Science Foundation under grant GJ-803 and in part by the U.S. Army Research Office.     

Shuffle languages are in P

In this paper we show that shuffle languages are contained in one-way-NSPACE(log n) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression E we construct a shuffle automaton which accepts the language generated by E and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.     

On languages of automaton counter machines

A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed.     

Quotient Complexity of Closed Languages

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in an analogous way, where by factor we mean contiguous subsequence, and by subword we mean scattered subsequence. We study the state complexity (which we prefer to call quotient complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star, and reversal in each of the four classes of closed languages. We show that repeated applications of positive closure and complement to a closed language result in at most four distinct languages, while Kleene closure and complement give at most eight.     

On iterated hairpin completion

(Bounded) hairpin completion and its iterated versions are operations on formal languages which have been inspired by hairpin formation in DNA biochemistry. The paper answers two questions asked in the literature about iterated hairpin completion.The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion.In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular: actually, it is not context-free, but context-sensitive.     

Characterization of co-observable languages and formulas for their super/sublanguages

We present fixed-point based characterization of several classes of co-observable languages that are of interest in the context of decentralized supervisory control of discrete-event systems, including C&P /spl or/ D&A co-observable languages, C&P co-observable languages, and D&A co-observable languages. We also provide formulas for computing super/sublanguages for each of these classes. In cases where the class of co-observable languages is not closed under intersection/union, we provide upper/lower bound of the super/sublanguage formula we present. The computation of super/sublanguages and also computation of their upper/lower bounds has lead to the introduction of other classes of co-observable languages, namely, strongly C&P co-observable languages, strongly D&A co-observable languages, locally observable languages, and strongly locally observable languages. Fixed-point based characterization of all the above language classes is also given, and their closure under intersection/union is investigated. We also study whether the fixed-point operator preserves prefix closure, relative closure (also called L/sub m/(G)-closure), and controllability.     

Two complementary operations inspired by the DNA hairpin formation: Completion and reduction

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.     

Algebraic properties on the cuts of lattice-valued regular languages

In this paper, the algebraic operations on the cuts of lattice-valued regular languages are studied. Some sufficient conditions are given to guarantee the family of the cuts of lattice-valued regular languages to be closed under such algebraic operations as union, intersection, complement, quotient, homomorphism, inverse homomorphism, concatennation, reversal, etc. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program (Grant No. 2002CB312200).