Context-sensitive transitive closure operators
From MaRDI portal
Publication:1319508
DOI10.1016/0168-0072(94)90036-1zbMath0799.03043OpenAlexW2093975937MaRDI QIDQ1319508
Publication date: 12 April 1994
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(94)90036-1
PHpolynomial-time hierarchycomplexity classesPSPACEdescriptive complexity theoryNPPfixed point operatorprogram schemescontext-sensitive transitive closure operator
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Generalized hex and logical characterizations of polynomial space ⋮ Positive versions of polynomial time ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Methods for proving completeness via logical reductions
- Fixed-point extensions of first-order logic
- Some relationships between logics of programs and complexity theory
- Complete problems for symmetric logspace involving free groups
- Using the Hamiltonian path operator to capture NP
- An observation on time-storage trade off
- The polynomial-time hierarchy
- Logical and schematic characterization of complexity classes
- Relationships between nondeterministic and deterministic tape complexities
- On uniformity within \(NC^ 1\)
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- On static logics, dynamic logics, and complexity classes
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Monotone versus positive
- Nondeterministic Space is Closed under Complementation
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- Logical Description of Monotone NP Problems
- REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
This page was built for publication: Context-sensitive transitive closure operators
