Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]

DOI10.1007/978-3-642-00982-2_11zbMath1234.68117OpenAlexW1582229778MaRDI QIDQ3618574

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_11

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Word problems, etc. in computability and recursion theory (03D40)

Related Items (1)

Linear circuits, two-variable logic and weakly blocked monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The kernel of monoid morphisms
• 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
• Semigroups, Presburger formulas, and languages
• On uniformity within \(NC^ 1\)
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Amplifying lower bounds by means of self-reducibility
• STACS 2005
• The descriptive complexity approach to LOGCFL

This page was built for publication: Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]