The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.
La fonction de récurrence d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur . Nous la calculons explicitement pour les suites d’Arnoux-Rauzy, définies par des conditions combinatoires qui en font une généralisation naturelle des suites sturmiennes. Puis nous répondons à une question de Morse et Hedlund (1940) en montrant que ne peut avoir une limite finie pour aucune suite non ultimement périodique.
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word from a given set of substrings (fragments) of a word . We introduce an hypothesis involving the set of fragments and the maximal length of the minimal forbidden factors of . Such hypothesis allows us to reconstruct uniquely the word from the set in linear...
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments) of a word w. We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w. Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear...
In this paper, we extend to automorphisms of free groups some results and constructions that classically hold for morphisms of the free monoid, i.e., the so-called substitutions. A geometric representation of the attractive lamination of a class of automorphisms of the free group (irreducible with irreducible powers (iwip) automorphisms) is given in the case where the dilation coefficient of the automorphism is a unit Pisot number. The shift map associated with the attractive symbolic lamination...
This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and...
The necessary and sufficient conditions are extracted for periodicity of bi-ideals. They cover infinitely and finitely generated bi-ideals.
We extend the DSV method of computing the growth series of an unambiguous context-free language to the larger class of indexed languages. We illustrate the technique with numerous examples.
In this paper results concerning structural and approximability properties of the subclass of NP-Complete Optimization Problems, defined over a lattice are considered. First, various approaches to the concept of Fully Polynomial Approximation Scheme are presented with application to several known problems in the class of NP-Complete Optimization Problems.Secondly, a characterization of full Approximability for the class of Max Subset Problems is introduced.
Parikh matrices have become a useful tool for investigation of subword structure of words. Several generalizations of this concept have been considered. Based on the concept of formal power series, we describe a general framework covering most of these generalizations. In addition, we provide a new characterization of binary amiable words – words having a common Parikh matrix.
Expansions in noninteger bases often appear in number theory and probability theory, and they are closely connected to ergodic theory, measure theory and topology. For two-letter alphabets the golden ratio plays a special role: in smaller bases only trivial expansions are unique, whereas in greater bases there exist nontrivial unique expansions. In this paper we determine the corresponding critical bases for all three-letter alphabets and we establish the fractal nature of these bases in dependence...