|
| << previous |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 9 of 9 found articles
| Title: |
Undecidability Results for Timed Automata with Silent Transitions |
| Author: |
Bouyer, Patricia Haddad, Serge Reynier, Pierre-Alain |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 92 (2009) nr. 1-2 pages 1-25 |
| Year: |
2009-06-01 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 9 of 9 found articles
| << previous |