Congruence Preserving Functions on Free Monoids

2016/09/05 by Patrick Cégielski, Cégielski, Patrick, Serge Grigorieff +2
Computer Science · #08A30 #Advanced Algebra and Logic #FOS: Mathematics #Logic, programming, and type systems #Rings and Algebras (math.RA) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1609.01144

openalex publication_date 2016/09/05 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28

Abstract

A function on an algebra is congruence preserving if, for any congruence, it maps congruent elements to congruent elements. We show that, on a free monoid generated by at least 3 letters, a function from the free monoid into itself is congruence preserving %nonmonogenic if and only if it is of the form x ↦ w₀ x w₁ ⋯ w_n-1 x w_n for some finite sequence of words w₀,…,w_n. We generalize this result to functions of arbitrary arity. This shows that a free monoid with at least three generators is a (noncommutative) affine complete algebra. Up to our knowledge, it is the first (nontrivial) case of a noncommutative affine complete algebra.

Related

• The algebra of complete binary trees is affine complete
• A countable family of finitely presented infinite congruence-free monoids
• Congruence Preservation, Lattices and Recognizability
• Hyperlogarithms: Functions on Free Monoids
• Congruence Preservation, Lattices and Recognizability