Standard

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. стр. 188-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10952 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Jirásková, G & Okhotin, A 2018, State complexity of unambiguous operations on deterministic finite automata. в Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 10952 LNCS, Springer Nature, стр. 188-199, 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018, Halifax, Канада, 25/07/18. https://doi.org/10.1007/978-3-319-94631-3_16

APA

Jirásková, G., & Okhotin, A. (2018). State complexity of unambiguous operations on deterministic finite automata. в Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings (стр. 188-199). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10952 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-94631-3_16

Vancouver

Jirásková G, Okhotin A. State complexity of unambiguous operations on deterministic finite automata. в Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature. 2018. стр. 188-199. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-94631-3_16

Author

Jirásková, Galina ; Okhotin, Alexander. / State complexity of unambiguous operations on deterministic finite automata. Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings. Springer Nature, 2018. стр. 188-199 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{355b79d266854550be9e85bdcc3cbf39,
title = "State complexity of unambiguous operations on deterministic finite automata",
abstract = "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.",
author = "Galina Jir{\'a}skov{\'a} and Alexander Okhotin",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-94631-3_16",
language = "English",
isbn = "9783319946306",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "188--199",
booktitle = "Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings",
address = "Germany",
note = "20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 ; Conference date: 25-07-2018 Through 27-07-2018",

}

RIS

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