Standard

From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient. / Мартынова, Ольга Максимовна; Охотин, Александр Сергеевич.

Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings. ed. / Giuseppa Castiglione; Sabrina Mantaci. Springer Nature, 2025. p. 267–280 (Lecture Notes in Computer Science; Vol. 15981 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Мартынова, ОМ & Охотин, АС 2025, From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient. in G Castiglione & S Mantaci (eds), Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings. Lecture Notes in Computer Science, vol. 15981 LNCS, Springer Nature, pp. 267–280, 29th International Conference on Implementation and Application of Automata, Палермо, Italy, 22/09/25. https://doi.org/10.1007/978-3-032-02602-6_19

APA

Мартынова, О. М., & Охотин, А. С. (2025). From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient. In G. Castiglione, & S. Mantaci (Eds.), Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings (pp. 267–280). (Lecture Notes in Computer Science; Vol. 15981 LNCS). Springer Nature. https://doi.org/10.1007/978-3-032-02602-6_19

Vancouver

Мартынова ОМ, Охотин АС. From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient. In Castiglione G, Mantaci S, editors, Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings. Springer Nature. 2025. p. 267–280. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-032-02602-6_19

Author

Мартынова, Ольга Максимовна ; Охотин, Александр Сергеевич. / From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient. Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings. editor / Giuseppa Castiglione ; Sabrina Mantaci. Springer Nature, 2025. pp. 267–280 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{70e874a700bb4dcc84bdb26edacf7381,
title = "From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient",
abstract = "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.",
author = "Мартынова, {Ольга Максимовна} and Охотин, {Александр Сергеевич}",
year = "2025",
month = aug,
day = "22",
doi = "10.1007/978-3-032-02602-6_19",
language = "English",
isbn = "9783032026019",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "267–280",
editor = "Giuseppa Castiglione and Sabrina Mantaci",
booktitle = "Implementation and Application of Automata",
address = "Germany",
note = "null ; Conference date: 22-09-2025 Through 25-09-2025",
url = "https://ciaa2025.unipa.it/",

}

RIS

TY - GEN

T1 - From regular expressions to deterministic finite automata: 2^{\frac{n}{2}+\sqrt{n}(\log n)^{\Theta(1)}} states are necessary and sufficient

AU - Мартынова, Ольга Максимовна

AU - Охотин, Александр Сергеевич

N1 - Conference code: 29

PY - 2025/8/22

Y1 - 2025/8/22

N2 - 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.

AB - 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.

UR - https://www.mendeley.com/catalogue/2a97a52c-730b-3b32-b0af-07932ee62583/

U2 - 10.1007/978-3-032-02602-6_19

DO - 10.1007/978-3-032-02602-6_19

M3 - Conference contribution

SN - 9783032026019

T3 - Lecture Notes in Computer Science

SP - 267

EP - 280

BT - Implementation and Application of Automata

A2 - Castiglione, Giuseppa

A2 - Mantaci, Sabrina

PB - Springer Nature

Y2 - 22 September 2025 through 25 September 2025

ER -

ID: 140131868