Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings |
Издатель | Springer Nature |
Страницы | 188-199 |
Число страниц | 12 |
ISBN (печатное издание) | 9783319946306 |
DOI | |
Состояние | Опубликовано - 1 янв 2018 |
Событие | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax, Канада Продолжительность: 25 июл 2018 → 27 июл 2018 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 10952 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 |
---|---|
Страна/Tерритория | Канада |
Город | Halifax |
Период | 25/07/18 → 27/07/18 |
ID: 33856917