The complexity of monadic recursion schemes: Exponential time bounds

Decidability of theories and sets of sentences (03B25) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: The complexity of monadic recursion schemes: Exponential time bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q796301)