Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 language | English |
|---|---|
| Title of host publication | Computer Science – Theory and Applications - 17th International Computer Science Symposium in Russia, CSR 2022, Proceedings |
| Editors | Alexander S. Kulikov, Sofya Raskhodnikova |
| Publisher | Springer Nature |
| Pages | 256-268 |
| Number of pages | 13 |
| ISBN (Print) | 9783031095733 |
| DOIs | |
| State | Published - Jun 2022 |
| Event | 17th International Computer Science Symposium in Russia, CSR 2022 - Virtual, Online Duration: 29 Jun 2022 → 1 Jul 2022 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 13296 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 17th International Computer Science Symposium in Russia, CSR 2022 |
|---|---|
| City | Virtual, Online |
| Period | 29/06/22 → 1/07/22 |
ID: 97267370