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

complexitywordsrecognizable languagessemigroup varietiesBoolean circuitalphabetprogramfinite monoidaperiodic monoidcounting modulo puniversal monoids

Mathematics Subject Classification ID

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

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

• 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?)
• A taxonomy of problems with fast parallel algorithms
• Sur le produit de concatenation non ambigu
• The dot-depth hierarchy of star-free languages is infinite

Cited in

(9)

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

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)