The freeness problem over matrix semigroups and bounded languages




Émilie Charlier, Juha Honkala

PublisherACADEMIC PRESS INC ELSEVIER SCIENCE

2014

Information and Computation

INFORMATION AND COMPUTATION

INFORM COMPUT

237

243

256

14

0890-5401

DOIhttps://doi.org/10.1016/j.ic.2014.03.001



We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2 x 2 matrices with rational entries when the products are restricted to certain bounded languages. We also show that this problem becomes undecidable for sufficiently large matrices. (C) 2014 Elsevier Inc. All rights reserved.




Last updated on 2024-26-11 at 18:25