Commuting upper triangular binary morphisms

Juha Honkala

arxiv: 2302.06158 · v4 · submitted 2023-02-13 · 💻 cs.FL

Commuting upper triangular binary morphisms

Juha Honkala This is my paper

Pith reviewed 2026-05-24 10:13 UTC · model grok-4.3

classification 💻 cs.FL

keywords commuting morphismsupper triangular morphismsbinary alphabetfree monoidincidence matrixmorphism compositioncombinatorics on words

0 comments

The pith

All upper triangular binary morphisms that commute under composition are explicitly characterized.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a complete description of which upper triangular morphisms on a two-letter alphabet satisfy g1 composed with g2 equals g2 composed with g1. This classification is possible because the upper triangular condition on incidence matrices severely restricts the allowed images of each letter. A reader would care since the result turns the abstract commutativity question into a check against a finite collection of matrix and image forms. If the description is accurate, any pair in this class can be tested for commutativity by direct comparison to the listed cases rather than by computing full compositions.

Core claim

A morphism g from the free monoid on a binary alphabet into itself is upper triangular when its incidence matrix is upper triangular. The paper gives the full list of all such g1 and g2 for which the composition g1 g2 equals g2 g1, obtained by exhaustive case analysis on the possible matrix entries and the resulting word images of the two letters.

What carries the argument

Upper triangular incidence matrix, which forces the image of the first letter to contain only the first letter and thereby limits the possible commuting pairs to a small number of explicit families.

If this is right

Commutativity of any two such morphisms reduces to verifying membership in one of the enumerated families defined by their incidence matrices.
The complete set of commuting pairs is finite in number up to parameter choices and can be generated algorithmically.
Equality of the compositions can be decided without expanding the full words by comparing matrix parameters and letter images directly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same matrix-driven case analysis might extend to deciding other algebraic properties such as conjugacy for the same restricted class.
The binary upper-triangular restriction could serve as a base case for inductive arguments toward three-letter alphabets.
The explicit forms supply test instances for software that solves word equations involving commuting morphisms.

Load-bearing premise

The morphisms act on exactly two letters and their incidence matrices are required to be upper triangular.

What would settle it

A concrete pair of upper triangular binary morphisms whose compositions commute but whose forms are absent from the listed families would show the characterization is incomplete.

read the original abstract

A morphism $g$ from the free monoid $X^*$ into itself is called upper triangular if the matrix of $g$ is upper triangular. We characterize all upper triangular binary morphisms $g_1$ and $g_2$ such that $g_1g_2=g_2g_1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Honkala gives an explicit list of all commuting pairs among upper triangular binary morphisms.

read the letter

The paper states and proves a clean characterization: on a binary alphabet, two upper triangular morphisms commute exactly when their incidence matrices and images of the generators fall into one of a handful of listed forms. The triangular restriction lets the author reduce the commuting condition g1 g2 = g2 g1 to manageable casework on the matrix entries and the lengths of the images of the two letters. That casework appears to be exhaustive within the stated bounds, and the definitions stay standard (free monoid, incidence matrix, upper triangular). No circularity or free parameters show up. The result is new in the sense that it isolates this subclass and finishes the classification rather than restating earlier general theorems. The main limitation is exactly the one the title announces: binary alphabet plus upper triangular matrices. That makes the problem solvable but also keeps the payoff small outside the immediate sub-area. Nothing in the argument suggests the same technique scales to larger alphabets or non-triangular cases, and the paper does not claim it does. The work is therefore useful to someone who already needs to handle triangular morphisms (for instance when checking properties of certain automata or when the matrix form arises naturally), but it will not move broader questions about arbitrary commuting morphisms. The citation pattern looks normal for the field and does not rely on self-reference to prop up the claim. A specialist reading group on combinatorics on words might spend half an hour on the case analysis; a general automata or algebra group would skip it. The paper is coherent on its own terms and the claim is falsifiable by counter-example, so it merits referee time even if the scope stays narrow.

Referee Report

1 major / 0 minor

Summary. The manuscript characterizes all upper triangular binary morphisms g1 and g2 such that g1 g2 = g2 g1, where upper triangular refers to the incidence matrix of the morphism being upper triangular over a binary alphabet.

Significance. If the explicit characterization is complete and correctly proved, the result contributes a concrete classification within the monoid of endomorphisms of the free monoid on two generators, under a matrix restriction that reduces the possible images of letters. This may serve as a stepping stone for broader questions on commuting morphisms.

major comments (1)

The abstract states that a characterization exists, but the provided text supplies neither an outline of the case analysis nor verification that all commuting pairs have been enumerated; without an explicit list of the forms or a proof strategy in the main body, the central claim cannot be assessed for completeness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report and the opportunity to clarify the presentation of our results on commuting upper triangular binary morphisms. We address the single major comment below.

read point-by-point responses

Referee: The abstract states that a characterization exists, but the provided text supplies neither an outline of the case analysis nor verification that all commuting pairs have been enumerated; without an explicit list of the forms or a proof strategy in the main body, the central claim cannot be assessed for completeness.

Authors: We agree that an explicit outline of the case analysis and a summary verification of the enumerated pairs would improve readability and allow easier assessment of completeness. The manuscript does contain a full case analysis based on the possible images of the two generators under the upper-triangular constraint (considering the possible lengths and prefix relations enforced by the incidence matrix being upper triangular), but this analysis is distributed through the proofs rather than summarized upfront. In the revised version we will insert a new subsection (immediately after the preliminaries) that (i) states the overall proof strategy, (ii) lists the exhaustive cases considered for the pair (g1,g2), and (iii) provides a compact table or enumerated list of all commuting pairs that arise. This addition will make the completeness claim transparent without altering the mathematical content. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states an explicit characterization of all upper-triangular binary morphisms that commute, with the scope (binary alphabet and upper-triangular incidence matrices) declared up front in the claim itself. No fitted parameters, self-definitional loops, or load-bearing self-citations appear in the abstract or the described result structure; the work rests on standard external definitions of free monoids, morphisms, and matrix representations. The derivation is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; the central claim rests on the standard definition of upper triangular morphisms and the binary alphabet restriction.

axioms (1)

domain assumption A morphism is upper triangular when its incidence matrix is upper triangular.
This is the defining property invoked in the abstract.

pith-pipeline@v0.9.0 · 5555 in / 943 out tokens · 20949 ms · 2026-05-24T10:13:53.130674+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Automatic Sequences

Allouche J-P , and Shallit J. Automatic Sequences. Theory, Applications, Generalizations, Cambridge Uni- versity Press, 2003. ISBN:0-521-82332-3

work page 2003
[2]

On the decidability of semigr oup freeness, RAIRO - Theor

Cassaigne J, and Nicolas F. On the decidability of semigr oup freeness, RAIRO - Theor. Inform. Appl

work page
[3]

doi:10.1051/ita/2012010

46:355–399. doi:10.1051/ita/2012010

work page doi:10.1051/ita/2012010
[4]

The equations h(w) = wn in binary alphabets, Theoret

Harju T, and Linna M. The equations h(w) = wn in binary alphabets, Theoret. Comput. Sci. 1984. 33:327–329

work page 1984
[5]

Remarks concerning the freeness problem over morphism and matrix semigroups, Theoret

Honkala J. Remarks concerning the freeness problem over morphism and matrix semigroups, Theoret. Comput. Sci. 2014. 557:115–119. doi:10.1016/j.tcs.2014. 08.013

work page doi:10.1016/j.tcs.2014 2014
[6]

The freeness problem for uniform free monoid m orphisms, in M

Honkala J. The freeness problem for uniform free monoid m orphisms, in M. Gheorghe, I. Petre, M. Perez- Jimenez, G. Rozenberg, A. Salomaa (Eds.): Multidisciplinary Creativity, Spandugino, 2015, pp. 261–268

work page 2015
[7]

A characterization of free pairs of upper tria ngular free monoid morphisms, Inform

Honkala J. A characterization of free pairs of upper tria ngular free monoid morphisms, Inform. Comput

work page
[8]

doi:10.1016/j.ic.2019.03.007

267:110–115. doi:10.1016/j.ic.2019.03.007

work page doi:10.1016/j.ic.2019.03.007 2019
[9]

Combinatorics on morphisms - the freeness pro blem for pairs of morphisms, submitted

Honkala J. Combinatorics on morphisms - the freeness pro blem for pairs of morphisms, submitted

work page
[10]

Combinatorics on W ords, Addison-Wesley, 1983

Lothaire M. Combinatorics on W ords, Addison-Wesley, 1983. ISBN:978-0-12-198820-3. doi:10. 1016/ C2013-0-10554-5

work page 1983
[11]

Algebraic Combinatorics on W ords , Cambridge University Press, 2002

Lothaire M. Algebraic Combinatorics on W ords , Cambridge University Press, 2002. doi:10.1017/ CBO9781107326019. 298 J. Honkala / Commuting Upper Triangular Binary Morphisms

work page 2002
[12]

Wasserman

Rao H, and Wen Z-Y . Invertible substitutions with a comm on periodic point, in J. Barral, S. Seuret (Eds.): Recent Developments in Fractals and Related Fields , Birkh¨ auser, 2010, pp. 401–409. doi:10.1007/978-0- 8176-4888-6 26

work page doi:10.1007/978-0- 2010
[13]

The Mathematical Theory of L Systems , Academic Press, 1980

Rozenberg G, and Salomaa A. The Mathematical Theory of L Systems , Academic Press, 1980. ISBN: 9780080874067

work page 1980
[14]

Rozenberg G, and Salomaa A. (Eds.). Handbook of F ormal Languages , V ols. 1-3, Springer, 1997. ISBN:978-3-642-63863-3

work page 1997
[15]

Jewels of F ormal Language Theory, Computer Science Press, 1981

Salomaa A. Jewels of F ormal Language Theory, Computer Science Press, 1981

work page 1981

[1] [1]

Automatic Sequences

Allouche J-P , and Shallit J. Automatic Sequences. Theory, Applications, Generalizations, Cambridge Uni- versity Press, 2003. ISBN:0-521-82332-3

work page 2003

[2] [2]

On the decidability of semigr oup freeness, RAIRO - Theor

Cassaigne J, and Nicolas F. On the decidability of semigr oup freeness, RAIRO - Theor. Inform. Appl

work page

[3] [3]

doi:10.1051/ita/2012010

46:355–399. doi:10.1051/ita/2012010

work page doi:10.1051/ita/2012010

[4] [4]

The equations h(w) = wn in binary alphabets, Theoret

Harju T, and Linna M. The equations h(w) = wn in binary alphabets, Theoret. Comput. Sci. 1984. 33:327–329

work page 1984

[5] [5]

Remarks concerning the freeness problem over morphism and matrix semigroups, Theoret

Honkala J. Remarks concerning the freeness problem over morphism and matrix semigroups, Theoret. Comput. Sci. 2014. 557:115–119. doi:10.1016/j.tcs.2014. 08.013

work page doi:10.1016/j.tcs.2014 2014

[6] [6]

The freeness problem for uniform free monoid m orphisms, in M

Honkala J. The freeness problem for uniform free monoid m orphisms, in M. Gheorghe, I. Petre, M. Perez- Jimenez, G. Rozenberg, A. Salomaa (Eds.): Multidisciplinary Creativity, Spandugino, 2015, pp. 261–268

work page 2015

[7] [7]

A characterization of free pairs of upper tria ngular free monoid morphisms, Inform

Honkala J. A characterization of free pairs of upper tria ngular free monoid morphisms, Inform. Comput

work page

[8] [8]

doi:10.1016/j.ic.2019.03.007

267:110–115. doi:10.1016/j.ic.2019.03.007

work page doi:10.1016/j.ic.2019.03.007 2019

[9] [9]

Combinatorics on morphisms - the freeness pro blem for pairs of morphisms, submitted

Honkala J. Combinatorics on morphisms - the freeness pro blem for pairs of morphisms, submitted

work page

[10] [10]

Combinatorics on W ords, Addison-Wesley, 1983

Lothaire M. Combinatorics on W ords, Addison-Wesley, 1983. ISBN:978-0-12-198820-3. doi:10. 1016/ C2013-0-10554-5

work page 1983

[11] [11]

Algebraic Combinatorics on W ords , Cambridge University Press, 2002

Lothaire M. Algebraic Combinatorics on W ords , Cambridge University Press, 2002. doi:10.1017/ CBO9781107326019. 298 J. Honkala / Commuting Upper Triangular Binary Morphisms

work page 2002

[12] [12]

Wasserman

Rao H, and Wen Z-Y . Invertible substitutions with a comm on periodic point, in J. Barral, S. Seuret (Eds.): Recent Developments in Fractals and Related Fields , Birkh¨ auser, 2010, pp. 401–409. doi:10.1007/978-0- 8176-4888-6 26

work page doi:10.1007/978-0- 2010

[13] [13]

The Mathematical Theory of L Systems , Academic Press, 1980

Rozenberg G, and Salomaa A. The Mathematical Theory of L Systems , Academic Press, 1980. ISBN: 9780080874067

work page 1980

[14] [14]

Rozenberg G, and Salomaa A. (Eds.). Handbook of F ormal Languages , V ols. 1-3, Springer, 1997. ISBN:978-3-642-63863-3

work page 1997

[15] [15]

Jewels of F ormal Language Theory, Computer Science Press, 1981

Salomaa A. Jewels of F ormal Language Theory, Computer Science Press, 1981

work page 1981