Standard

State complexity of operations on two-way deterministic finite automata over a unary alphabet. / Kunc, Michal; Okhotin, Alexander.

Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings. 2011. p. 222-234 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6808 LNCS).

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

Harvard

Kunc, M & Okhotin, A 2011, State complexity of operations on two-way deterministic finite automata over a unary alphabet. in Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6808 LNCS, pp. 222-234, 13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011, Giessen/Limburg, Germany, 25/07/11. https://doi.org/10.1007/978-3-642-22600-7_18

APA

Kunc, M., & Okhotin, A. (2011). State complexity of operations on two-way deterministic finite automata over a unary alphabet. In Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings (pp. 222-234). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6808 LNCS). https://doi.org/10.1007/978-3-642-22600-7_18

Vancouver

Kunc M, Okhotin A. State complexity of operations on two-way deterministic finite automata over a unary alphabet. In Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings. 2011. p. 222-234. (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-22600-7_18

Author

Kunc, Michal ; Okhotin, Alexander. / State complexity of operations on two-way deterministic finite automata over a unary alphabet. Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings. 2011. pp. 222-234 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{8830732f351742fc92d7408f128b1547,
title = "State complexity of operations on two-way deterministic finite automata over a unary alphabet",
abstract = "The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m∈+∈n and m∈+∈n∈+∈1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m∈+∈n and 2m∈+∈n∈+∈4 states; (iii) Kleene star of an n-state 2DFA, (g(n)∈+∈O(n))2 states, where is the maximum value of lcm(p 1, ..., p k ) for , known as Landau's function; (iv) k-th power of an n-state 2DFA, between (k∈-∈1)g(n)∈-∈k and k(g(n)∈+∈n) states; (v) concatenation of an m-state and an n-state 2DFAs, states.",
author = "Michal Kunc and Alexander Okhotin",
year = "2011",
month = aug,
day = "11",
doi = "10.1007/978-3-642-22600-7_18",
language = "English",
isbn = "9783642225994",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "222--234",
booktitle = "Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings",
note = "13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011 ; Conference date: 25-07-2011 Through 27-07-2011",

}

RIS

TY - GEN

T1 - State complexity of operations on two-way deterministic finite automata over a unary alphabet

AU - Kunc, Michal

AU - Okhotin, Alexander

PY - 2011/8/11

Y1 - 2011/8/11

N2 - The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m∈+∈n and m∈+∈n∈+∈1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m∈+∈n and 2m∈+∈n∈+∈4 states; (iii) Kleene star of an n-state 2DFA, (g(n)∈+∈O(n))2 states, where is the maximum value of lcm(p 1, ..., p k ) for , known as Landau's function; (iv) k-th power of an n-state 2DFA, between (k∈-∈1)g(n)∈-∈k and k(g(n)∈+∈n) states; (v) concatenation of an m-state and an n-state 2DFAs, states.

AB - The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m∈+∈n and m∈+∈n∈+∈1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m∈+∈n and 2m∈+∈n∈+∈4 states; (iii) Kleene star of an n-state 2DFA, (g(n)∈+∈O(n))2 states, where is the maximum value of lcm(p 1, ..., p k ) for , known as Landau's function; (iv) k-th power of an n-state 2DFA, between (k∈-∈1)g(n)∈-∈k and k(g(n)∈+∈n) states; (v) concatenation of an m-state and an n-state 2DFAs, states.

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

U2 - 10.1007/978-3-642-22600-7_18

DO - 10.1007/978-3-642-22600-7_18

M3 - Conference contribution

AN - SCOPUS:79961190841

SN - 9783642225994

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

SP - 222

EP - 234

BT - Descriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings

T2 - 13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011

Y2 - 25 July 2011 through 27 July 2011

ER -

ID: 41143605