KUNC, Michal a Alexander OKHOTIN. Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Giancarlo Mauri, Alberto Leporati. Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. Berlin: Springer, 2011, s. 324-336. ISBN 978-3-642-22320-4. Dostupné z: https://dx.doi.org/10.1007/978-3-642-22321-1_28. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{961392, author = {Kunc, Michal and Okhotin, Alexander}, address = {Berlin}, booktitle = {Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings}, doi = {http://dx.doi.org/10.1007/978-3-642-22321-1_28}, editor = {Giancarlo Mauri, Alberto Leporati}, keywords = {finite automata; two-way deterministic automata; periodicity; transformation semigroups; unary languages}, language = {eng}, location = {Berlin}, isbn = {978-3-642-22320-4}, pages = {324-336}, publisher = {Springer}, title = {Describing periodicity in two-way deterministic finite automata using transformation semigroups}, year = {2011} }
TY - JOUR ID - 961392 AU - Kunc, Michal - Okhotin, Alexander PY - 2011 TI - Describing periodicity in two-way deterministic finite automata using transformation semigroups PB - Springer CY - Berlin SN - 9783642223204 KW - finite automata KW - two-way deterministic automata KW - periodicity KW - transformation semigroups KW - unary languages 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 max{G(n-l) + l + 1 | 0 <= l <= n} states, where G(k) is the maximum order of a permutation of k elements. ER -
KUNC, Michal a Alexander OKHOTIN. Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Giancarlo Mauri, Alberto Leporati. \textit{Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings}. Berlin: Springer, 2011, s.~324-336. ISBN~978-3-642-22320-4. Dostupné z: https://dx.doi.org/10.1007/978-3-642-22321-1\_{}28.
|