DOI

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings
РедакторыAlexander S. Kulikov, Sofya Raskhodnikova
ИздательSpringer Nature
Страницы256-268
Число страниц13
ISBN (печатное издание)9783031095733
DOI
СостояниеОпубликовано - июн 2022
Событие17th International Computer Science Symposium in Russia, CSR 2022 - Virtual, Online
Продолжительность: 29 июн 20221 июл 2022

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

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

конференция

конференция17th International Computer Science Symposium in Russia, CSR 2022
ГородVirtual, Online
Период29/06/221/07/22

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

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

ID: 97267370