[en] 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.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Honkala, Juha; University of Turku > Mathematics and Statistics
Language :
English
Title :
The freeness problem over matrix semigroups and bounded languages
Publication date :
2014
Journal title :
Information and Computation
ISSN :
0890-5401
eISSN :
1090-2651
Publisher :
Academic Press, San Diego, United States - California
J. Cassaigne, and F. Nicolas On the decidability of semigroup freeness RAIRO Theor. Inform. Appl. 46 2012 355 399
D.A. Klarner, J.-C. Birget, and W. Satterfield On the undecidability of the freeness of integer matrix semigroups Int. J. Algebra Comput. 1 2 1991 223 226
J. Cassaigne, T. Harju, and J. Karhumäki On the undecidability of freeness of matrix semigroups Int. J. Algebra Comput. 9 3-4 1999 295 305 dedicated to the memory of Marcel-Paul Schützenberger
V. Blondel, J. Cassaigne, and J. Karhumäki Freeness of multiplicative matrix semigroups Unsolved Problems in Mathematical Systems and Control Theory 2004 Princeton University Press 309 314
P. Bell, and I. Potapov Reachability problems in quaternion matrix and rotation semigroups Mathematical Foundations of Computer Science Lect. Notes Comput. Sci. vol. 4708 2007 Springer Berlin 346 358
P. Gawrychowski, M. Gutan, and A. Kisielewicz On the problem of freeness of multiplicative matrix semigroups Theor. Comput. Sci. 411 7-9 2010 1115 1120
J. Honkala Number systems and the injectivity problem for matrix representations of free monoids Int. J. Algebra Comput. 19 2 2009 229 233
W. Kuich, and A. Salomaa Semirings, Automata, Languages EATCS Monogr. Theor. Comput. Sci. vol. 5 1986 Springer-Verlag Berlin
P. Bell, V. Halava, T. Harju, J. Karhumäki, and I. Potapov Matrix equations and Hilbert's tenth problem Int. J. Algebra Comput. 18 8 2008 1231 1241
P. Lancaster, and M. Tismenetsky The Theory of Matrices second ed. Comput. Sci. Appl. Math. 1985 Academic Press Inc. Orlando, FL
A. Salomaa, and M. Soittola Automata-Theoretic Aspects of Formal Power Series Texts Monogr. Comput. Sci. 1978 Springer-Verlag New York
G. Rozenberg, and A. Salomaa Cornerstones of Undecidability 1994 Prentice Hall New York
