{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T23:35:40Z","timestamp":1790811340218,"version":"4.1.0"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2014,12,5]],"date-time":"2014-12-05T00:00:00Z","timestamp":1417737600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>Timed and register automata are well-known models of computation over timed and data words, respectively. The former has <jats:italic>clocks<\/jats:italic> that allow to test the lapse of time between two events, whilst the latter includes <jats:italic>registers<\/jats:italic> 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.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.1017\/s0960129514000322","type":"journal-article","created":{"date-parts":[[2014,12,5]],"date-time":"2014-12-05T04:58:59Z","timestamp":1417755539000},"page":"993-1021","source":"Crossref","is-referenced-by-count":9,"title":["Relating timed and register automata"],"prefix":"10.1017","volume":"26","author":[{"given":"DIEGO","family":"FIGUEIRA","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"PIOTR","family":"HOFMAN","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u0141AWOMIR","family":"LASOTA","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,12,5]]},"reference":[{"key":"S0960129514000322_ref23","first-page":"411","article-title":"Safety metric temporal logic is fully decidable","author":"Ouaknine","year":"2006","journal-title":"TACAS"},{"key":"S0960129514000322_ref17","first-page":"381","article-title":"Safely freezing LTL","author":"Lazi\u0107","year":"2006","journal-title":"FSTTCS"},{"key":"S0960129514000322_ref10","doi-asserted-by":"crossref","unstructured":"Figueira D. , Figueira S. , Schmitz S. and Schnoebelen P. (2011) Ackermannian and primitive-recursive bounds with Dickson's lemma. In: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS), Toronto, Ontario, Canada 269\u2013278. Available at: http:\/\/doi.ieeecomputersociety.org\/10.1109\/LICS.2011.39.","DOI":"10.1109\/LICS.2011.39"},{"key":"S0960129514000322_ref18","unstructured":"Lazi\u0107 R. (2008) Safety alternating automata on data words. In: CoRR, ArXiv:0802.4237."},{"key":"S0960129514000322_ref3","article-title":"What you must remember when processing data words","author":"Benedikt","year":"2010","journal-title":"AMW"},{"key":"S0960129514000322_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"S0960129514000322_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"S0960129514000322_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_12"},{"key":"S0960129514000322_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00038-5"},{"key":"S0960129514000322_ref11","doi-asserted-by":"crossref","unstructured":"Figueira D. , Hofman P. , and Lasota S. (2010) Relating timed and register automata. In: Proceedings 17th International Workshop on Expressiveness in Concurrency, EXPRESS'10, Paris, France 61\u201375. Available at: http:\/\/dx.doi.org\/10.4204\/EPTCS.41.5.","DOI":"10.4204\/EPTCS.41.5"},{"key":"S0960129514000322_ref6","first-page":"121","article-title":"On termination for faulty channel machines","author":"Bouyer","year":"2008","journal-title":"STACS"},{"key":"S0960129514000322_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_54"},{"key":"S0960129514000322_ref21","first-page":"54","volume-title":"LICS","author":"Ouaknine","year":"2004"},{"key":"S0960129514000322_ref15","first-page":"250","article-title":"Alternating timed automata","author":"Lasota","year":"2005","journal-title":"FoSSaCS"},{"key":"S0960129514000322_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01967649"},{"key":"S0960129514000322_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/1342991.1342994"},{"key":"S0960129514000322_ref8","first-page":"205","volume-title":"LICS","author":"Chambart","year":"2008"},{"key":"S0960129514000322_ref13","volume-title":"LICS","author":"Jenkins","year":"2010"},{"key":"S0960129514000322_ref5","first-page":"355","article-title":"Automata with group actions","author":"Boja\u0144czyk","year":"2011","journal-title":"Proceedings LICS'11"},{"key":"S0960129514000322_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"S0960129514000322_ref1","first-page":"1089","article-title":"Decidability and complexity results for timed automata via channel machines","author":"Abdulla","year":"2005","journal-title":"ICALP"},{"key":"S0960129514000322_ref24","first-page":"273","article-title":"Weak alternating timed automata","author":"Parys","year":"2009","journal-title":"ICALP"},{"key":"S0960129514000322_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"S0960129514000322_ref12","first-page":"331","article-title":"Future-looking logics on data words and trees","author":"Figueira","year":"2009","journal-title":"MFCS"},{"key":"S0960129514000322_ref22","first-page":"188","volume-title":"LICS","author":"Ouaknine","year":"2005"},{"key":"S0960129514000322_ref25","unstructured":"Parys P. and Walukiewicz I. (2011) Personal communication."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129514000322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T20:06:46Z","timestamp":1555618006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129514000322\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,5]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S0960129514000322"],"URL":"https:\/\/doi.org\/10.1017\/s0960129514000322","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,5]]}}}