zbMATH — the first resource for mathematics

Relating timed and register automata. (English) Zbl 1362.68138
Summary: Timed and register automata are well-known models of computation over timed and data words, respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave differently in appearance, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance.
This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton over ordered data domain, and conversely that a run of a register automaton can be simulated by a timed automaton. These are exponential time reductions hold both in the finite and infinite words settings. Our results allow to transfer decidability results back and forth between these two kinds of models, as well complexity results modulo an exponential time reduction. We justify the usefulness of these reductions by obtaining new results on register automata.

68Q45 Formal languages and automata
Full Text: DOI
[1] DOI: 10.1007/BF01967649 · Zbl 0211.31205 · doi:10.1007/BF01967649
[2] DOI: 10.1145/1013560.1013562 · Zbl 1367.68175 · doi:10.1145/1013560.1013562
[3] ACM Transactions on Computational Logic (TOCL) 9 (2008)
[4] FoSSaCS pp 250– (2005)
[5] ACM Transactions on Computational Logic (TOCL) 10 (2009)
[6] DOI: 10.1016/0304-3975(94)90242-9 · Zbl 0938.68711 · doi:10.1016/0304-3975(94)90242-9
[7] LICS pp 205– (2008)
[8] LICS (2010)
[9] DOI: 10.1016/S0890-5401(03)00038-5 · Zbl 1028.68080 · doi:10.1016/S0890-5401(03)00038-5
[10] MFCS pp 331– (2009)
[11] STACS pp 121– (2008)
[12] Proceedings LICS’11 pp 355– (2011)
[13] DOI: 10.1007/978-3-642-31585-5_12 · Zbl 1367.68159 · doi:10.1007/978-3-642-31585-5_12
[14] AMW (2010)
[15] DOI: 10.1016/0304-3975(94)90010-8 · Zbl 0803.68071 · doi:10.1016/0304-3975(94)90010-8
[16] ICALP pp 1089– (2005)
[17] DOI: 10.1007/978-3-642-15155-2_54 · Zbl 1287.68059 · doi:10.1007/978-3-642-15155-2_54
[18] ICALP pp 273– (2009)
[19] TACAS pp 411– (2006)
[20] LICS pp 188– (2005)
[21] LICS pp 54– (2004)
[22] FSTTCS pp 381– (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.