Automata with Timers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909124214652928 |
|---|---|
| author | Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan Vaandrager, Frits W. |
| author_facet | Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan Vaandrager, Frits W. |
| contents | In this work, we study properties of deterministic finite-state automata with timers, a subclass of timed automata proposed by Vaandrager et al. as a candidate for an efficiently learnable timed model. We first study the complexity of the configuration reachability problem for such automata and establish that it is PSPACE-complete. Then, as simultaneous timeouts (we call these, races) can occur in timed runs of such automata, we study the problem of determining whether it is possible to modify the delays between the actions in a run, in a way to avoid such races. The absence of races is important for modelling purposes and to streamline learning of automata with timers. We provide an effective characterization of when an automaton is race-avoiding and establish that the related decision problem is in 3EXP and PSPACE-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_07451 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Automata with Timers Bruyère, Véronique Pérez, Guillermo A. Staquet, Gaëtan Vaandrager, Frits W. Formal Languages and Automata Theory F.4.3 In this work, we study properties of deterministic finite-state automata with timers, a subclass of timed automata proposed by Vaandrager et al. as a candidate for an efficiently learnable timed model. We first study the complexity of the configuration reachability problem for such automata and establish that it is PSPACE-complete. Then, as simultaneous timeouts (we call these, races) can occur in timed runs of such automata, we study the problem of determining whether it is possible to modify the delays between the actions in a run, in a way to avoid such races. The absence of races is important for modelling purposes and to streamline learning of automata with timers. We provide an effective characterization of when an automaton is race-avoiding and establish that the related decision problem is in 3EXP and PSPACE-hard. |
| title | Automata with Timers |
| topic | Formal Languages and Automata Theory F.4.3 |
| url | https://arxiv.org/abs/2305.07451 |