Andre Arnold ; Patrick Cegielski ; Serge Grigorieff ; Irene Guessarian - The algebra of binary trees is affine complete

dmtcs:6890 - Discrete Mathematics & Theoretical Computer Science, November 4, 2021, vol. 23 no. 2, special issue in honour of Maurice Pouzet - https://doi.org/10.46298/dmtcs.6890
The algebra of binary trees is affine complete

Authors: Andre Arnold ; Patrick Cegielski ; Serge Grigorieff ; Irene Guessarian

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 polynomial.


Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
Section: Special issues
Published on: November 4, 2021
Accepted on: May 11, 2021
Submitted on: November 10, 2020
Keywords: Computer Science - Formal Languages and Automata Theory,06A99, 08A30, 08B20


Share

Consultation statistics

This page has been seen 159 times.
This article's PDF has been downloaded 38 times.