The freeness problem over matrix semigroups and bounded languages
: Émilie Charlier, Juha Honkala
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
: 2014
: Information and Computation
: INFORMATION AND COMPUTATION
: INFORM COMPUT
: 237
: 243
: 256
: 14
: 0890-5401
DOI: https://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.