Descriptive complexity of deterministic polylogarithmic time and space

DOI10.1016/J.JCSS.2021.02.003MaRDI QIDQ2662676zbMATH OpenOpenAlexFDO

Authors Flavio Ferrarotti, Jan Van den Bussche, Jonni Virtema, Senén González, Jose Maria Turull Torres

Publication date 14 April 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.03413

zbMATH Keywords

descriptive complexitypolylogarithmic queries

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Recommendations

• A restricted second-order logic for non-deterministic poly-logarithmic time
• scientific article; zbMATH DE number 1342206
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• Descriptive characterizations of computational complexity
• Logical hierarchies in PTIME

Cites work

• Circuits, matrices, and nonassociative computation
• Computing LOGCFL certificates
• Descriptive complexity of deterministic polylogarithmic time
• Descriptive complexity of linear equation systems and applications to propositional proof complexity
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Elements of finite model theory.
• Finite model theory and its applications.
• Fixed-point extensions of first-order logic
• Graph properties checkable in linear time in the number of vertices
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• 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 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Logarithmic Depth Circuits for Algebraic Functions
• Number of quantifiers is better than number of tape cells
• On Relating Time and Space to Size and Depth
• On uniformity within \(NC^ 1\)
• Relational queries computable in polynomial time
• Sublinear time algorithms
• The polynomial-time hierarchy
• The Space Complexity of Elimination Theory: Upper Bounds

Cited in

(4)

• Descriptive complexity of deterministic polylogarithmic time
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• The logics for the complexity classes with limited non-determinism
• Recursion-theoretic alternation

This page was built for publication: Descriptive complexity of deterministic polylogarithmic time and space

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