• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Undecidability in Matrices over Laurent Polynomials

Vesa Halava, Tero Harju, Undecidability in Matrices over Laurent Polynomials. Advances in Applied Mathematics 33(4), 747–752, 2004.

Abstract:

We show that it is undecidable for finite sets $S$ of upper triangular
4x4-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.

BibTeX entry:

@ARTICLE{jHaHa04a,
  title = {Undecidability in Matrices over Laurent Polynomials},
  author = {Halava, Vesa and Harju, Tero},
  journal = {Advances in Applied Mathematics},
  volume = {33},
  number = {4},
  pages = {747–752},
  year = {2004},
  keywords = {undecidability, matrices, Laurent polynomials},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication