A timed extension of input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) under the event-clock model was introduced by Nguyen and Ogawa (“Event-clock visibly pushdown automata”, 2009), who showed that this model can be determinized using the method of region construction. This paper proposes a new, direct determinization procedure for these automata: an n-state nondeterministic automaton with k different clock constraints is transformed to a deterministic automaton with 2n2 states, 2n2+k stack symbols and the same clock constraints as in the original automaton. The construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.

Original languageEnglish
Title of host publicationComputer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings
EditorsAlexander S. Kulikov, Sofya Raskhodnikova
PublisherSpringer Nature
Pages256-268
Number of pages13
ISBN (Print)9783031095733
DOIs
StatePublished - Jun 2022
Event17th International Computer Science Symposium in Russia, CSR 2022 - Virtual, Online
Duration: 29 Jun 20221 Jul 2022

Publication series

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

Conference

Conference17th International Computer Science Symposium in Russia, CSR 2022
CityVirtual, Online
Period29/06/221/07/22

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • determinization, input-driven pushdown automata, state complexity, Timed systems, visibly pushdown automata

ID: 97267370