RAIRO-Theor. Inf. Appl.
Volume 46, Number 3, July-September 2012
|Page(s)||355 - 399|
|Published online||29 May 2012|
On the decidability of semigroup freeness∗
Institut de mathématiques de Luminy, case 907, 163 avenue de Luminy, 13288
Marseille Cedex 9,
2 Lehrstuhl für Bioinformatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany
Accepted: 7 February 2012
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability of the freeness problem over three-by-three integer matrices. Both results led to the publication of many subsequent papers. The aim of the present paper is (i) to present general results about freeness problems, (ii) to study the decidability of freeness problems over various particular semigroups (special attention is devoted to multiplicative matrix semigroups), and (iii) to propose precise, challenging open questions in order to promote the study of the topic.
Mathematics Subject Classification: 20M05 / 03B25 / 15A30
Key words: Decidability / semigroup freeness / matrix semigroups / Post correspondence problem
© EDP Sciences 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.