Input-driven pushdown automata with limited nondeterminism (Invited Paper)

Alexander Okhotin, Kai Salomaa

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

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

Аннотация

It is known that determinizing a nondeterministic input-driven pushdown automaton (NIDPDA) of size n results in the worst case in a machine of size (R. Alur, P. Madhusudan, "Adding nesting structure to words", J.ACM 56(3), 2009). This paper considers the special case of k-path NIDPDAs, which have at most k computations on any input. It is shown that the smallest deterministic IDPDA equivalent to a k-path NIDPDA of size n is of size Θ(n k ). The paper also gives an algorithm for deciding whether or not a given NIDPDA has the k-path property, for a given k; if k is fixed, the problem is P-complete.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 18th International Conference, DLT 2014, Proceedings
ИздательSpringer Nature
Страницы84-102
Число страниц19
ISBN (печатное издание)9783319096971
DOI
СостояниеОпубликовано - 1 янв 2014
Событие18th International Conference on Developments in Language Theory, DLT 2014 - Ekaterinburg, Российская Федерация
Продолжительность: 26 авг 201429 авг 2014

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

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

конференция

конференция18th International Conference on Developments in Language Theory, DLT 2014
СтранаРоссийская Федерация
ГородEkaterinburg
Период26/08/1429/08/14

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

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

Fingerprint Подробные сведения о темах исследования «Input-driven pushdown automata with limited nondeterminism (Invited Paper)». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать