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

DOI10.1016/0304-3975(83)90091-9zbMath0537.68039OpenAlexW2085033370MaRDI QIDQ792758

Daniel J. Rosenkrantz, Harry B. III Hunt

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) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25)

Related Items

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

Cites Work

• Unnamed Item
• The complexity of monadic recursion schemes: executability problems, nesting depth, and applications
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• Monadic recursion schemes: The effect of constants
• Program schemes, recursion schemes, and formal languages
• Relationships between nondeterministic and deterministic tape complexities
• On the computational power of pushdown automata
• On the Computational Complexity of Program Scheme Equivalence
• On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
• Decidable Properties of Monadic Functional Schemas
• Functional schemas with nested predicates