Programs over semigroups of dot-depth one

DOI10.1016/S0304-3975(99)00278-9zbMath0946.68073MaRDI QIDQ1575738

Denis Thérien, Alexis Maciel, Pierre Péladeau

Publication date: 21 August 2000

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

zbMATH Keywords

semigroupBoolean circuitsdot-depth onep-variety

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ Difference hierarchies and duality with an application to formal languages ⋮ The Power of Programs over Monoids in DA ⋮ Characterizing level one in group-based concatenation hierarchies

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
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Finite semigroup varieties defined by programs
• Characterizations of locally testable events
• Parity, circuits, and the polynomial-time hierarchy
• Languages that Capture Complexity Classes
• Finite monoids and the fine structure of NC ¹
• Circuit Bottom Fan-in and Computational Power
• On finite monoids having only trivial subgroups
• CONSTANT-DEPTH PERIODIC CIRCUITS

This page was built for publication: Programs over semigroups of dot-depth one