The complexity of monadic recursion schemes: Exponential time bounds

DOI10.1016/0022-0000(84)90021-7zbMath0543.68034OpenAlexW2013008477MaRDI QIDQ796301

Daniel J. Rosenkrantz, Harry B. III Hunt

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90021-7

zbMATH Keywords

decision problemsmonadic recursion schemesexecutability problem

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)

Related Items (1)

Sufficient-completeness, ground-reducibility and their complexity

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• 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
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Ianov's Program Schemata

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