D | |
---|---|
[DJL+14] | Laurent Doyen,
Line Juhl,
Kim Guldstrand Larsen,
Nicolas Markey, and
Mahsa Shirmohammadi.
Synchronizing words for weighted and timed automata.
In FSTTCS'14,
Leibniz International Proceedings in Informatics 29, pages 121-132. Leibniz-Zentrum für Informatik, December 2014.
@inproceedings{fsttcs2014-DJLMS, author = {Doyen, Laurent and Juhl, Line and Larsen, Kim Guldstrand and Markey, Nicolas and Shirmohammadi, Mahsa}, title = {Synchronizing words for weighted and timed automata}, editor = {Raman, Venkatesh and Suresh, S. P.}, booktitle = {{P}roceedings of the 34th {C}onference on {F}oundations of {S}oftware {T}echnology and {T}heoretical {C}omputer {S}cience ({FSTTCS}'14)}, acronym = {{FSTTCS}'14}, publisher = {Leibniz-Zentrum f{\"u}r Informatik}, series = {Leibniz International Proceedings in Informatics}, volume = {29}, pages = {121-132}, year = {2014}, month = dec, doi = {10.4230/LIPIcs.FSTTCS.2014.121}, abstract = {The problem of synchronizing automata is concerned with the existence of a word that sends all states ofM the automaton to one and the same state. This problem has classically been studied for complete deterministic finite automata, with the existence problem being NLOGSPACE-complete.\par In this paper we consider synchronizing-word problems for weighted and timed automata. We consider the synchronization problem in several variants and combinations of these, including deterministic and non-deterministic timed and weighted automata, synchronization to unique location with possibly different clock valuations or accumulated weights, as well as synchronization with a safety condition forbidding the automaton to visit states outside a safety-set during synchronization (e.g. energy constraints). For deterministic weighted automata, the synchronization problem is proven PSPACE-complete under energy constraints, and in 3-EXPSPACE under general safety constraints. For timed automata the synchronization problems are shown to be PSPACE-complete in the deterministic case, and undecidable in the non-deterministic case.}, } |
- 1
- 1
- 1
- 1
- 1