State complexity of some operations on binary regular languages

We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

The complexity of basic complex operations

It is well-known that the product of two complex numbersX+iY andU+iV requires exactly 3 realm/d. We study the algebraic complexity of several other operations from the repertoire of complex arithmetic. We show, for instance, that complex inversion requires exactly 4m/d and that general complex division requires at least 5m/d. For the latter problem an upperbound of 6m/d is known, leaving some speculation as to its precise complexity. The proofs illustrate several criteria which may be of more general use in assessing the complexity of concrete sets of rational functions.     

State complexity of unique rational operations

For each basic language operation we define its “unique” counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity.     

Continuous operations on languages

Most of the operations of interest in language theory arecontinuous in a certain technical sense. For such operations, there always exist infinite sets of languages that areindependent in the sense that no language in such a set can be generated from the other languages in the set by the operations in question.     

正则语言的一个特征

Myhill-Nerode定理利用等价关系描述了正则语言的一个重要特征,它是有限自动机理论中的一个经典、优美的结果。为了将Myhill-Nerode定理推广到更一般的情形,引入了有限自动机M上的状态转移半群和Σ*上的M-半群,讨论了其若干性质。在此基础上,将Myhill-Nerode定理中的等价关系一般化,给出了正则语言的一个新的特征定理,Myhill-Nerode定理成为该定理的一个推论。讨论了正则语言的最一般的特征,提出了有待进一步研究的问题。     

Operations preserving regular languages

Given a strictly increasing sequence s   of non-negative integers, filtering a word _a0a1?_an$a_0{a}_1?a_n$ by s   consists in deleting the letters _ai$a_i$ such that i   is not in the set {_s0,_s1,…}$\{s_0,s_1,\dots \}$. By a natural generalization, denote by L[s]$L[s]$, where L is a language, the set of all words of L filtered by s. The filtering problem is to characterize the filters s such that, for every regular language L  , L[s]$L[s]$ is regular. In this paper, the filtering problem is solved, and a unified approach is provided to solve similar questions, including the removal problem considered by Seiferas and McNaughton. Our approach relies on a detailed study of various residual notions, notably residually ultimately periodic sequences and residually rational transductions.     

On the intersection of regex languages with regular languages

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

Renormalized measure of regular languages

This paper modifies the signed real measure of regular languages, which has been reported in recent literature for analysis and synthesis of discrete event supervisory control laws. A new concept of renormalized measure is introduced to eliminate a user-selectable parameter in the present version of the language measure. The concept of measure renormalization is illustrated by an example.     

Context-free complexity of finite languages

In this paper the investigation of the theory of grammatical complexity as started by Bucher (1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question we are concerned with is the following: Given some finite language L, what is the smallest number of context-free productions needed to generate L, the so-called (context-free) complexity of L. We strengthen some of the results given by Bucher et al. (1981), the main result being a necessary condition for certain sequences of finite languages to be of sublinear complexity.     

Well quasi-orders and regular languages

An extension of Myhill's theorem of automata theory, due to Ehrenfeucht et al. [4] shows that a subsetX of a semigroupsS is recognizable if and only ifX is closed with respect to a monotone well quasi-order onS. In this paper we prove that a similar extension of Nerode's theorem is not possible by showing that there exist non-regular languages on a binary alphabet which are closed with respect to a right-monotone well quasi-order. We give then some additional conditions under which a setX S closed with respect to a right-monotone well quasi-order becomes recognizable. We prove the following main proposition: A subsetX ofS is recognizable if and only ifX is closed with respect to two well quasi-orders<=₁ and<=₂ which are right-monotone and left-monotone, respectively. Some corollaries and applications are given. Moreover, we consider the family of all languages which are closed with respect to a right-monotone well quasi-order on a finitely generated free monoid. We prove that is closed under rational operations, intersection, inverse morphisms and direct non-erasing morphisms. This implies that is closed under faithful rational transductions. Finally we prove that the languages in satisfy a suitable pumping lemma and that contains languages which are not recursively enumerable.     

Learning regular languages using RFSAs

Residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. In order to identify a given target language L, classical inference algorithms try to identify words which define identical residual languages of L. Here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of L. We consider the class of Residual Finite State Automata (RFSAs). An RFSA A is a NonDeterministic Automaton whose states corresponds to residual languages of the language L_A it recognizes. The inclusion relations between residual languages of L_A can be naturally materialized on A. We prove that the class of RFSAs is not polynomially characterizable. We lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. Moreover, its minimal RFSA representation is much smaller than its minimal DFA representation. Finally, we design a new learning algorithm, DeLeTe2, based on the search for the inclusion relations between the residual languages of the target language. We give sufficient conditions for the identifiability of the target language. We experimentally compare the performance of DeLeTe2 to those of classical inference algorithms.     

Petri nets and regular languages

It is shown that the regularity problem for firing sequence sets of Petri nets is decidable. For the proof, new techniques to characterize unbounded places are introduced. In the class $\text{L}$₀ of terminal languages of labelled Petri nets the regularity problem in undecidable. In addition some lower bounds for the undecidability of the equality problems in $\text{L}$₀ and $\text{L}$ are given. L₀^λ is shown to be not closed under complementation without reference to the reachability problem.     

Unconstrained optimal control of regular languages

This paper formulates an unconstrained optimal policy for control of regular languages realized as deterministic finite state automata (DFSA). A signed real measure quantifies the behavior of controlled sublanguages based on a state transition cost matrix and a characteristic vector as reported in an earlier publication. The state-based optimal control policy is obtained by selectively disabling controllable events to maximize the measure of the controlled plant language without any further constraints. Synthesis of the optimal control policy requires at most n iterations, where n is the number of states of the DFSA model. Each iteration solves a set of n simultaneous linear algebraic equations. As such, computational complexity of the control synthesis is polynomial in n.     

Robust optimal control of regular languages

This paper presents an algorithm for robust optimal control of regular languages under specified uncertainty bounds on the event cost parameters of the language measure that has been recently reported in literature. The performance index for the proposed robust optimal policy is obtained by combining the measure of the supervised plant language with uncertainty. The performance of a controller is represented by the language measure of the supervised plant and is minimized over the given range of event cost uncertainties. Synthesis of the robust optimal supervisory control policy requires at most n iterations, where n is the number of states of the deterministic finite-state automaton (DFSA) model, generated from the regular language of the unsupervised plant behavior. The computational complexity of the control synthesis method is polynomial in n.