The descriptive complexity of the fixed-points of bounded formulas

DOI10.1007/3-540-44622-2_11MaRDI QIDQ2753672zbMATH OpenFDO

Authors Albert Atserias

Publication date 11 November 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44622-2_11

zbMATH Keywords

BIT predicatecircuit uniformityinteger divisionlogarithmic-time hierarchyrudimentary languages

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)

Recommendations

• Bounded arithmetic and descriptive complexity
• On fixed-point logic with counting
• Bounded-arity hierarchies in fixed-point logics
• The expressive power of fixed-point logic with counting
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(4)

• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• On the descriptive complexity of \(\overline{\varSigma ^*\overline{L}}\)
• Bounded arithmetic and descriptive complexity
• Fluted formulas and the limits of decidability

This page was built for publication: The descriptive complexity of the fixed-points of bounded formulas

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