Narrow Results

A class of languages is closed under a given operation if the resulting language belongs to this class whenever the operands belong to it. We examine the closure properties of various subclasses of regular languages under basic operations of intersection, union, concatenation and power, positive closure and star, reversal, and complementation. We consider the following classes: definite languages and their variants (left ideal, finitely generated left ideal, symmetric definite, generalized definite and combinational), two-sided comets and their variants comets and stars, and the classes of singleton, finite, ordered, star-free, and power-separating languages. We also give an overview about subclasses of convex languages (classes of ideal, free, and closed languages), union-free languages, and group languages. We summarize some inclusion relations between these classes. Subsequently, for all pairs of a class and an operation, we provide an answer whether this class is closed under this operation or not.

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as $1$-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case, the size gap from $1$-limited automata to one-way deterministic finite automata is double exponential.

Here we introduce two restricted versions of $1$-limited automata, once-marking$1$-limited automata and always-marking$1$-limited automata, and study their descriptional complexity. We prove that once-marking $1$-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic $1$-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking $1$-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic.

We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation.

We investigate the complexity of basic regular operations on languages represented by Boolean and alternating finite automata. We get tight upper bounds $m+n$ and $m+n+1$ for union, intersection, and difference, $2^m+n$ and $2^m+n+1$ for concatenation, $2^n+n$ and $2^n+n+1$ for square, $m$ and $m+1$ for left quotient, $2^m$ and $2^m+1$ for right quotient. We also show that in both models, the complexity of complementation and symmetric difference is $n$ and $m+n$, respectively, while the complexity of star and reversal is $2^n$. All our witnesses are described over a unary or binary alphabets, and whenever we use a binary alphabet, it is always optimal. We also show that the tight upper bound for the conversion of alternating finite automata into nondeterministic finite automata with a unique initial state is $2^n+1$. Some of our results provide answers to open problems stated by Fellah et al. [5].

One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F₁F₂…F_k of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes.

We investigate the state complexity of concatenation and the nondeterministic state complexity of complementation of regular languages. We show that the upper bounds on the state complexity of concatenation are also tight in the case that the first automaton has more than one accepting state. In the case of nondeterministic state complexity of complementation, we show that the entire range of complexities, up to the known upper bound can be produced.

We consider the state complexity of several combined operations. Those results show that the state complexity of a combined operation is in general very different from the composition of the state complexities of the participating individual operations. We also consider general estimation methods for the state complexity of combined operations. In particular, estimation through nondeterministic state complexity is studied. It is shown that the method is very promising for a large class of combined operations.

Conjunctive grammars, introduced by Okhotin, extend context-free grammars by an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Okhotin posed nine open problems concerning those grammars. One of them was a question, whether a conjunctive grammars over a unary alphabet generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language {a⁴ⁿ : n ∈ ℕ}. We also generalize this result: for every set of natural numbers L we show that {aⁿ : n ∈ L} is a conjunctive unary language, whenever the set of representations in base-k system of elements of L is regular, for arbitrary k.

We study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak are considered, and another notion, called accept, is introduced. In all cases, we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols.

Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability and characterizations or representations of languages in Chomsky hierarchy were obtained in this framework.

In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Schützenberger representation of context-free languages, i.e., in the form L = h(L(γ) ∩ D), where γ is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages – this time using insertion systems of weight (3, 0) and star languages.

Antimirov and Mosses proposed a rewrite system for deciding the equivalence of two (extended) regular expressions. They argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal deterministic finite automata. In this paper we present a functional approach to that method, prove its correctness, and give some experimental comparative results. Besides an improved functional version of Antimirov and Mosses's algorithm, we present an alternative one using partial derivatives. Our preliminary results lead to the conclusion that, indeed, these methods are feasible and, most of the time, faster than the classical methods.

Our aim is to present an efficient algorithm that checks whether a binary regular language is geometrical or not, based on specific properties of its minimal deterministic automaton. Geometrical languages have been introduced in the framework of off-line temporal validation of real-time softwares. Actually, validation can be achieved through both a model based on regular languages and a model based on discrete geometry. Geometrical languages are intended to develop a link between these two models. The regular case is of practical interest regarding to implementation features, which motivates the design of an efficient geometricity test addressing the family of regular languages.

The consequences of regular expression hashing as a means of finite state automaton reduction is explored, based on variations of Brzozowski's algorithm. In this approach, each hash collision results in the merging of the automaton's states, and it is subsequently shown that a super-automaton will always be constructed, regardless of the hash function used. Since direct adaptation of the classical Brzozowski algorithm leads to a non-deterministic super-automaton, a new algorithm is put forward for constructing a deterministic FA. Approaches are proposed for measuring the quality of a hash function.

These ideas are empirically tested on a large sample of relatively small regular expressions and their associated automata, as well as on a small sample of relatively large regular expressions. Differences in the quality of tested hash functions are observed. Possible reasons for this are mentioned, but future empirical work is required to investigate the matter.

In this paper we study the non-deterministic communication complexity of regular languages. We show that a regular language has either constant or at least logarithmic non-deterministic communication complexity. We prove several linear lower bounds which we know cover a wide range of regular languages with linear complexity. Furthermore we find evidence that previous techniques (Tesson and Thérien 2005) for proving linear lower bounds, for instance in deterministic and probabilistic models, do not work in the non-deterministic setting.

We consider several problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center-disjoint k-locally testable languages in the strict sense. This result completes two results from [3] and [11]. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.

Restricting the Parikh Matrix mapping to a language rather than to an alphabet rises a set of problems that seem interesting to us. Moreover, amiability (or M-equivalence as it is named by other authors) is exploited in order to characterise certain types of languages. The paper also proposes a series of results establishing relations between classes of languages defined by Parikh matrix mappings and the Chomsky hierarchy. Finally, a result related to word composition concludes the paper, showing that for every two arbitrary words there exist two other words such that their composition (two by two) is amiable.

Solid codes have a nice property called synchronization property, which is useful in data transmission. The property is derived from infix-freeness and overlap-freeness of solid codes. Since a code is a language, we look at solid codes from formal language viewpoint. In particular, we study regular solid codes (that are solid codes and regular). We first tackle the solid code decidability problem for regular languages and propose a polynomial time algorithm. We, then, investigate the decidability of the overlap-freeness property and show that it is decidable for regular languages but is undecidable for context-free languages. Then, we study the prime solid code decomposition of regular solid codes and propose an efficient algorithm for the prime solid code decomposition problem. We also demonstrate that a solid code does not always have a unique prime solid code decomposition.

The partial derivative automaton () is usually smaller than other nondeterministic finite automata constructed from a regular expression, and it can be seen as a quotient of the Glushkov automaton (). By estimating the number of regular expressions that have ε as a partial derivative, we compute a lower bound of the average number of mergings of states in and describe its asymptotic behaviour. This depends on the alphabet size, k, and for growing k's its limit approaches half the number of states in . The lower bound corresponds to consider the automaton for the marked version of the regular expression, i.e. where all its letters are made different. Experimental results suggest that the average number of states of this automaton, and of the automaton for the unmarked regular expression, are very close to each other.

In this paper, we study the state complexities of two particular combinations of operations: catenation combined with union and catenation combined with intersection. We show that the state complexity of the former combined operation is considerably less than the mathematical composition of the state complexities of catenation and union, while the state complexity of the latter one is equal to the mathematical composition of the state complexities of catenation and intersection.

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is decidable. In 2009 this decidability problem has been solved positively in [5] by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.

In this paper, the relation between the Glushkov automaton and the partial derivative automaton of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of . Here we present a new quadratic construction of that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2. Broda et al. computed an upper bound for the ratio of the number of states of to the number of states of which is about ½ for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in , which we then use to get an average case approximation. In conclusion, assymptotically, and for large alphabets, the size of is half the size of the . This is corroborated by some experiments, even for small alphabets and small regular expressions.