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.


Combinatorics on morphisms, Free monoid morphism, Freeness problem



Last updated on 26/11/2024 08:52:12 PM