Cyclic automata (Q1100919): Difference between revisions

The author defines Cayley automata. These are finite state devices, acting as acceptors, capable of ``walking'' on an input Cayley graph (of some group) and eventually deciding whether to accept or reject the graph. Such an automaton is equipped with a finite number of pebbles (markers) which it can rop on (and pick from) the nodes of the graph. The paper is devoted to questions about the simplest kind of Cayley automata, those on (one-generator) cyclic graphs, here called cyclic automata. A complete characterization is give of cyclic graph languages accepted by o-pebble cyclic automata while arbitrary n-pebble cyclic automata are shown to define a strict hierarchy. Various decision problems are also discussed.