Freeness Problem for Matrix Semigroups of Parikh Matrices

• Autorzy: Teh Wen Chean , Atanasiu Adrian , Wong Denis C. K.

Identyfikatory

DOI

10.3233/FI-2021-2029

• Języki publikacji: EN

Abstrakty

EN

Since the undecidability of the mortality problem for 3 × 3 matrices over integers was proved using the Post Correspondence Problem, various studies on decision problems of matrix semigroups have emerged. The freeness problem in particular has received much attention but decidability remains open even for 2 × 2 upper triangular matrices over nonnegative integers. Parikh matrices are upper triangular matrices introduced as a generalization of Parikh vectors and have become useful tools in studying of subword occurrences. In this work, we focus on semigroups of Parikh matrices and study the freeness problem in this context.

Słowa kluczowe

EN

freeness problem; matrix semigroups; Parikh matrices; decidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 179, nr 4
• Strony: 385--397
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Teh Wen Chean

• School of Mathematical Sciences, Universiti Sains Malaysia, Penang, Malaysia

autor

Atanasiu Adrian

• Faculty of Mathematics and Computer Science, Bucharest University, Bucharest, Romania

autor

Wong Denis C. K.

• DMAS, LKC FES, Universiti Tunku Abdul Rahman, Kajang, Malaysia

Bibliografia

• [1] Paterson MS. Unsolvability in 3 x 3 matrices. Studies in Appl. Math., 1970. 49:105-107. doi:10.1002/ sapm1970491105.
• [2] Eilenberg S. Automata, languages, and machines, volume 58 of Pure and Applied Matematics : a Series of Monographs and Textbook. Academic Press, New York, 1974. ISBN: 978-0-122-34001-7.
• [3] Cassaigne J, Harju T, Karhumäki J. On the undecidability of freeness of matrix semigroups. Internat. J. Algebra Comput., 1999. 9(3-4):295-305. doi:10.1142/S0218196799000199.
• [4] Klarner DA, Birget JC, Satterfield W. On the undecidability of the freeness of integer matrix semigroups. Internat. J. Algebra Comput., 1991. 1(2):223-226. doi:10.1142/S0218196791000146.
• [5] Cassaigne J, Nicolas F. On the decidability of semigroup freeness. RAIRO Theor. Inform. Appl., 2012. 46(3):355-399. doi:10.1051/ita/2012010.
• [6] Bell P, Potapov I. Reachability problems in quaternion matrix and rotation semigroups. Inform. and Comput., 2008. 206(11):1353-1361. doi:10.1016/j.ic.2008.06.004.
• [7] Charlier E, Honkala J. The freeness problem over matrix semigroups and bounded languages. Inform. and Comput., 2014. 237:243-256. doi:10.1016/j.ic.2014.03.001.
• [8] Gawrychowski P, Gutan M, Kisielewicz A. On the problem of freeness of multiplicative matrix semigroups. Theoret. Comput. Sci., 2010. 411(7-9):1115-1120. doi:10.1016/j.tcs.2009.12.005.
• [9] Ko SK, Potapov I. Matrix semigroup freeness problems in SL(2,Z). In: SOFSEM 2017: theory and practice of computer science, volume 10139 of Lecture Notes in Comput. Sci., pp. 268-279. Springer, Cham, 2017. doi:10.1007/978-3-319-51963-0_21.
• [10] Duncan A, Gilman RH. Word hyperbolic semigroups. Math. Proc. Cambridge Philos. Soc., 2004. 136(3):513-524. doi:10.1017/S0305004103007497.
• [11] Hoffmann M, Holt DF, Owens MD, Thomas RM. Semigroups with a context-free word problem. In: International Conference on Developments in Language Theory, volume 7410 of Lecture Notes in Comput. Sci., pp. 97-108. Springer, Heidelberg, 2012.
• [12] Brough T, Cain AJ, Pfeiffer M. Context-free word problem semigroups. In: Developments in language theory, volume 11647 of Lecture Notes in Comput. Sci., pp. 292-305. Springer, Cham, 2019.
• [13] Mateescu A, Salomaa A, Salomaa K, Yu S. A sharpening of the Parikh mapping. Theor. Inform. Appl., 2001. 35(6):551-564. doi:10.1051/ita:2001131.
• [14] Poovanandran G, Teh WC. Elementary matrix equivalence and core transformation graphs for Parikh matrices. Discrete Appl. Math., 2018. 251:276-289. doi:10.1016/j.dam.2018.06.002.
• [15] Salomaa A. Criteria for the matrix equivalence of words. Theoret. Comput. Sci., 2010. 411(16-18):1818-1827. doi:10.1016/j.tcs.2010.01.036.
• [16] Şerbănuţă VN, Şerbănuţă TF. Injectivity of the Parikh matrix mappings revisited. Fund. Inform., 2006. 73(1-2):265-283.
• [17] Atanasiu A, Poovanandran G, Teh WC. Parikh motivated study in repetition in words. Bull. Math. Soc. Sci. Math. Roumanie, 2019. 62(4):325-340.
• [18] Teh WC, Atanasiu A, Poovanandran G. On strongly M-unambiguous prints and Şerbănuţă’s conjecture for Parikh matrices. Theoret. Comput. Sci., 2018. 719:86-93. doi:10.1016/j.tcs.2017.11.016.
• [19] Salomaa A. Parikh matrices: subword indicators and degrees of ambiguity. In: Adventures between lower bounds and higher altitudes, volume 11011 of Lecture Notes in Comput. Sci., pp. 100-112. Springer, Cham, 2018. doi:10.1007/978-3-319-98355-4_7.
• [20] Mahalingam K, Subramanian KG. Product of Parikh matrices and commutativity. Internat. J. Found. Comput. Sci., 2012. 23(1):207-223. doi:10.1142/S0129054112500049.
• [21] Berstel J, Perrin D, Reutenauer C. Codes and automata, volume 129 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2010. ISBN: 978-0-521-88831-8.
• [22] Mandel A, Simon I. On finite semigroups of matrices. Theoret. Comput. Sci., 1977/78. 5(2):101-111. doi:10.1016/0304-3975(77)90001-9.
• [23] Teh WC. Separability of M-equivalent words by morphisms. Internat. J. Found. Comput. Sci., 2016. 27(1):39-52. doi:10.1142/S0129054116500039.
• [24] Manvel B, Meyerowitz A, Schwenk A, Smith K, Stockmeyer P. Reconstruction of sequences. Discrete Math., 1991. 94(3):209-219. doi:10.1016/0012-365X(91)90026-X.
• [25] Atanasiu A. Binary amiable words. Internat. J. Found. Comput. Sci., 2007. 18(2):387-400. doi:10.1142/S0129054107004735.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).