Nicolas Markey

Résumé

In this paper, we improve two recent undecidability results of Brihaye, Bruyère and Raskin about weighted timed automata, an extension of timed automata with a cost variable. Our results rely on a new encoding of the two counters of a Minsky machine that only require three clocks and one stopwatch cost, while previous reductions required five clocks and one stopwatch cost.

@article{ipl98(5)-BBM,
  author =              {Bouyer, Patricia and Brihaye, {\relax Th}omas and
                         Markey, Nicolas},
  title =               {Improved Undecidability Results on Weighted Timed
                         Automata},
  publisher =           {Elsevier},
  journal =             {Information Processing Letters},
  volume =              {98},
  number =              {5},
  pages =               {188-194},
  year =                {2006},
  month =               jun,
  doi =                 {10.1016/j.ipl.2006.01.012},
  abstract =            {In this paper, we improve two recent undecidability
                         results of Brihaye, Bruy{\`e}re and Raskin about
                         weighted timed automata, an extension of timed
                         automata with a cost variable. Our results rely on a
                         new encoding of the two counters of a Minsky machine
                         that only require three clocks and one stopwatch
                         cost, while previous reductions required five clocks
                         and one stopwatch cost.},
}