Nondeterminism versus determinism of finite automata over directed acyclic graphs
Andreas Potthoff, Sebastian Seibert, Wolfgang H Thomas · Bulletin of the Belgian Mathematical Society - Simon Stevin · 1994
Three types of finite-state graph automata are compared over directed acyclic graphs (where vertices and edges are labelled). The automata are distinguished by the way how states are attached to an input graph (“vertexmarking”, “edge-marking”, and “1-sphere-marking”). We note the equivalence of these models, relate them to logical definability notions, and show that deterministic versions are strictly weaker (thus correcting an error of [9]). 1