The paper deals with the decomposition and with the boundarz and hull construction of the so-called nondense point set. This problem and its applications have been frequently studied in computational geometry, raster graphics and, in particular, in the image processing (see e.g. [3], [6], [7], [8], [9], [10]). We solve a problem of the point set decomposition by means of certain relations in graph theory.
We investigate the finite repetition threshold for k-letter alphabets, k ≥ 4, that is the smallest number r for which there exists an infinite r+-free word containing a finite number of r-powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (i.e. a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture that this number...
We define finite type invariants for cyclic equivalence classes of nanophrases and construct universal invariants. Also, we identify the universal finite type invariant of degree 1 essentially with the linking matrix. It is known that extended Arnold basic invariants to signed words are finite type invariants of degree 2, by Fujiwara's work. We give another proof of this result and show that those invariants do not provide the universal one of degree 2.
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.
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.