The freeness problem over matrix semigroups and bounded languages - UTU Research Portal

A1 Refereed original research article in a scientific journal

The freeness problem over matrix semigroups and bounded languages

Authors: Émilie Charlier, Juha Honkala

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

Publication year: 2014

Journal: Information and Computation

Journal name in source: INFORMATION AND COMPUTATION

Journal acronym: INFORM COMPUT

Volume: 237

First page : 243

Last page: 256

Number of pages: 14

ISSN: 0890-5401

DOI: https://doi.org/10.1016/j.ic.2014.03.001

Abstract

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.