First order extensions of residue classes and uniform circuit complexity

DOI10.1007/978-3-642-39992-3_8MaRDI QIDQ2849422zbMATH OpenOpenAlexFDO

Authors Carlos E. P. Ortiz, Argimiro Arratia

Publication date 17 September 2013

Published in Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39992-3_8

Mathematics Subject Classification ID

Applications of logic to commutative algebra (13L05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Methods of class field theory to separate logics over finite residue classes and circuit complexity
• Circuit complexity and the expressive power of generalized first-order formulas
• On uniformity within \(NC^ 1\)
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Definability of Languages by Generalized First-Order Formulas over (N,+)

Cited in

(1)

• Methods of class field theory to separate logics over finite residue classes and circuit complexity

This page was built for publication: First order extensions of residue classes and uniform circuit complexity

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