Descriptional complexity of input-driven pushdown automata

Alexander Okhotin, Xiaoxue Piao, Kai Salomaa

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

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

Аннотация

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) can be determinized. Alur and Madhusudan (Adding nesting structure to words, J.ACM 56(3), 2009) showed that a deterministic IDPDA simulating a nondeterministic IDPDA with n states and stack symbols may need, in the worst case, states. In their construction, the equivalent deterministic IDPDA does, in fact, not need to use the stack. This paper considers the size blow-up of determinization in more detail, and gives a lower bound construction, that is tight within a multiplicative constant, with respect to the size of the nondeterministic automaton both for the number of states and the number of stack symbols. The paper also surveys the recent results on operational state complexity of IDPDAs, and on the cost of converting a nondeterministic automaton to an unambiguous one, and an unambiguous automaton to a deterministic one.

Язык оригиналаанглийский
Название основной публикацииLanguages Alive
Подзаголовок основной публикацииEssays Dedicated to Jurgen Dassow on the Occasion of His 65th Birthday
РедакторыHenning Bordihn, Martin Kutrib, Bianca Truthe
Страницы186-206
Число страниц21
DOI
СостояниеОпубликовано - 8 окт 2012

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

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

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

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

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

Цитировать