2022/06/23 by Thomas Aird, Aird, Thomas, Duarte Miguel Ferreira Rodrigues Ribeiro +1
Computer Science · #05E10 #05E99 #12K10 #16Y60 #20M05 #20M07 (Primary) 08B05 #20M30 #20M32 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Logic, programming, and type systems #Polynomial and algebraic computation #Rings and Algebras (math.RA) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2206.11725
openalex publication_date 2022/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We exhibit a faithful representation of the stylic monoid of every finite rank as a monoid of upper unitriangular matrices over the tropical semiring. Thus, we show that the stylic monoid of finite rank n generates the pseudovariety \boldsymbolJn, which corresponds to the class of all piecewise testable languages of height n, in the framework of Eilenberg's correspondence. From this, we obtain the equational theory of the stylic monoids of finite rank, show that they are finitely based if and only if n ≤ 3, and that their identity checking problem is decidable in linearithmic time. We also establish connections between the stylic monoids and other plactic-like monoids, and solve the finite basis problem for the stylic monoid with involution.