On some properties of the syntactic semigroup of a very pure subsemigroup
On some subsemigroups of a free semigroup.
On syntacticity of finite regular semigroups.
On the decidability of semigroup freeness∗
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....
On the decidability of semigroup freeness
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...
On the decidability of semigroup freeness∗
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....
On the deficit of a set of words.
On the degree of finite maximal biprefix codes.
On the greatest congruence relation contained in an equivalence relation and its applications to the algebraic theory of machines
On the periodicity of morphisms on free monoids
On the structure of some group codes.
On the topological structure of a finitely generated semigroup of matrices.
On Varieties of Literally Idempotent Languages
A language L ⊆A* is literally idempotent in case that ua2v ∈ L if and only if uav ∈ L, for each u,v ∈ A*, a ∈ A. Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the...
Partially abelian squarefree words
Periodic endomorphisms of a free monoid.
Pour le monoïde plaxique
Cet article est probablement le dernier texte de mathématiques écrit en vue de sa publication par M. P. Schützenberger, décédé en juillet 1996. Il était offert par son auteur en hommage à André Lentin, à l'occasion d'un colloque tenu en l'honneur de celui-ci le 23 février 1996 ; M. P. Schützenberger, déjà très malade, n'avait pu participer à cette rencontre, mais avait tenu à rédiger, non sans souffrances, une contribution scientifique qui témoignât de son amitié pour A. Lentin. Lorsque je lui dis...
Purity in the category of M-sets.
Quasi-completely right disjunctive languages.
Quelques langages algébriques
-systems of unary algebras. II: Maximal and minimal subalgebras of the direct products of unary algebras