scientific article; zbMATH DE number 1086678

MaRDI QIDQ4362929zbMATH OpenFDO

Authors Martin Otto

Publication date 13 November 1997

zbMATH Keywords

bounded variable fragmentbounded variable fragment of infinitary logiccombinatorial circuitscombinatorial symmetry of circuitsfirst-order definabilityfirst-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On symmetric circuits and fixed-point logics
• scientific article; zbMATH DE number 6691390
• Circuit complexity and the expressive power of generalized first-order formulas
• From formulas to cirquents in computability logic
• A classical propositional logic for reasoning about reversible logic circuits
• Propositional Logic for Circuit Classes
• Expansions of pseudoinfinite structures and circuit and proof complexity
• A logical characterization of constant-depth circuits over the reals
• scientific article; zbMATH DE number 4008383
• Computational complexity and the expressive power of logics

Cited in

(9)

• On symmetric circuits and fixed-point logics
• scientific article; zbMATH DE number 6691390 (Why is no real title available?)
• A logic for constant-depth circuits
• Definability by constant-depth polynomial-size circuits
• Symmetric circuits for rank logic
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Symmetric arithmetic circuits
• Symmetric arithmetic circuits
• Limits of symmetric computation (invited talk)

This page was built for publication:

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