The complexity of monadic recursion schemes: Exponential time bounds (Q796301)

We study the computational complexity of decision problems for the class \({\mathcal M}\) of monadic recursion schemes. By the ''executability problem'' for a class \({\mathcal S}\) of monadic recursion schemes, we mean the problem of determining whether a given defined function symbol of a given scheme in \({\mathcal S}\) can be called during at least one computation. The executability problem for a class \({\mathcal C}\) of very simple monadic recursion schemes is shown to require deterministic exponential time. Using arguments about executability problems and about the class \({\mathcal C}\), a number of decision problems for \({\mathcal M}\) and for several of \({\mathcal M}'s\) subclasses are shown to require deterministic exponential time. Deterministic exponential time upper bounds are also presented for several of these decision problems. The decision problems considered include the computational identity, isomorphism, strong equivalence, weak equivalence, and divergence problems.