|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 9 van 9 gevonden artikelen
| Titel: |
Undecidability Results for Timed Automata with Silent Transitions |
| Auteur: |
Bouyer, Patricia Haddad, Serge Reynier, Pierre-Alain |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 92 (2009) nr. 1-2 pagina's 1-25 |
| Jaar: |
2009-06-01 |
| Inhoud: |
In this work, we study decision problems related to timed automata with silent transitions (TA_{ε}) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent transitions: can we decide whether the language recognized by a TA_{ε} can be recognized by some TA? Then we establish in the framework of TA_{ε} some old open conjectures that O. Finkel has recently solved for TA. His proofs follow a generic scheme which relies on the fact that only a finite number of configurations can be reached by a TA while reading a timed word. This property does not hold for TA_{ε}, the proofs in the framework of TA_{ε} thus require more elaborated arguments. We establish undecidability of complementability, minimization of the number of clocks, and closure under shuffle. We also show these results in the framework of infinite timed languages. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 9 van 9 gevonden artikelen
| << vorige |