Pushdown automata, multiset automata, and Petri nets

In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpret...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001, Vol.256 (1), p.3-21
Main Authors: Hirshfeld, Yoram, Moller, Faron
Format: Article
Language:English
Subjects:
Automata
Bisimulation
Concurrency
Petri nets
Rewrite systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpreting concatenation as parallel composition. In this way, we provide natural definitions for commutative (parallel) context-free automata, multiset (parallel, or random access, pushdown) automata, and Petri nets. We provide example automata which demonstrate the strictness of this hierarchy. In particular, we provide a proof of an earlier conjecture by Moller: that multiset automata form a proper subset of Petri nets. This result contrasts with the result of Caucal for the analogous question in the sequential case where the hierarchy collapses.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(00)00099-2