Nondeterministic operations on finite relational structures

AbstractThis article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure properties are maintained. We relate them to the logical theory of finite relational structures and hypergraphs. Our central theorem says that every transduction which is definable in counting monadic second-order logic is a bottom-up transduction on term representations. Finally, several examples indicate that one cannot hope for decidable logical theories in the presence of unbounded nondeterminism