Remarks concerning the freeness problem over morphism and matrix semigroups.

DOI10.1016/J.TCS.2014.08.013MaRDI QIDQ300262zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(15)

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

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)