Context-sensitive transitive closure operators

DOI10.1016/0168-0072(94)90036-1zbMath0799.03043OpenAlexW2093975937MaRDI QIDQ1319508

Iain A. Stewart

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

zbMATH Keywords

PHpolynomial-time hierarchycomplexity classesPSPACEdescriptive complexity theoryNPPfixed point operatorprogram schemescontext-sensitive transitive closure operator

Mathematics Subject Classification ID

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