André Arnold ; Patrick Cégielski ; Irène Guessarian - Affine completeness of some free binary algebras

fi:8962 - Fundamenta Informaticae, October 21, 2022, Volume 186, Issues 1-4: Trakhtenbrot's centenary
Affine completeness of some free binary algebras

Authors: André Arnold ; Patrick Cégielski ; Irène Guessarian

    A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. An algebra is said to be affine complete if every congruence preserving function is a polynomial function. We show that the algebra of (possibly empty) binary trees whose leaves are labeled by letters of an alphabet containing at least one letter, and the free monoid on an alphabet containing at least two letters are affine complete.


    Volume: Volume 186, Issues 1-4: Trakhtenbrot's centenary
    Published on: October 21, 2022
    Accepted on: June 21, 2022
    Submitted on: January 17, 2022
    Keywords: Mathematics - Rings and Algebras,Computer Science - Formal Languages and Automata Theory,06A99 - 08A30 - 08B20,F.4.m

    Share

    Consultation statistics

    This page has been seen 4 times.
    This article's PDF has been downloaded 2 times.