Standard

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. p. 324-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6795 LNCS).

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

Harvard

Kunc, M & Okhotin, A 2011, Describing periodicity in two-way deterministic finite automata using transformation semigroups. in Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6795 LNCS, pp. 324-336, 15th International Conference on Developments in Language Theory, DLT 2011, Milan, Italy, 19/07/11. https://doi.org/10.1007/978-3-642-22321-1_28

APA

Kunc, M., & Okhotin, A. (2011). Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings (pp. 324-336). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6795 LNCS). https://doi.org/10.1007/978-3-642-22321-1_28

Vancouver

Kunc M, Okhotin A. Describing periodicity in two-way deterministic finite automata using transformation semigroups. In Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings. 2011. p. 324-336. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22321-1_28

Author

Kunc, Michal ; Okhotin, Alexander. / Describing periodicity in two-way deterministic finite automata using transformation semigroups. Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings. 2011. pp. 324-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{028451ef579e46ed9862feb02efe4fd4,
title = "Describing periodicity in two-way deterministic finite automata using transformation semigroups",
abstract = "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.",
author = "Michal Kunc and Alexander Okhotin",
year = "2011",
month = jul,
day = "29",
doi = "10.1007/978-3-642-22321-1_28",
language = "English",
isbn = "9783642223204",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "324--336",
booktitle = "Developments in Language Theory - 15th International Conference, DLT 2011, Proceedings",
note = "15th International Conference on Developments in Language Theory, DLT 2011 ; Conference date: 19-07-2011 Through 22-07-2011",

}

RIS

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