Standard

Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata. / Geffert, Viliam; Охотин, Александр Сергеевич.

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. 180–192 (Lecture Notes in Computer Science; Vol. 15981 LNCS).

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

Harvard

Geffert, V & Охотин, АС 2025, Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata. 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. 180–192, 29th International Conference on Implementation and Application of Automata, Палермо, Italy, 22/09/25. https://doi.org/10.1007/978-3-032-02602-6_13

APA

Geffert, V., & Охотин, А. С. (2025). Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata. In G. Castiglione, & S. Mantaci (Eds.), Implementation and Application of Automata: 29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings (pp. 180–192). (Lecture Notes in Computer Science; Vol. 15981 LNCS). Springer Nature. https://doi.org/10.1007/978-3-032-02602-6_13

Vancouver

Geffert V, Охотин АС. Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata. 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. 180–192. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-032-02602-6_13

Author

Geffert, Viliam ; Охотин, Александр Сергеевич. / Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata. 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. 180–192 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{13d1d21dc93c4ae4bfde95d5079c1bb6,
title = "Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata",
abstract = "It is shown that an n-state two-way nondeterministic finite automaton (2NFA) over an alphabet Σ can be transformed to a one-way automaton (1NFA) with |Σ|·n12+1 states, where n12∼34πn3n is a trinomial coefficient. A close lower bound of n12 states is given for a four-symbol alphabet. To compare, for unrestricted alphabets, this transformation is known to require 2nn+1∼1πn4n states (Kapoutsis, “Removing bidirectionality from nondeterministic finite automata”, MFCS 2005).",
keywords = "Two-way finite automata, nondeterministic finite automata, state complexity",
author = "Viliam Geffert and Охотин, {Александр Сергеевич}",
year = "2025",
month = aug,
day = "22",
doi = "10.1007/978-3-032-02602-6_13",
language = "English",
isbn = "9783032026019",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "180–192",
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 - Simulating Two-Way Nondeterministic Finite Automata Over Small Alphabets by One-Way Nondeterministic Automata

AU - Geffert, Viliam

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

N1 - Conference code: 29

PY - 2025/8/22

Y1 - 2025/8/22

N2 - It is shown that an n-state two-way nondeterministic finite automaton (2NFA) over an alphabet Σ can be transformed to a one-way automaton (1NFA) with |Σ|·n12+1 states, where n12∼34πn3n is a trinomial coefficient. A close lower bound of n12 states is given for a four-symbol alphabet. To compare, for unrestricted alphabets, this transformation is known to require 2nn+1∼1πn4n states (Kapoutsis, “Removing bidirectionality from nondeterministic finite automata”, MFCS 2005).

AB - It is shown that an n-state two-way nondeterministic finite automaton (2NFA) over an alphabet Σ can be transformed to a one-way automaton (1NFA) with |Σ|·n12+1 states, where n12∼34πn3n is a trinomial coefficient. A close lower bound of n12 states is given for a four-symbol alphabet. To compare, for unrestricted alphabets, this transformation is known to require 2nn+1∼1πn4n states (Kapoutsis, “Removing bidirectionality from nondeterministic finite automata”, MFCS 2005).

KW - Two-way finite automata

KW - nondeterministic finite automata

KW - state complexity

UR - https://www.mendeley.com/catalogue/8c241089-3870-33ef-9f98-ec0f1f883a56/

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

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

M3 - Conference contribution

SN - 9783032026019

T3 - Lecture Notes in Computer Science

SP - 180

EP - 192

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: 140132084