2008 (English)In: CONCUR 2008 - Concurrency Theory / [ed] VanBreugel F; Chechik M, Berlin: Springer-Verlag , 2008, 67-81 p.Conference paper (Refereed)
We introduce R-automata - finite state machines which operate on a finite number of unbounded counters. The values of the counters can be incremented, reset to zero, or left unchanged along the transitions. R-automata can be, for example, used to model systems with resources (modeled by the counters) which are consumed in small parts but which can be replenished at once. We define the language accepted by an R-automaton relative to a natural number D as the set of words allowing a run along which no counter value exceeds D. As the main result, we show decidability of the universality problem, i.e., the problem whether there is a number D such that the corresponding language is universal. We present a proof based on finite monoids and the factorization forest theorem. This theorem was applied for distance automata in  - a special case of R-automata with one counter which is never reset. As a second technical contribution, we extend the decidability result to R-automata with Buchi acceptance conditions.
Place, publisher, year, edition, pages
Berlin: Springer-Verlag , 2008. 67-81 p.
, Lecture Notes in Computer Science, 5201
IdentifiersURN: urn:nbn:se:uu:diva-103917DOI: 10.1007/978-3-540-85361-9_9ISI: 000259487000005ISBN: 978-3-540-85360-2OAI: oai:DiVA.org:uu-103917DiVA: diva2:219028
19th International Conference on Concurrency Theory Toronto, CANADA, AUG 19-22, 2008