Computability by monadic second-order logic

Information Processing Letters, vol. 167, pp. 106074

Abstract

A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula of 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.

Authors 1

1. Joost Engelfriet corresponding Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands

   LIACS, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands#TAB#