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.

Original languageEnglish
Title of host publicationComputer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings
EditorsRahul Santhanam, Daniil Musatov
PublisherSpringer Nature
Pages349-360
Number of pages12
ISBN (Print)9783030794156
DOIs
StatePublished - Jun 2021
Event16th International Computer Science Symposium in Russia, CSR 2021 - Sochi, Russian Federation
Duration: 28 Jun 20212 Jul 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12730 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Computer Science Symposium in Russia, CSR 2021
Country/TerritoryRussian Federation
CitySochi
Period28/06/212/07/21

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 84641633