Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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 июн 2022 → 1 июл 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/22 → 1/07/22 |
ID: 97267370