Prefix-Recognisable Graphs and Monadic Second-Order Logic

Achim Blumensath

We present several characterisations of the class of prefix-recognisable
graphs including representations via graph-grammars and
MSO-interpretations.  The former implies that prefix-recognisable graphs
have bounded clique-width; the latter is used to extend this class to
arbitrary relational structures.  We prove that the prefix-recognisable
groups are exactly the context-free groups. Finally, we develop methods
to prove that certain structures are not prefix-recognisable and apply
them to well-ordered structures.