Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny (2004) use it.
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...
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 .
Maria Serna, Fatos Xhafa (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We show that some classical P-complete problems can be solved efficiently in NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by ( ln 4 + (1))log , asymptotically with high probability, where is the instance size.
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.
Christian Hagenah, Anca Muscholl (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
The standard procedure to transform a regular expression of size to an -free nondeterministic finite automaton yields automata with states and ( ) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic showed how to build an -free NFA with only ( log()) transitions. The current lower bound on the number of transitions is Ω( log()). A rough running time estimation for the common follow sets (CFS) construction proposed...
A. Frid, D. Jamet (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length . We also give the precise asymptotics for it, which happens to be ( ). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [39 (1982) 67–84], then independently by Mignosi [82 (1991) 71–84], and others.
Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...
Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word is in a multiword if it occurs in word that can be obtained by selecting one single symbol among the symbols provided in each position of . Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word is certain in a multiword . We study the language CERTAIN() of multiwords...
Golnaz Badkobeh, Maxime Crochemore, Michaël Rao (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We investigate the finite repetition threshold for -letter alphabets, ≥ 4, that is the smallest number for which there exists an infinite -free word containing a finite number of -powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (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...
Wolfgang Steiner (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
The (−)-integers are natural generalisations of the -integers, and thus of the integers, for negative real bases. When is the analogue of a Parry number, we describe the structure of the set of (−)-integers by a fixed point of an anti-morphism.
Jean-Louis Merrien (2010)
ESAIM: Mathematical Modelling and Numerical Analysis
Similarity:
We propose a two point subdivision scheme with parameters to draw curves that satisfy Hermite conditions at both ends of . We build three functions and on dyadic numbers and, using infinite products of matrices, we prove that, under assumptions on the parameters, these functions can be extended by continuity on , with and .
Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in ( log ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
Julien Cassaigne, Juhani Karhumäki, Ján Maňuch (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We say that two languages and are conjugates if they satisfy the for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
Jérôme Monnot (2010)
RAIRO - Operations Research
Similarity:
In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem which only differ on a linear transformation of their objective functions. This...