Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion (Formula presented), deletion (Formula presented), square root (Formula presented), and the first half (Formula presented). For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires mn+2m states, as long as K is well-nested; deletion is representable with 2n states, for well-nested K; square root requires n3-O(n2) states, for well-nested L; the well-nested subset of the first half is representable with 2O(n2) states. Without the well-nestedness constraints, non-closure is established in each case.
Язык оригинала | английский |
---|---|
Название основной публикации | Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings |
Издатель | Springer Nature |
Страницы | 224-236 |
Число страниц | 13 |
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: 33857063