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 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)

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

• 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?)
• An Infinite Hierarchy of Context-Free Languages
• Restricted one-counter machines with undecidable universe problems
• Reversal-bounded multipushdown machines

Cited in

(3)

• On undecidability bounds for matrix decision problems
• 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)