01283688

j

01283688 Badouel, Eric Darondeau, Philippe Raoult, Jean-Claude Context-free event domains are recognizable. Inf. Comput. 149, No.2, 134-172 (1999). 1999 Elsevier Science (Academic Press), San Diego, CA EN Stark's trace automata

doi:10.1006/inco.1998.2752

Summary: The possibly non-distributive event domains which arise from Winskel's event structures with binary conflict are known to coincide with the domains of configurations of Stark's trace automata. We prove that whenever the transitive reduction of the order on finite elements in an event domain is a context-free graph in the sense of M\"uller and Schupp, the event domain may also be generated from a finite trace automaton, where both the set of states and the concurrent alphabet are finite. We show that the set of graph grammars which generate event domains is a recursive set. We obtain altogether an effective procedure which decides from an unlabeled graph grammar whether it generates an event domain and which constructs in that case a finite trace automaton recognizing that event domain. $\copyright$ Academic Press.