Finite semigroup varieties defined by programs

DOI10.1016/S0304-3975(96)00297-6MaRDI QIDQ1390876zbMATH OpenFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 17309
• Programs over semigroups of dot-depth one
• Finite semigroup varieties of the form V*D
• The power of programs over monoids in \textbf{J}

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1256663 (Why is no real title available?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• CONSTANT-DEPTH PERIODIC CIRCUITS
• Finite monoids and the fine structure of NC ¹
• Finite semigroup varieties of the form V*D
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Non-uniform automata over groups
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)
• \(NC^ 1\): The automata-theoretic viewpoint
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(8)

• scientific article; zbMATH DE number 7577578 (Why is no real title available?)
• The power of programs over monoids in DA
• On the computational power of programs over \(\mathsf{BA}_2\) monoid
• Languages polylog-time reducible to dot-depth 1/2
• scientific article; zbMATH DE number 17309 (Why is no real title available?)
• Programs over semigroups of dot-depth one
• The power of programs over monoids in \textbf{J}
• Languages defined with modular counting quantifiers

This page was built for publication: Finite semigroup varieties defined by programs

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