The complexity of monadic recursion schemes: executability problems, nesting depth, and applications

DOI10.1016/0304-3975(83)90091-9MaRDI QIDQ792758zbMATH OpenOpenAlexFDO

Authors H. B. III Hunt, Daniel J. Rosenkrantz

Publication date 1983

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(83)90091-9

zbMATH Keywords

complexities of decision problemsexecutability problemsmaximal possible depths of nesting of function callsmonadic recursion schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25) Abstract data types; algebraic specification (68Q65)

Cites work

• scientific article; zbMATH DE number 3737028 (Why is no real title available?)
• Decidable Properties of Monadic Functional Schemas
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Functional schemas with nested predicates
• Monadic recursion schemes: The effect of constants
• On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
• On the Computational Complexity of Program Scheme Equivalence
• On the computational power of pushdown automata
• Program schemes, recursion schemes, and formal languages
• Relationships between nondeterministic and deterministic tape complexities
• The complexity of monadic recursion schemes: executability problems, nesting depth, and applications

Cited in

(3)

• The complexity of monadic recursion schemes: executability problems, nesting depth, and applications
• The complexity of monadic recursion schemes: Exponential time bounds
• scientific article; zbMATH DE number 4097355 (Why is no real title available?)

This page was built for publication: The complexity of monadic recursion schemes: executability problems, nesting depth, and applications

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