A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A characterization of free pairs of upper triangular free monoid morphisms
Tekijät: Juha Honkala
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2019
Journal: Information and Computation
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 267
Aloitussivu: 110
Lopetussivu: 115
Sivujen määrä: 6
ISSN: 0890-5401
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2019.03.007
Tiivistelmä
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.
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.