The complexity of monadic recursion schemes: executability problems, nesting depth, and applications
DOI10.1016/0304-3975(83)90091-9zbMATH Open0537.68039OpenAlexW2085033370MaRDI QIDQ792758FDOQ792758
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
complexities of decision problemsexecutability problemsmaximal possible depths of nesting of function callsmonadic recursion schemes
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
- Relationships between nondeterministic and deterministic tape complexities
- On the computational power of pushdown automata
- Equivalence problems for deterministic context-free languages and monadic recursion schemes
- Program schemes, recursion schemes, and formal languages
- Decidable Properties of Monadic Functional Schemas
- On the Computational Complexity of Program Scheme Equivalence
- On the Complexity of Flowchart and Loop Program Schemes and Programming Languages
- Monadic recursion schemes: The effect of constants
- Title not available (Why is that?)
- Functional schemas with nested predicates
- The complexity of monadic recursion schemes: executability problems, nesting depth, and applications
Cited In (3)
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)
