Un algorithme sous-optimal pour construire un graphe -arête connexe de coût minimal
Un nouveau type de preuve mathématique : le théorème des quatre couleurs. I - Exposé préliminaire
Un nouveau type de preuve mathématiques : II - Le théorème des quatre couleurs
Un théorème de décomposition des questionnaires optimaux identifiant des monômes booléens. Applications
Unambiguous erasing morphisms in free monoids
This paper discusses the fundamental combinatorial question of whether or not, for a given string α, there exists a morphism σ such that σ is unambiguous with respect to α, i.e. there exists no other morphism τ satisfying τ(α) = σ(α). While Freydenberger et al. [Int. J. Found. Comput. Sci. 17 (2006) 601–628] characterise those strings for which there exists an unambiguous nonerasing morphism σ, little is known about the unambiguity of erasing morphisms, i.e. morphisms that map symbols...
Unavoidable set : extension and reduction
Unavoidable Set: Extension and Reduction
We give an explicit criterion for unavoidability of word sets. We characterize extendible, finitely and infinitely as well, elements in them. We furnish a reasonable upper bound and an exponential lower bound on the maximum leghth of words in a reduced unavoidable set of a given cardinality.
Unavoidable sets. (Ensembles inévitables.)
Undecidability of infinite post correspondence problem for instances of size 8
The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...
Undecidability of infinite post correspondence problem for instances of size 8
The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...
Undecidability of infinite post correspondence problem for instances of Size 9
In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst.36 (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable...
Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères
Une caractérisation simple des nombres de Sturm
Un mot sturmien est la discrétisation d’une droite de pente irrationnelle. Un nombre de Sturm est la pente d’un mot sturmien qui est invariant par une substitution non triviale. Ces nombres sont certains irrationnels quadratiques caractérisés par la forme de leur développement en fraction continue. Nous donnons une caractérisation très simple des nombres de Sturm : un nombre irrationnel positif est de Sturm (de première espèce) si et seulement s’il est quadratique et à conjugué négatif.
Une généralisation du théorème de Cobham
Nous généralisons le théorème de Cobham ([2]), en démontrant qu'une partie infinie de ℕ est reconnaissable en base k (k entier strictement plus grand que un) et reconnaissable dans un système de numération associé à un nombre de Pisot unitaire (ayant une propriété arithmétique supplémentaire) si et seulement si elle est ultimement périodique.
Uniformly bounded duplication codes
Duplication is the replacement of a factor w within a word by ww. This operation can be used iteratively to generate languages starting from words or sets of words. By undoing duplications, one can eventually reach a square-free word, the original word's duplication root. The duplication root is unique, if the length of duplications is fixed. Based on these unique roots we define the concept of duplication code. Elementary properties are stated, then the conditions under which infinite duplication...
Uniformly growing backtrack trees
Union of all the minimum cycle bases of a graph.
Unique decipherability in the additive monoid of sets of numbers
Sets of integers form a monoid, where the product of two sets A and B is defined as the set containing a+b for all and . We give a characterization of when a family of finite sets is a code in this monoid, that is when the sets do not satisfy any nontrivial relation. We also extend this result for some infinite sets, including all infinite rational sets.
Unique decipherability in the additive monoid of sets of numbers
Sets of integers form a monoid, where the product of two sets A and B is defined as the set containing a+b for all and . We give a characterization of when a family of finite sets is a code in this monoid, that is when the sets do not satisfy any nontrivial relation. We also extend this result for some infinite sets, including all infinite rational sets.
Unit rectangle visibility graphs.