Abstract / Description of output
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with only a weak test for zero. We show that weak simulation preorder is decidable for OCN and that weak simulation approximants do not converge at level ω, but only at ω2. In contrast, other semantic relations like weak bisimulation are undecidable for OCN [1], and so are weak (and strong) trace inclusion (Sec. VII).
| Original language | English |
|---|---|
| Title of host publication | Logic in Computer Science (LICS), 2013 28th Annual IEEE/ACM Symposium on |
| Publisher | Institute of Electrical and Electronics Engineers |
| Pages | 203-212 |
| Number of pages | 10 |
| ISBN (Print) | 978-1-4799-0413-6 |
| DOIs | |
| Publication status | Published - 2013 |
Keywords / Materials (for Non-textual outputs)
- Petri nets
- automata theory
- bisimulation equivalence
- decidability
- OCN
- one-counter automata
- one-counter nets
- semantic relations
- weak bisimulation
- weak simulation decidability
- weak simulation preorder
- weak test
- weak trace inclusion
- Automata
- Computational modeling
- Educational institutions
- Games
- Model checking
- Radiation detectors
- Semantics
- Automata theory
- One-counter machines