Permutation properties and the Fibonacci semigroup.
Sur les sous-monoïdes très purs
On the product of balanced sequences
The product = ⊗ of two sequences and is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product of two balanced sequences is balanced too. In the case and are binary sequences, we prove, as a main result, that, if such a product is balanced and () = 4, then is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the...
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumäki on the characterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators,...
On the product of balanced sequences
The product = ⊗ of two sequences and is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product of two balanced sequences is balanced too. In the case and are binary sequences, we prove, as a main result, that, if such a product is balanced and () = 4, then is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the...
A synchronization property of pure subsemigroups.
Some results on finite maximal codes
Unambiguous recognizable two-dimensional languages
We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of...
On some factorization problems.
Page 1