Periodic and Infinite Traces in Matrix Semigroups

DOI10.1007/978-3-540-77566-9_13zbMATH Open1133.03017OpenAlexW2131490285MaRDI QIDQ5448643FDOQ5448643

Paul C. Bell, Igor Potapov

Publication date: 7 March 2008

Published in: SOFSEM 2008: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77566-9_13

Recommendations

• Developments in Language Theory
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
• The Identity Correspondence Problem and Its Applications
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

zbMATH Keywords

undecidabilityPost's correspondence problemcounter automaton

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Thue and Post systems, etc. (03D03) Algebraic systems of matrices (15A30) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40)

Cited In (9)

• Relations in the semigroup of 2 × 2 upper-triangular matrices
• Semi-periodic \infty-tuples
• On injectivity of quantum finite automata
• Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$
• Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$
• Reachability problems in quaternion matrix and rotation semigroups
• Freeness properties of weighted and probabilistic automata over bounded languages
• Acceptance Ambiguity for Quantum Automata
• Developments in Language Theory

This page was built for publication: Periodic and Infinite Traces in Matrix Semigroups

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