Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
State complexity of unambiguous operations on deterministic finite automata. / Jirásková, Galina; Okhotin, Alexander.
Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, 2018. p. 188-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10952 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - State complexity of unambiguous operations on deterministic finite automata
AU - Jirásková, Galina
AU - Okhotin, Alexander
PY - 2018/1/1
Y1 - 2018/1/1
N2 - The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn - 1 for the unambiguous concatenation, it is known to be m2n-1 - 2n-2 (Daley et al. “Orthogonal concatenation: Language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3/8 2n+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.
AB - The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn - 1 for the unambiguous concatenation, it is known to be m2n-1 - 2n-2 (Daley et al. “Orthogonal concatenation: Language equations and state complexity”, J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3/8 2n+1. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m + n-2, and unambiguous star requires n-2 states in the worst case.
UR - http://www.scopus.com/inward/record.url?scp=85050610342&partnerID=8YFLogxK
UR - http://www.mendeley.com/research/state-complexity-unambiguous-operations-deterministic-finite-automata
U2 - 10.1007/978-3-319-94631-3_16
DO - 10.1007/978-3-319-94631-3_16
M3 - Conference contribution
AN - SCOPUS:85050610342
SN - 9783319946306
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 188
EP - 199
BT - Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings
PB - Springer Nature
T2 - 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018
Y2 - 25 July 2018 through 27 July 2018
ER -
ID: 33856917