Standard

On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. / Петров, Семен Андреевич; Okhotin, Alexander.

Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. ред. / Alberto Leporati; Carlos Martín-Vide; Dana Shapira; Claudio Zandron. Springer Nature, 2021. стр. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12638 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Петров, СА & Okhotin, A 2021, On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. в A Leporati, C Martín-Vide, D Shapira & C Zandron (ред.), Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 12638 LNCS, Springer Nature, стр. 81-93, 15th International Conference on Language and Automata Theory and Applications, LATA 2021, Milan, Италия, 1/03/21. https://doi.org/10.1007/978-3-030-68195-1_7

APA

Петров, С. А., & Okhotin, A. (2021). On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. в A. Leporati, C. Martín-Vide, D. Shapira, & C. Zandron (Ред.), Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings (стр. 81-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12638 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-68195-1_7

Vancouver

Петров СА, Okhotin A. On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. в Leporati A, Martín-Vide C, Shapira D, Zandron C, Редакторы, Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. Springer Nature. 2021. стр. 81-93. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-68195-1_7

Author

Петров, Семен Андреевич ; Okhotin, Alexander. / On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata. Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. Редактор / Alberto Leporati ; Carlos Martín-Vide ; Dana Shapira ; Claudio Zandron. Springer Nature, 2021. стр. 81-93 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{c40f008cccae43f5b3e4bff12cb8f5bc,
title = "On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata",
abstract = "The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.",
keywords = "Descriptional complexity, Two-way finite automata, Unambiguous finite automata",
author = "Петров, {Семен Андреевич} and Alexander Okhotin",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 15th International Conference on Language and Automata Theory and Applications, LATA 2021 ; Conference date: 01-03-2021 Through 05-03-2021",
year = "2021",
month = feb,
doi = "10.1007/978-3-030-68195-1_7",
language = "English",
isbn = "9783030681944",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "81--93",
editor = "Alberto Leporati and Carlos Mart{\'i}n-Vide and Dana Shapira and Claudio Zandron",
booktitle = "Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings",
address = "Germany",

}

RIS

TY - GEN

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

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

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/2

Y1 - 2021/2

N2 - The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.

AB - The paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA). It is proved that a 2DFA with n states can be transformed to a UFA with fewer than 2n· n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((42)n·n-1/2) states. The latter result is proved by estimating the rank of a certain matrix.

KW - Descriptional complexity

KW - Two-way finite automata

KW - Unambiguous finite automata

UR - http://www.scopus.com/inward/record.url?scp=85104419404&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/f8549224-1e18-31a8-ad79-829adc62dcb3/

U2 - 10.1007/978-3-030-68195-1_7

DO - 10.1007/978-3-030-68195-1_7

M3 - Conference contribution

AN - SCOPUS:85104419404

SN - 9783030681944

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 93

BT - Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings

A2 - Leporati, Alberto

A2 - Martín-Vide, Carlos

A2 - Shapira, Dana

A2 - Zandron, Claudio

PB - Springer Nature

T2 - 15th International Conference on Language and Automata Theory and Applications, LATA 2021

Y2 - 1 March 2021 through 5 March 2021

ER -

ID: 78911685