Descriptional complexity is the study of the conciseness of the various models representing
formal languages. The state complexity of a regular language is the size, measured by the …

We investigate the descriptional complexity of operations on finite and infinite regular
languages over unary and arbitrary alphabets. The languages are represented by …

The state complexity of basic operations on regular languages has been studied in
[9],[10],[11]. Here we focus on finite languages. We show that the catenation of two finite …

Over the last 30 years or so many results have appeared on the descriptional complexity of
machines with limited resources. Since these results have appeared in a variety of different …

The states of a finite-state automaton 𝒩 can be identified with collections of words in the
prefix closure of the regular language accepted by 𝒩. But words can be ordered, and among …

The purpose of the paper is to give an introductory survey of the main aspects and results
regarding the relative succinctness of different representations of languages, such as finite …

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 …

We study the state complexity of combined operations. Two particular combined operations
are studied: star of union and star of intersection. It is shown that the state complexity of a …

We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to
the deterministic finite automaton (DFA) conversion problem, for automata accepting …

Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to
deterministic finite automata was shown. Over the last 50 years, a vast literature …