Lowering Undecidability Bounds for Decision Questions in Matrices

DOI10.1007/11779148_34MaRDI QIDQ3617076zbMATH OpenOpenAlexFDO

Authors Paul C. Bell, Igor Potapov

Publication date 26 March 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11779148_34

zbMATH Keywords

matrix semigroupsmembershippiecewise linear mapstheory of computingvector reachability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) Semigroups of transformations, relations, partitions, etc. (20M20)

Recommendations

• On undecidability bounds for matrix decision problems
• Improved matrix pair undecidability results
• Undecidability bounds for integer matrices using Claus instances
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• The invariance problem for matrix semigroups

Cited in

(8)

• Lower bounds for some decision problems over \(C\)
• On undecidability bounds for matrix decision problems
• Improved matrix pair undecidability results
• The invariance problem for matrix semigroups
• Orbits of linear maps and regular languages
• Undecidability bounds for integer matrices using Claus instances
• About the decision of reachability for register machines
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS

This page was built for publication: Lowering Undecidability Bounds for Decision Questions in Matrices

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