On the decidability of semigroup freeness

DOI10.1051/ita/2012010zbMath1252.20050arXiv0808.3112OpenAlexW2002395412MaRDI QIDQ2905326

François Nicolas, Julien Cassaigne

Publication date: 27 August 2012

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0808.3112

zbMATH Keywords

undecidabilitydecidabilityfree monoidsmatrix semigroupsPost correspondence problemfreeness problemsemigroup freeness

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic systems of matrices (15A30)

Related Items

Remarks concerning the freeness problem over morphism and matrix semigroups., Solving the membership problem for parabolic Möbius monoids, A characterization of free pairs of upper triangular free monoid morphisms, The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete, Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$, Products of matrices and recursively enumerable sets, A Kraft-McMillan inequality for free semigroups of upper-triangular matrices, On injectivity of quantum finite automata, Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\), Strongly automatic semigroups, Freeness Problem for Matrix Semigroups of Parikh Matrices, The freeness problem over matrix semigroups and bounded languages, On the problem of freeness of multiplicative matrix semigroups, Freeness properties of weighted and probabilistic automata over bounded languages, Unnamed Item, Relations in the semigroup of 2 × 2 upper-triangular matrices, Acceptance Ambiguity for Quantum Automata, On the membership problem for some subgroups of \(SL_2(\mathbf{Z})\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When is a pair of matrices mortal?
• On the rational subset problem for groups.
• Reachability problems in quaternion matrix and rotation semigroups
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• On finite semigroups of matrices
• Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices
• Undecidable problems for probabilistic automata of fixed dimension
• The boundedness of all products of a pair of matrices is undecidable
• Binary (generalized) Post Correspondence Problem
• Decision problems for semi-Thue systems with a few rules
• The mortality problem for matrices of low dimensions
• On the problem of freeness of multiplicative matrix semigroups
• Mortality in Matrix Semigroups
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• Polynomial-time algorithm for the orbit problem
• More on Mortality
• Mortality of 2 × 2 Matrices
• Pell's Equation and Two Generator Free Möbius Groups
• Beardon's Diophantine Equations and Non-Free Möbius Groups
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Some decision problems on integer matrices
• Recursive Unsolvability of a problem of Thue
• Unsolvability in 3 × 3 Matrices
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• A variant of a recursively unsolvable problem
• Free semigroups of \(2\times 2\) matrices