2006/01/13 by Matthieu Picantin, Picantin, Matthieu · 7 citations
Computer Science · Mathematics · #Algebra over a field #Computer science #Divisibility rule #FOS: Mathematics #General Mathematics (math.GM) #Geometric and Algebraic Topology #Mathematics #Pure mathematics #Rings, Modules, and Algebras #math.GM #semigroups and automata theory
paper · pdf · open access · doi:10.48550/arxiv.math/0601328
published in arXiv (Cornell University) (Cornell University) · 20 pages
arxiv created 2006/01/13 · openalex publication_date 2006/01/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Divisibility monoids are a natural lattice-theoretical generalization of Mazurkiewicz trace monoids, namely monoids in which the distributivity of the involved divisibility lattices is kept as an hypothesis, but the relations between the generators are not supposed to necessarily be commutations. Here, we show that every divisibility monoid admits an explicit finite transducer which allows to compute normal forms in quadratic time. In addition, we prove that every divisibility monoid is biautomatic.