A Taxonomy of Infinite State Processes
Faron Moller · Electronic Notes in Theoretical Computer Science · 1998
In this tutorial paper, we consider various classes of 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, push-down) automata, and Petri nets.