Further closure properties of input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

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

1 Цитирования (Scopus)

Аннотация

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 июл 201827 июл 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
СтранаКанада
ГородHalifax
Период25/07/1827/07/18

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Further closure properties of input-driven pushdown automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать