State complexity of operations on input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

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

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

Аннотация

The family of deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ("Visibly pushdown languages", STOC 2004), the reversal and the Kleene star of an n-state IDPDA can be represented by an IDPDA 2O(n2) with states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ(n log n) states, as well as an m 2 Θ(n log n)-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.

Язык оригиналаанглийский
Название основной публикацииMathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings
Страницы485-496
Число страниц12
DOI
СостояниеОпубликовано - 2011
Опубликовано для внешнего пользованияДа
Событие36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011 - Warsaw, Польша
Продолжительность: 22 авг 201126 авг 2011

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

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

конференция

конференция36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011
СтранаПольша
ГородWarsaw
Период22/08/1126/08/11

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

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

Fingerprint

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

Цитировать