Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Describing periodicity in two-way deterministic finite automata using transformation semigroups. / Kunc, Michal; Okhotin, Alexander.
Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings. 2011. стр. 324-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6795 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Describing periodicity in two-way deterministic finite automata using transformation semigroups
AU - Kunc, Michal
AU - Okhotin, Alexander
PY - 2011/7/29
Y1 - 2011/7/29
N2 - A framework for the study of periodic behaviour of two-way deterministic finite automata (2DFA) is developed. Computations of 2DFAs are represented by a two-way analogue of transformation semigroups, every element of which describes the behaviour of a 2DFA on a certain string x. A subsemigroup generated by this element represents the behaviour on strings in x +. The main contribution of this paper is a description of all such monogenic subsemigroups up to isomorphism. This characterization is then used to show that transforming an n-state 2DFA over a one-letter alphabet to an equivalent sweeping 2DFA requires exactly n+1 states, and transforming it to a one-way automaton requires exactly states, where G(k) is the maximum order of a permutation of k elements.
AB - A framework for the study of periodic behaviour of two-way deterministic finite automata (2DFA) is developed. Computations of 2DFAs are represented by a two-way analogue of transformation semigroups, every element of which describes the behaviour of a 2DFA on a certain string x. A subsemigroup generated by this element represents the behaviour on strings in x +. The main contribution of this paper is a description of all such monogenic subsemigroups up to isomorphism. This characterization is then used to show that transforming an n-state 2DFA over a one-letter alphabet to an equivalent sweeping 2DFA requires exactly n+1 states, and transforming it to a one-way automaton requires exactly states, where G(k) is the maximum order of a permutation of k elements.
UR - http://www.scopus.com/inward/record.url?scp=79960742191&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22321-1_28
DO - 10.1007/978-3-642-22321-1_28
M3 - Conference contribution
AN - SCOPUS:79960742191
SN - 9783642223204
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 324
EP - 336
BT - Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings
T2 - 15th International Conference on Developments in Language Theory, DLT 2011
Y2 - 19 July 2011 through 22 July 2011
ER -
ID: 41142716