Programs over semigroups of dot-depth one
type: Item
instance of: scholarly article
title: Programs over semigroups of dot-depth one
zbMATH Open document ID: 0946.68073
DOI: 10.1016/S0304-3975(99)00278-9
author: Alexis Maciel
author: Pierre Péladeau
author: Denis Thérien
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1493509
zbMATH Keywords: semigroup
zbMATH Keywords: dot-depth one
zbMATH Keywords: p-variety
zbMATH Keywords: Boolean circuits
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Regular languages in \(NC\)
cites work: Non-uniform automata over groups
cites work: Finite monoids and the fine structure of NC 1
cites work: Characterizations of locally testable events
cites work: Circuit Bottom Fan-in and Computational Power
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Languages that Capture Complexity Classes
cites work: Q3673124
cites work: \(NC^ 1\): The automata-theoretic viewpoint
cites work: Finite semigroup varieties defined by programs
cites work: On finite monoids having only trivial subgroups
cites work: CONSTANT-DEPTH PERIODIC CIRCUITS
cites work: Q4302435
cites work: Q4381392
Recommended article: Q3974006
Recommended article: Finite semigroup varieties defined by programs
Recommended article: Programs in partial algebras
Recommended article: Programs over aperiodic monoids
Recommended article: Semigroups and languages of dot-depth two
Recommended article: Q3730029
Recommended article: SEMIGROUPS WITH if–then–else AND HALTING PROGRAMS
Recommended article: Q4945239
Recommended article: Program schemes, arrays, Lindström quantifiers and zero-one laws
Recommended article: Generic Properties for Semialgebraic Programs
description: scientific article; zbMATH DE number 1493509