L'ubomíra Balková, Zuzana Masáková (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
We study the palindromic complexity of infinite words , the fixed points of the substitution over a binary alphabet, , , with , which are canonically associated with quadratic non-simple Parry numbers .
Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...
Z. Masáková, T. Vávra (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We consider numeration systems with base and − , for quadratic Pisot numbers and focus on comparing the combinatorial structure of the sets Z and Z of numbers with integer expansion in base , resp. − . Our main result is the comparison of languages of infinite words and coding the ordering of distances between consecutive - and (− )-integers. It turns out that for a class of roots of − − , the languages coincide, while for other...
József Balogh, Béla Bollobás (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈...
Jing Dong, Qinghui Liu (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [36 (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [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 of size 8.
Arturo Carpi, Aldo de Luca (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words ...
Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu (2013)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Most of the constructions of infinite words having polynomial subword complexity are quite complicated, , sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words over a binary alphabet { } with polynomial subword complexity . Assuming contains an infinite number of ’s, our method is based on the gap function which gives the distances between consecutive ’s. It is known that...
Luís Balsa Bicho, António Ornelas (2014)
ESAIM: Control, Optimisation and Calculus of Variations
Similarity:
We prove of vector minimizers () = (||) to multiple integrals ∫ ((), |()|) on a ⊂ ℝ, among the Sobolev functions (·) in + (, ℝ), using a : ℝ×ℝ → [0,∞] with (·) and . Besides such basic hypotheses, (·,·) is assumed to satisfy also...
Andrzej Szepietowski (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton is hyper-minimized if no automaton with fewer states is almost equivalent to . A regular language is canonical if the minimal automaton accepting is hyper-minimized. The asymptotic state complexity () of a regular language is the number of states of a hyper-minimized automaton for a language finitely different from . In this paper we show...
Fábio Júlio Valentim (2012)
Annales de l'I.H.P. Probabilités et statistiques
Similarity:
Fix a polynomial of the form () = + ∑2≤≤ =1 with (1) gt; 0. We prove that the evolution, on the diffusive scale, of the empirical density of exclusion processes on , with conductances given by special class of functions, is described by the unique weak solution of the non-linear parabolic partial differential equation = ∑ ...