Basic Analysis of Structure Rewriting Systems

A single state of an analyzed system has, in practice, often a complex structure in itself, while in theory it is usually simple in some sense, e.g. it can be a tree. We show how the interpretation of structures of bounded clique-width in the binary tree allows to apply tree automata to the analysis of a basic kind of systems where states are arbitrary relational structures. A few new questions emerge for more general systems, and we discuss them as well.