Synchronizing Words for Weighted and Timed Automata

Doyen, Laurent; Juhl, Line; Larsen, Kim G.; Markey, Nicolas; Shirmohammadi, Mahsa

doi:10.4230/LIPIcs.FSTTCS.2014.121

File

LIPIcs.FSTTCS.2014.121.pdf

Filesize: 0.51 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2014.121
URN: urn:nbn:de:0030-drops-48370

Author Details

Laurent Doyen

Line Juhl

Kim G. Larsen

Nicolas Markey

Mahsa Shirmohammadi

Cite AsGet BibTex

Laurent Doyen, Line Juhl, Kim G. Larsen, Nicolas Markey, and Mahsa Shirmohammadi. Synchronizing Words for Weighted and Timed Automata. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 121-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.121

Abstract

The problem of synchronizing automata is concerned with the existence of a word that sends all states of 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. 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.

Keywords

Synchronizing words
weighted automata
timed automata

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Rajeev Alur and David L. Dill. A theory of timed automata. TCS, 126(2):183-235, 1994.
Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, and E. Shapiro. DNA molecule provides a computing machine with both data and fuel. National Acad. Sci. USA, 100:2191-2196, 2003.
Ján Černý. Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny časopis, 14(3):208-216, 1964.
L. Doyen, T. Massart, and M. Shirmohammadi. Infinite synchronizing words for probabilistic automata. In Proc. of MFCS, LNCS 6907, pages 278-289. Springer, 2011.
Laurent Doyen, Line Juhl, Kim G. Larsen, Nicolas Markey, and Mahsa Shirmohammadi. Synchronizing words for timed and weighted automata. Research Report LSV-13-15, Laboratoire Spécification et Vérification, ENS Cachan, France, October 2013. 23 pages.
F. M. Fominykh and M. V. Volkov. P(l)aying for synchronization. In Nelma Moreira and Rogério Reis, editors, CIAA'12, volume 7381 of LNCS, pages 159-170. Springer, 2012.
P. V. Martyugin. Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. In Farid M. Ablayev and Ernst W. Mayr, editors, CSR'10, volume 6072 of LNCS, pages 288-302. Springer, 2010.
M. V. Volkov. Synchronizing automata and the Černý conjecture. In LATA'08, volume 5196 of LNCS, pages 11-27. Springer, 2008.