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 …

The number of states in a deterministic finite automaton (DFA) recognizing the language Lk,
where L is regular language recognized by an n-state DFA, and k⩾ 2 is a constant, is shown …

The state complexity of a regular language is the number of states of its minimal
determinitisc finite automaton. The complexity of a language operation is the complexity of …

The family of languages recognized by deterministic input-driven pushdown automata
(IDPDA; aka visibly pushdown automata, aka nested word automata) is known to be closed …

We continue the investigation of union-free regular languages that are described by regular
expressions without the union operation. We also define deterministic union-free languages …

We investigate the class of languages recognized by permutation deterministic finite
automata. Using automata constructions and some properties of permutation automata, we …

It is proved that the set of scattered substrings of a language recognized by an n-state DFA
requires a DFA with at least 2 [TeX:]^{n/2-2} states (the known upper bound is 2 [TeX:]^ n) …

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 …

The paper investigates the effect of basic language-theoretic operations on the number of
states in two-way deterministic finite automata (2DFAs). If m and n are the number of states …

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 …