A Taxonomy of Infinite State Processes

AbstractIn 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