Undecidability in matrices over Laurent polynomials.

DOI10.1016/J.AAM.2004.04.002zbMATH Open1147.20315OpenAlexW2050618314MaRDI QIDQ705234FDOQ705234

Vesa Halava, Tero Harju

Publication date: 26 January 2005

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2004.04.002

Recommendations

• scientific article; zbMATH DE number 2087212
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Examples of undecidable problems for 2-generator matrix semigroups
• On Markov's undecidability theorem for integer matrices.
• Undecidability bounds for integer matrices using Claus instances

zbMATH Keywords

finite automataundecidabilityfinite sets of upper triangular matricesmatrices over Laurent polynomials

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Reversal-bounded multipushdown machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Infinite Hierarchy of Context-Free Languages
• Restricted one-counter machines with undecidable universe problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• On undecidability bounds for matrix decision problems
• Title not available (Why is that?)

This page was built for publication: Undecidability in matrices over Laurent polynomials.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705234)