The freeness problem over matrix semigroups and bounded languages

2013/04/05 by Émilie Charlier, Charlier, Émilie, Juha Honkala +1
Computer Science · Mathematics · #Advanced Algebra and Logic #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #G.2.0 #Geometric and Algebraic Topology #cs.DM #math.CO #msc:F.4.3 #msc:G.2.0 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1304.1637

17 pages

arxiv created 2013/04/05 · openalex publication_date 2013/04/05 · arxiv updated 2013/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2× 2 matrices with rational entries when the products are restricted to certain bounded languages.

Related

• On the decidability of semigroup freeness
• Matrix Semigroup Freeness Problems in SL(2,ℤ)
• On the Word Problem for Free Products of Semigroups and Monoids
• The word problem for free adequate semigroups
• Product-free sets in the free semigroup