Programs over semigroups of dot-depth one

DOI10.1016/S0304-3975(99)00278-9MaRDI QIDQ1575738zbMATH OpenFDO

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

Publication date 21 August 2000

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

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00278-9

zbMATH Keywords

Boolean circuitsdot-depth onep-varietysemigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 17309
• Finite semigroup varieties defined by programs
• Programs in partial algebras
• Programs over aperiodic monoids
• Semigroups and languages of dot-depth two
• scientific article; zbMATH DE number 3961008
• Semigroups with if-then-else and halting programs
• Publication:4945239
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Generic properties for semialgebraic programs

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• \(NC^ 1\): The automata-theoretic viewpoint
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Characterizations of locally testable events
• Circuit Bottom Fan-in and Computational Power
• CONSTANT-DEPTH PERIODIC CIRCUITS
• Finite monoids and the fine structure of NC ¹
• Finite semigroup varieties defined by programs
• scientific article; zbMATH DE number 3827223 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1136081 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Non-uniform automata over groups
• On finite monoids having only trivial subgroups
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages in \(NC\)

Cited in

(10)

• Finite semigroup varieties defined by programs
• Characterizing level one in group-based concatenation hierarchies
• On the computational power of programs over \(\mathsf{BA}_2\) monoid
• Difference hierarchies and duality with an application to formal languages
• Perfect correspondences between dot-depth and polynomial-time hierarchies
• Efficient algorithms for membership in Boolean hierarchies of regular languages
• scientific article; zbMATH DE number 17309 (Why is no real title available?)
• The power of programs over monoids in DA
• The regular languages of first-order logic with one alternation
• Languages polylog-time reducible to dot-depth 1/2

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

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