A characterization of free pairs of upper triangular free monoid morphisms



: Juha Honkala

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2019

: Information and Computation

: INFORM COMPUT

: 267

: 110

: 115

: 6

: 0890-5401

: 1090-2651

DOI: https://doi.org/10.1016/j.ic.2019.03.007


We study combinatorics on morphisms. More precisely, we study free monoid morphisms and their freeness properties. By definition, a set F of endomorphisms of a free monoid is free, if every product formed of morphims from F can be uniquely factorized. We show that if f and g are endomorphisms of the free monoid A* having upper triangular incidence matrices with diagonal entries at least two, then the pair {f, g} is free if and only if f and g do not commute. This result implies that for such pairs freeness is very easy to decide. (C) 2019 Elsevier Inc. All rights reserved.



Last updated on 2024-26-11 at 20:52