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
Simulation is decidable for one-counter nets
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Computer Systems.
1998 (English)In: CONCUR'98 Concurrency Theory: Proceedings of the 9th International Conference, 1998, Vol. 1466, 253-268 p.Conference paper, Published paper (Refereed)
Abstract [en]

We prove that the simulation preorder is decidable for the class of one-counter nets. A one-counter net consists of a finite-state machine operating on a variable (counter) which ranges over the natural numbers. Each transition can increase or decrease the value of the counter. A transition may not be performed if this implies that the value of the counter becomes negative. The class of one-counter nets is computationally equivalent to the class of Petri nets with one unbounded place, and to the class of pushdown automata where the stack alphabet is restricted to one symbol. To our knowledge, this is the first result in the literature which gives a positive answer to the decidability of simulation preorder between pairs of processes in a class whose elements are neither finite-state nor allow finite partitioning of their state spaces.

Place, publisher, year, edition, pages
1998. Vol. 1466, 253-268 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1466
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-27328DOI: 10.1007/BFb0055627ISBN: 978-3-540-64896-3 (print)ISBN: 978-3-540-68455-8 (print)OAI: oai:DiVA.org:uu-27328DiVA: diva2:55223
Conference
CONCUR '98: Concurrency Theory, 9th International Conference, Nice, France, September 8-11, 1998
Available from: 2008-10-17 Created: 2008-10-17 Last updated: 2013-10-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Abdulla, Parosh Aziz

Search in DiVA

By author/editor
Abdulla, Parosh Aziz
By organisation
Department of Computer Systems
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 416 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