A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On Markov's undecidability theorem for integer matrices
Tekijät: Halava V, Harju T
Kustantaja: SPRINGER
Julkaisuvuosi: 2007
Lehti:: Semigroup Forum
Tietokannassa oleva lehden nimi: SEMIGROUP FORUM
Lehden akronyymi: SEMIGROUP FORUM
Vuosikerta: 75
Numero: 1
Aloitussivu: 173
Lopetussivu: 180
Sivujen määrä: 8
ISSN: 0037-1912
DOI: https://doi.org/10.1007/s00233-007-0714-x
Tiivistelmä
We study a problem considered originally by A. Markov in 1947: Given two finitely generated matrix semigroups, determine whether or not they contain a common element. This problem was proved undecidable by Markov for 4 x 4 matrices, even in a very restrict form, and for 3 x 3 matrices by Krom in 1981. Here we give a new proof in the 3 x 3 case which gives undecidability in ail almost as restricted form as the result of Markov.
We study a problem considered originally by A. Markov in 1947: Given two finitely generated matrix semigroups, determine whether or not they contain a common element. This problem was proved undecidable by Markov for 4 x 4 matrices, even in a very restrict form, and for 3 x 3 matrices by Krom in 1981. Here we give a new proof in the 3 x 3 case which gives undecidability in ail almost as restricted form as the result of Markov.
Turun yliopiston Tutkimustietojärjestelmän portaali