Descriptional complexity of unambiguous nested word automata

Alexander Okhotin, Kai Salomaa

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

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

Аннотация

It is known that converting an n-state nondeterministic nested word automaton (a.k.a. input-driven automaton; a.k.a. visibly pushdown automaton) to a corresponding deterministic automaton requires in the worst case 2 Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2Θ(n2) size blow-up occurs when converting a nondeterministic nested word automaton to an unambiguous one, and an unambiguous nested word automaton to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the state complexity of complementation for nondeterministic nested word automata is 2Θ(n2), and that the state complexity of homomorphism for deterministic nested word automata is 2Θ(n2).

Язык оригиналаанглийский
Название основной публикацииLanguage and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings
Страницы414-426
Число страниц13
DOI
СостояниеОпубликовано - 8 июн 2011
Событие5th International Conference on Language and Automata Theory and Applications, LATA2011 - Tarragona, Испания
Продолжительность: 26 мая 201131 мая 2011

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

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

конференция

конференция5th International Conference on Language and Automata Theory and Applications, LATA2011
СтранаИспания
ГородTarragona
Период26/05/1131/05/11

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

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

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

Цитировать