Descriptional complexity of unambiguous input-driven pushdown automata

Alexander Okhotin, Kai Salomaa

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

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

Аннотация

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2Θ(n2) states (B. von Braunmühl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2Θ(n2) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2Θ(n2), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2Θ(n2).

Язык оригиналаанглийский
Страницы (с-по)1-11
Число страниц11
ЖурналTheoretical Computer Science
Том566
Номер выпускаC
DOI
СостояниеОпубликовано - 1 янв 2015

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

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

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

Цитировать