Regular State Machines

Jürgen Teich(a) and Lothar Thiele(b)
(a) University of Paderborn
(b) ETH-Zentrum, Zürich

In this talk, we introduce the notion of a model called regular state machines (RSM) that characterizes a class of state-transition systems with a regular, repetitive, and (frequently) unbounded number of states and state transitions. An example of first choice is the state of a fifo queue, as written by a process and read by another process.

We show that many models of parallel computation, represented ususally by process graphs, may be effectively and finitely described in the state-space by an RSM, e.g., Petri nets and subclasses thereof.

Mathematically, a RSM is described by a set of indexed states, defined over an index domain which is a lattice bounded by a polyhedron.

We further show how properties such as state reachability, existence of periodic schedules, and memory analysis can be done efficiently based on results obtained in the area of mapping regular algorithms to processor arrays and loop parallelization...

Further info and related paper(s):

• send mail to Jürgen or to Lothar