Finite semigroup varieties defined by programs

DOI10.1016/S0304-3975(96)00297-6zbMath0901.68094MaRDI QIDQ1390876

Pierre Péladeau, Howard Straubing, Denis Thérien

Publication date: 22 July 1998

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

zbMATH Keywords

regular languagescircuit complexity classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Languages polylog-time reducible to dot-depth 1/2 ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ Unnamed Item ⋮ Programs over semigroups of dot-depth one ⋮ The Power of Programs over Monoids in DA ⋮ Languages defined with modular counting quantifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(NC^ 1\): The automata-theoretic viewpoint
• Non-uniform automata over groups
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Finite semigroup varieties of the form V*D
• Parity, circuits, and the polynomial-time hierarchy
• Finite monoids and the fine structure of NC ¹
• CONSTANT-DEPTH PERIODIC CIRCUITS