Undecidability in matrices over Laurent polynomials.

DOI10.1016/J.AAM.2004.04.002MaRDI QIDQ705234zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

finite automatafinite sets of upper triangular matricesmatrices over Laurent polynomialsundecidability

Mathematics Subject Classification ID

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

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

Cites work

• An Infinite Hierarchy of Context-Free Languages
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 1339970 (Why is no real title available?)
• scientific article; zbMATH DE number 2245556 (Why is no real title available?)
• Restricted one-counter machines with undecidable universe problems
• Reversal-bounded multipushdown machines

Cited in

(4)

• On undecidability bounds for matrix decision problems
• scientific article; zbMATH DE number 1339970 (Why is no real title available?)
• Products of matrices and recursively enumerable sets
• scientific article; zbMATH DE number 2087212 (Why is no real title available?)

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)