Skip to Main content Skip to Navigation
Journal articles

The algebra of binary trees is affine complete

Abstract : A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is a polynomial function, thus exhibiting the first example of a non commutative and non associative affine complete algebra.
Complete list of metadata
Contributor : irene guessarian Connect in order to contact the contributor
Submitted on : Saturday, September 10, 2022 - 10:21:14 AM
Last modification on : Friday, September 16, 2022 - 3:54:17 AM


Publisher files allowed on an open archive



André Arnold, Patrick Cégielski, Serge Grigorieff, Irène Guessarian. The algebra of binary trees is affine complete. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2021, 23 (2), ⟨10.46298/dmtcs.6890⟩. ⟨hal-03774317⟩



Record views


Files downloads