On the decidability of membership in matrix-exponential semigroups

DOI10.1145/3286487MaRDI QIDQ5215447zbMATH OpenOpenAlexWikidataFDO

Authors Joël Ouaknine, Amaury Pouly, J. Sousa Pinto, James Worrell

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3286487

zbMATH Keywords

commuting matriceshybrid automatalinear forms in logarithmsmatrix exponentialmatrix logarithmsmatrix reachability

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Matrix exponential and similar functions of matrices (15A16) Free semigroups, generators and relations, word problems (20M05) Semigroups of transformations, relations, partitions, etc. (20M20)

Recommendations

• Solvability of Matrix-Exponential Equations
• Decidability of the membership problem for \(2\times 2\) integer matrices
• On the membership of invertible diagonal and scalar matrices
• Developments in Language Theory
• On the computational complexity of matrix semigroup problems

Cited in

(5)

• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• scientific article; zbMATH DE number 7559393 (Why is no real title available?)
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• Mathematical Foundations of Computer Science 2004
• Termination of linear loops under commutative updates

This page was built for publication: On the decidability of membership in matrix-exponential semigroups

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