Remarks concerning the freeness problem over morphism and matrix semigroups.

DOI10.1016/J.TCS.2014.08.013zbMATH Open1339.20049OpenAlexW2076013530MaRDI QIDQ300262FDOQ300262

Authors: Juha Honkala 

Publication date: 27 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.08.013

Recommendations

• The freeness problem over matrix semigroups and bounded languages
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On the decidability of semigroup freeness.
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Freeness problem for matrix semigroups of Parikh matrices

zbMATH Keywords

decidabilitymatrix semigroupsfreeness problemmatrix semiringsmorphism semigroups

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Decidability of theories and sets of sentences (03B25) Semirings (16Y60) Free semigroups, generators and relations, word problems (20M05)

Cites Work

• On finite semigroups of matrices
• On the decidability of semigroup freeness.
• Undecidability bounds for integer matrices using Claus instances
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Reachability problems in quaternion matrix and rotation semigroups

Cited In (15)

• The freeness problem over matrix semigroups and bounded languages
• On the problem of freeness of multiplicative matrix semigroups
• Scalar ambiguity and freeness in matrix semigroups over bounded languages
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On some free semigroups, generated by matrices
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
• Commuting upper triangular binary morphisms
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• Freeness properties of weighted and probabilistic automata over bounded languages
• NUMBER SYSTEMS AND THE INJECTIVITY PROBLEM FOR MATRIX REPRESENTATIONS OF FREE MONOIDS
• Language-theoretic problems in certain matrix monoids
• A characterization of free pairs of upper triangular free monoid morphisms
• On the decidability of semigroup freeness.
• Freeness problem for matrix semigroups of Parikh matrices
• A simple undecidable problem for free groups

This page was built for publication: Remarks concerning the freeness problem over morphism and matrix semigroups.

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