Most complex deterministic union-free regular languages

DOI10.1007/978-3-319-94631-3_4zbMATH Open1435.68150arXiv1711.09149OpenAlexW2964270270MaRDI QIDQ777986FDOQ777986

Sylvie Davies, Janusz Brzozowski

Publication date: 30 June 2020

Abstract: A regular language $L$ is union-free if it can be represented by a regular expression without the union operation. A union-free language is deterministic if it can be accepted by a deterministic one-cycle-free-path finite automaton; this is an automaton which has one final state and exactly one cycle-free path from any state to the final state. Jir'askov'a and Masopust proved that the state complexities of the basic operations reversal, star, product, and boolean operations in deterministic union-free languages are exactly the same as those in the class of all regular languages. To prove that the bounds are met they used five types of automata, involving eight types of transformations of the set of states of the automata. We show that for each $nge3$ there exists one ternary witness of state complexity $n$ that meets the bound for reversal and product. Moreover, the restrictions of this witness to binary alphabets meet the bounds for star and boolean operations. We also show that the tight upper bounds on the state complexity of binary operations that take arguments over different alphabets are the same as those for arbitrary regular languages. Furthermore, we prove that the maximal syntactic semigroup of a union-free language has $n^n$ elements, as in the case of regular languages, and that the maximal state complexities of atoms of union-free languages are the same as those for regular languages. Finally, we prove that there exists a most complex union-free language that meets the bounds for all these complexity measures. Altogether this proves that the complexity measures above cannot distinguish union-free languages from regular languages.

Full work available at URL: https://arxiv.org/abs/1711.09149

zbMATH Keywords

regular languagetransition semigroupstate complexityreversalBoolean operationsyntactic semigroupdifferent alphabetsone-cycle-free-path automatonunion-free language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (8)

• Complexity in Union-Free Regular Languages
• Union-complexities of Kleene plus operation
• Operational union-complexity
• Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages
• In Search of Most Complex Regular Languages
• On Union-Free and Deterministic Union-Free Languages
• Most Complex Regular Right-Ideal Languages
• Complexity in union-free regular languages

This page was built for publication: Most complex deterministic union-free regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777986)