Linear circuits, two-variable logic and weakly blocked monoids

DOI10.1016/j.tcs.2013.07.005zbMath1297.94134OpenAlexW2000194783MaRDI QIDQ391307

Andreas Krebs, Mark Mercer, Christoph Behle

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.005

zbMATH Keywords

bounded-depth circuitslinear ciruitstwo-variable logicweakly blocked monoids

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Algebraic theory of languages and automata (68Q70)

Related Items (1)

A topological approach to non-uniform complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Regular languages defined with generalized quantifiers
• On uniformity within \(NC^ 1\)
• Characterizing \(\text{TC}^{0}\) in terms of infinite groups
• Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages
• Parity, circuits, and the polynomial-time hierarchy
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]
• On finite monoids having only trivial subgroups
• Automata, Languages and Programming

This page was built for publication: Linear circuits, two-variable logic and weakly blocked monoids