Standard

On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata. / Петров, Семен Андреевич; Охотин, Александр Сергеевич.

Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings. ed. / Sang-Ki Ko; Florin Manea. Springer Nature, 2025. p. 107–122 (Lecture Notes in Computer Science; Vol. 16036 LNCS).

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

Harvard

Петров, СА & Охотин, АС 2025, On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata. in S-K Ko & F Manea (eds), Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings. Lecture Notes in Computer Science, vol. 16036 LNCS, Springer Nature, pp. 107–122, Developments in Language Theory, Сеул, Korea, Republic of, 19/08/25. https://doi.org/10.1007/978-3-032-01475-7_8

APA

Петров, С. А., & Охотин, А. С. (2025). On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata. In S-K. Ko, & F. Manea (Eds.), Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings (pp. 107–122). (Lecture Notes in Computer Science; Vol. 16036 LNCS). Springer Nature. https://doi.org/10.1007/978-3-032-01475-7_8

Vancouver

Петров СА, Охотин АС. On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata. In Ko S-K, Manea F, editors, Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings. Springer Nature. 2025. p. 107–122. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-032-01475-7_8

Author

Петров, Семен Андреевич ; Охотин, Александр Сергеевич. / On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata. Developments in Language Theory: 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings. editor / Sang-Ki Ko ; Florin Manea. Springer Nature, 2025. pp. 107–122 (Lecture Notes in Computer Science).

BibTeX

@inproceedings{4a22842c81cd4abcb8118be53250d817,
title = "On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata",
abstract = "This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least ∑k=1n(k-1)!k!nkn+1k = Ω(n2n+2/e2n) states, where nk denotes Stirling{\textquoteright}s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.",
keywords = "Two-way finite automata, state complexity, unambiguous finite automata",
author = "Петров, {Семен Андреевич} and Охотин, {Александр Сергеевич}",
year = "2025",
month = aug,
day = "16",
doi = "10.1007/978-3-032-01475-7_8",
language = "English",
isbn = "9783032014740",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "107–122",
editor = "Sang-Ki Ko and Florin Manea",
booktitle = "Developments in Language Theory",
address = "Germany",
note = "Developments in Language Theory, DLT 2025 ; Conference date: 19-08-2025 Through 22-08-2025",
url = "https://cida.uos.ac.kr/dlt2025/",

}

RIS

TY - GEN

T1 - On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata

AU - Петров, Семен Андреевич

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

N1 - Conference code: 29

PY - 2025/8/16

Y1 - 2025/8/16

N2 - This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least ∑k=1n(k-1)!k!nkn+1k = Ω(n2n+2/e2n) states, where nk denotes Stirling’s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.

AB - This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least ∑k=1n(k-1)!k!nkn+1k = Ω(n2n+2/e2n) states, where nk denotes Stirling’s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.

KW - Two-way finite automata

KW - state complexity

KW - unambiguous finite automata

UR - https://www.mendeley.com/catalogue/b4002d49-87a1-3c49-a59c-91358d96885e/

U2 - 10.1007/978-3-032-01475-7_8

DO - 10.1007/978-3-032-01475-7_8

M3 - Conference contribution

SN - 9783032014740

T3 - Lecture Notes in Computer Science

SP - 107

EP - 122

BT - Developments in Language Theory

A2 - Ko, Sang-Ki

A2 - Manea, Florin

PB - Springer Nature

T2 - Developments in Language Theory

Y2 - 19 August 2025 through 22 August 2025

ER -

ID: 140132196