Computability by Monadic Second-Order Logic
arXiv:2008.12151
Abstract
A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula in monadic second-order logic. The latter means that the formula defines a set of graphs, in the usual way, such that each "computation graph" in that set determines a pair consisting of an input graph and an output graph.
12 pages, 4 figures, to appear in Information Processing Letters