uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
R-automata
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2008 (English)In: CONCUR 2008 - Concurrency Theory / [ed] VanBreugel F; Chechik M, Berlin: Springer-Verlag , 2008, 67-81 p.Conference paper, Published paper (Refereed)
Abstract [en]

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 [12] - 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.
Series
Lecture Notes in Computer Science, 5201
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-103917DOI: 10.1007/978-3-540-85361-9_9ISI: 000259487000005ISBN: 978-3-540-85360-2 (print)OAI: oai:DiVA.org:uu-103917DiVA: diva2:219028
Conference
19th International Conference on Concurrency Theory Toronto, CANADA, AUG 19-22, 2008
Available from: 2009-05-26 Created: 2009-05-26 Last updated: 2011-03-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh AzizKrcal, PavelYi, Wang

Search in DiVA

By author/editor
Abdulla, Parosh AzizKrcal, PavelYi, Wang
By organisation
Computer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 495 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf