DOI

Automata operating on strings of nested brackets, known as input-driven pushdown automata, and also as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan (“Visibly pushdown languages”, STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding ω -languages in terms of classical ω -regular languages and input-driven pushdown automata on finite strings. This characterization leads to a determinization construction for these automata, as well as to the first results on their topological classification.

Язык оригиналаанглийский
Название основной публикацииComputer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings
РедакторыRahul Santhanam, Daniil Musatov
ИздательSpringer Nature
Страницы349-360
Число страниц12
ISBN (печатное издание)9783030794156
DOI
СостояниеОпубликовано - июн 2021
Событие16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, Российская Федерация
Продолжительность: 28 июн 20212 июл 2021

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

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

конференция

конференция16th International Computer Science Symposium in Russia, CSR 2021
Страна/TерриторияРоссийская Федерация
ГородSochi
Период28/06/212/07/21

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

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

ID: 84641633