The complexity of monadic recursion schemes: executability problems, nesting depth, and applications
From MaRDI portal
Publication:792758
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
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) 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