The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 381 –
400 of
408
Classically, in order to resolve an equation u ≈ v over a free
monoid X*, we reduce it by a suitable family of substitutions
to a family of equations uf ≈ vf, , each involving less
variables than u ≈ v, and then combine solutions of uf ≈ vf
into solutions of u ≈ v. The problem is to get in a handy
parametrized form. The method we propose consists in parametrizing the
path traces in the so called graph of prime equations associated to
u ≈ v. We carry out such a parametrization in the case the...
We divide infinite sequences of subword complexity 2n+1 into
four subclasses with respect to left and right special elements
and examine the structure of the subclasses with the help of Rauzy
graphs. Let k ≥ 2 be an integer. If the expansion in base k
of a number is an Arnoux-Rauzy word, then it belongs to Subclass I
and the number is known to be transcendental. We prove the
transcendence of numbers with expansions in the subclasses II and
III.
We consider languages expressed by word equations in two variables and give a complete
characterization for their complexity functions, that is, the functions that give the number of
words of the same length. Specifically, we prove that there are only five types of complexities:
constant, linear, exponential, and two in between constant and linear. For the latter two, we
give precise characterizations in terms of the number of solutions of Diophantine equations of
certain types. In particular,...
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...
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.
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...
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...
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...
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.
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.
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...
We define by simple conditions two wide subclasses of the so-called Arnoux-Rauzy systems; the elements of the first one share the property of (measure-theoretic) weak mixing, thus we generalize and improve a counter-example to the conjecture that these systems are codings of rotations; those of the second one have eigenvalues, which was known hitherto only for a very small set of examples.
Currently displaying 381 –
400 of
408