The algebra of binary trees is affine complete

Autor:	Arnold, Andre, Cegielski, Patrick, Grigorieff, Serge, Guessarian, Irene
Rok vydání:	2020
Předmět:	Computer Science - Formal Languages and Automata Theory 06A99 08A30 08B20
Zdroj:	Discrete Mathematics & Theoretical Computer Science, vol. 23 no. 2, special issue in honour of Maurice Pouzet, Special issues (November 4, 2021) dmtcs:6890
Druh dokumentu:	Working Paper
DOI:	10.46298/dmtcs.6890
Popis:	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. Comment: 9 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2011.03925 Zobrazit plný text záznamu View this record from Arxiv