Programs over aperiodic monoids

DOI10.1016/0304-3975(89)90051-0MaRDI QIDQ1122664zbMATH OpenOpenAlexFDO

Authors Denis Thérien

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0304-3975(89)90051-0

zbMATH Keywords

alphabetaperiodic monoidBoolean circuitcomplexitycounting modulo pfinite monoidprogramrecognizable languagessemigroup varietiesuniversal monoidswords

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Review text

A program P over a finite monoid M is a finite sequence of instructions, i.e. of words over the alphabet \(I_ n=1,n\times M^{\{0,1\}}\) where n is a fixed integer. To each program \(P=\iota_ 1...\iota_ k\in I^*_ n\) is associated a function \(f_ P\) from \(\{0,1\}^ n\) into M. This function is defined by the rule: \[ \forall w=w_ 1...w_ n\in \{0,1\}^ n,\quad f_ P(w)=\prod^{k}_{i=1}f_ i(w_{k(i)}) \] if the i-th instruction is \(\iota_ i=(k(i),f_ i)\) for every i in \(1,k\). A language L in \(\{0,1\}^*\) is then said to be recognizable by M iff for each \(n\in {\mathbb{N}}\), there exists a program \(P(n)\in I^*_ n\) and a subset \(F_ n\subset M\) such that \(L\cap \{0,1\}^ n=f^{-1}_{P(n)}(F_ n)\). It is to be noticed that a language recognizable in the usual sense [cf. \textit{J. E. Pin}, Variétés de langages formels (Masson, Paris, 1984; Zbl 0636.68093)] is also recognizable in the sense of the paper, but the converse is false. The paper presents first a specific aperiodic monoid U which is universal in the following sense: any language L over \(\{0,1\}\) can be recognized by U. Secondly, the author studies different classes of non universal monoids. More precisely, it is shown - modulo some technical precisions - that every monoid M in the semigroup varieties \(R\vee L\), DA or \(J_ 1*G_ q\) cannot recognize the language \(MOD_ p=\{w\in \{0,1\}^*\), \(| w|_ 1\equiv 0 [p]\}\). Finally, the author conjectures that an aperiodic monoid M recognizes \(MOD_ p\) iff U divides M.

Recommendations

• Languages recognized by programs over the two-element monoid
• The power of programs over monoids in \textbf{J}
• The power of programs over monoids in DA
• scientific article; zbMATH DE number 4041299
• scientific article; zbMATH DE number 1916674

Cites work

• A taxonomy of problems with fast parallel algorithms
• scientific article; zbMATH DE number 4033093 (Why is no real title available?)
• scientific article; zbMATH DE number 4037246 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• Sur le produit de concatenation non ambigu
• The dot-depth hierarchy of star-free languages is infinite

Cited in

(10)

• Compositions of programs that induce special monotonic functions
• Programs over semigroups of dot-depth one
• Monoids of non-halting programs with tests
• Aperiodic languages in concurrency monoids
• Learning expressions and programs over monoids
• scientific article; zbMATH DE number 4041299 (Why is no real title available?)
• ON THE BURNSIDE SEMIGROUPS xⁿ = x^n+m
• Tameness and the power of programs over monoids in \(\mathbf{DA}\)
• The power of programs over monoids in DA
• The power of programs over monoids in \textbf{J}

This page was built for publication: Programs over aperiodic monoids

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