Context-sensitive transitive closure operators

DOI10.1016/0168-0072(94)90036-1MaRDI QIDQ1319508zbMATH OpenOpenAlexFDO

Authors Iain 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

complexity classescontext-sensitive transitive closure operatordescriptive complexity theoryfixed point operatorNPPPHpolynomial-time hierarchyprogram schemesPSPACE

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

This paper continues research initiated by Fagin about the question which (first or second order) logics can capture which complexity classes. The author introduces a new operator, called the context-sensitive transitive closure operator, which is able to express the class PSPACE. By varying how the operator is applied, also the complexity classes P, NP, PH (the polynomial-time hierarchy) can be captured.

Recommendations

• Languages that Capture Complexity Classes
• scientific article; zbMATH DE number 4106276
• scientific article; zbMATH DE number 408795
• scientific article; zbMATH DE number 4009811
• On the power of deterministic transitive closures

Cites work

• An observation on time-storage trade off
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Complete problems for symmetric logspace involving free groups
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• Fixed-point extensions of first-order logic
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 408812 (Why is no real title available?)
• scientific article; zbMATH DE number 219246 (Why is no real title available?)
• scientific article; zbMATH DE number 223336 (Why is no real title available?)
• scientific article; zbMATH DE number 223337 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Logical and schematic characterization of complexity classes
• Logical Description of Monotone NP Problems
• Methods for proving completeness via logical reductions
• Monotone versus positive
• Nondeterministic Space is Closed under Complementation
• On static logics, dynamic logics, and complexity classes
• On uniformity within \(NC^ 1\)
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Relational queries computable in polynomial time
• Relationships between nondeterministic and deterministic tape complexities
• Some relationships between logics of programs and complexity theory
• The polynomial-time hierarchy
• Using the Hamiltonian path operator to capture NP

Cited in

(7)

• Positive versions of polynomial time
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Generalized hex and logical characterizations of polynomial space
• Some Notes on Managing Closure Operators
• Cache-Friendly implementations of transitive closure
• scientific article; zbMATH DE number 1086669 (Why is no real title available?)
• scientific article; zbMATH DE number 1479646 (Why is no real title available?)

This page was built for publication: Context-sensitive transitive closure operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1319508)