Selected publications at LSV: 1999

BP99
Patricia Bouyer et Antoine Petit.  Decomposition and Composition of Timed Automata.  In ICALP'99, LNCS 1644, pages 210-219. Springer, 1999. ( PS | PS.GZ )
Résumé:
We propose in this paper a decomposition theorem for the timed automata introduced by Alur and Dill. To this purpose, we define a new simple and natural concatenation operation, indexed by the set of clocks to be reset, on timed automata generalizing the classical untimed concatenation.
    Then we extend the famous Kleene's and Büchi's theorems on classical untimed automata by simply changing the basic objects to take time into account, keeping the union operation and replacing the concatenation, finite and infinite iterations by the new timed concatenations and their induced iterations.
    Thus, and up to our knowledge, our result provides the simplest known algebraic characterization of recognizable timed languages.

@inproceedings{PB-AP-icalp99,
   address = {Prague, Czech Republic},
   author = {Bouyer, Patricia and Petit, Antoine},
   booktitle = {{P}roceedings of the 26th {I}nternational {C}olloquium on {A}utomata, {L}anguages and {P}rogramming ({ICALP}'99)},
   editor = {Wiedermann, Jir{\'i} and van Emde Boas, Peter and Nielsen, Mogens},
   month = jul,
   pages = {210-219},
   publisher = {Springer},
   series = {Lecture Notes in Computer Science},
   title = {Decomposition and Composition of Timed Automata},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PS/BP-icalp99.ps},
   volume = {1644},
   year = {1999},
}

À propos du LSV