It is proved that every regular expression of alphabetic width n, that is, with n occurrences of symbols of the alphabet, can be transformed into a deterministic finite automaton (DFA) with at most 2n2+(log2e22+o(1))nlnn states recognizing the same language (the best upper bound up to date is 2n). At the same time, it is also shown that this bound is close to optimal, namely, that there exist regular expressions of alphabetic width n over a two-symbol alphabet, such that every DFA for the same language has at least 2n2+(2+o(1))nlnn states (the previously known lower bound is 542n2). The same bounds are obtained for an intermediate problem of determinizing nondetermistic finite automata (NFA) with each state having all incoming transitions by the same symbol.
Original languageEnglish
Title of host publicationImplementation and Application of Automata
Subtitle of host publication29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings
EditorsGiuseppa Castiglione, Sabrina Mantaci
PublisherSpringer Nature
Pages267–280
Number of pages14
ISBN (Print)9783032026019
DOIs
StatePublished - 22 Aug 2025
Event29th International Conference on Implementation and Application of Automata - Палермо, Italy
Duration: 22 Sep 202525 Sep 2025
Conference number: 29
https://ciaa2025.unipa.it/

Publication series

NameLecture Notes in Computer Science
Volume15981 LNCS

Conference

Conference29th International Conference on Implementation and Application of Automata
Abbreviated titleCIAA 2025
Country/TerritoryItaly
CityПалермо
Period22/09/2525/09/25
Internet address

ID: 140131868