The complexity of monadic recursion schemes: Exponential time bounds

DOI10.1016/0022-0000(84)90021-7MaRDI QIDQ796301zbMATHOpenAlexFDO

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

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)

Recommendations

• Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze
• On the Hoare theory of monadic recursion schemes
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• Decidable properties of monadic recursive schemas with a depth parameter
• Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus

Cites work

• scientific article; zbMATH DE number 3576680 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• 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 Ianov's Program Schemata
• On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
• On the Computational Complexity of Program Scheme Equivalence
• The complexity of monadic recursion schemes: executability problems, nesting depth, and applications

Cited in

(6)

• scientific article; zbMATH DE number 3984549 (Why is no real title available?)
• On the Hoare theory of monadic recursion schemes
• The Hoare logic of deterministic and nondeterministic monadic recursion schemes
• Decidable properties of monadic recursive schemas with a depth parameter
• Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze
• Sufficient-completeness, ground-reducibility and their complexity

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)