DOI

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.
Язык оригиналаанглийский
Название основной публикацииImplementation and Application of Automata
Подзаголовок основной публикации29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings
РедакторыGiuseppa Castiglione, Sabrina Mantaci
ИздательSpringer Nature
Страницы267–280
Число страниц14
ISBN (печатное издание)9783032026019
DOI
СостояниеОпубликовано - 22 авг 2025
Событие29th International Conference on Implementation and Application of Automata - Палермо, Италия
Продолжительность: 22 сен 202525 сен 2025
Номер конференции: 29
https://ciaa2025.unipa.it/

Серия публикаций

НазваниеLecture Notes in Computer Science
Том15981 LNCS

конференция

конференция29th International Conference on Implementation and Application of Automata
Сокращенное названиеCIAA 2025
Страна/TерриторияИталия
ГородПалермо
Период22/09/2525/09/25
Сайт в сети Internet

ID: 140131868