Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
 
<< 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
 
 
  Undecidability Results for Timed Automata with Silent Transitions
 
 
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   
 
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland
Toegankelijkheidsverklaring