Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata

Galina Jirásková, Alexander Okhotin

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

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

Аннотация

The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an n-state automaton is exactly if all inputs are assumed to be well-nested, and between and (formula presented) without this restriction, cf. (formula presented) in the literature. For the concatenation of an m-state and an n-state IDPDA, the new lower bound is which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between and Finally, it is proved that transforming an n-state nondeterministic IDPDA to a deterministic one requires exactly states, cf. in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 22nd International Conference, DLT 2018, Proceedings
РедакторыMizuho Hoshi, Shinnosuke Seki
ИздательSpringer Nature
Страницы441-452
Число страниц12
ISBN (печатное издание)9783319986531
DOI
СостояниеОпубликовано - 1 янв 2018
Событие22nd International Conference on Developments in Language Theory, DLT 2018 - Tokyo, Япония
Продолжительность: 10 сен 201814 сен 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11088 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция22nd International Conference on Developments in Language Theory, DLT 2018
СтранаЯпония
ГородTokyo
Период10/09/1814/09/18

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

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

Fingerprint Подробные сведения о темах исследования «Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать