Periodic and Infinite Traces in Matrix Semigroups

DOI10.1007/978-3-540-77566-9_13zbMath1133.03017OpenAlexW2131490285MaRDI QIDQ5448643

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

zbMATH Keywords

undecidabilityPost's correspondence problemcounter automaton

Mathematics Subject Classification ID

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

Related Items (7)

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

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