Undecidability in matrices over Laurent polynomials\

: Halava V, Harju T

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2004

: Advances in Applied Mathematics

: ADVANCES IN APPLIED MATHEMATICS

: ADV APPL MATH

: 33

: 4

: 747

: 752

: 6

: 0196-8858

DOI: https://doi.org/10.1016/j.aam.2004.04.002

We show that it is undecidable for finite sets S of upper triangular (4 x 4)-matrices over Z[x, x(-1)] whether or not all elements in the semigroup generated by S have a nonzero constant term in some of the Laurent polynomials of the first row. This result follows from a representations of the integer weighted finite automata by matrices over Laurent polynomials. (C) 2004 Elsevier Inc. All rights reserved.

Mathematics