A1 Journal article – refereed
A characterization of free pairs of upper triangular free monoid morphisms




List of Authors: Juha Honkala
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2019
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Volume number: 267
Number of pages: 6
ISSN: 0890-5401

Abstract
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.


Internal Authors/Editors

Last updated on 2019-20-07 at 08:58