EXAMPLES OF UNDECIDABLE PROBLEMS FOR 2-GENERATOR MATRIX SEMIGROUPS

Authors
CASSAIGNE J KARHUMAKI J
Citation
J. Cassaigne et J. Karhumaki, EXAMPLES OF UNDECIDABLE PROBLEMS FOR 2-GENERATOR MATRIX SEMIGROUPS, Theoretical computer science, 204(1-2), 1998, pp. 29-34
Citations number
10
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
204
Issue
1-2
Year of publication
1998
Pages
29 - 34
Database
ISI
SICI code
0304-3975(1998)204:1-2<29:EOUPF2>2.0.ZU;2-F
Abstract
We show that the following two problems are undecidable: given two squ are matrices, decide whether the semigroup that they generate contains the zero matrix, and whether it contains a matrix having a zero in th e right upper corner. (C) 1998-Elsevier Science B.V. All rights reserv ed.