Loading [MathJax]/extensions/MathZoom.js
Displaying 601 –
620 of
893
We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side u and the right-hand side v of the rule of the system are not quasi-conjugate or are equal, that means if u and v are distinct, there do not exist words x, y and z such that u = xyz and v = zyx. We...
We study deterministic one-way communication complexity of functions with Hankel communication matrices. Some structural properties of such matrices are established and applied to the one-way two-party communication complexity of symmetric Boolean functions. It is shown that the number of required communication bits does not depend on the communication direction, provided that neither direction needs maximum complexity. Moreover, in order to obtain an optimal protocol, it is in any case sufficient...
We study deterministic one-way communication complexity
of functions with Hankel communication matrices.
Some structural properties of such matrices are established
and applied to the one-way two-party communication complexity
of symmetric Boolean functions.
It is shown that the number of required communication bits
does not depend on the communication direction, provided that
neither direction needs maximum complexity.
Moreover, in order to obtain an optimal protocol, it is
in any case sufficient...
For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized...
In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.
On peut définir la pente d'un mot écrit avec des 0 et des 1 comme le nombre de 1 divisé par le nombre de 0, et généraliser cette définition aux mots de longueur infinie. Considérant le lien entre les mots de Christoffel et les fractions continues, on se propose d'étudier le comportement de tels mots lorsqu'on additionne leurs pentes, ou qu'on les multiplie par un entier positif. Après un bref exposé des différentes notions liées aux mots de Christoffel, l'étude de la somme et de la multiplication...
A set C of vertices in a graph G = (V,E) is total dominating in G if all vertices of V are adjacent to a vertex of C. Furthermore, if a total dominating set C in G has the additional property that for any distinct vertices u, v ∈ V C the subsets formed by the vertices of C respectively adjacent to u and v are different, then we say that C is a locating-total dominating set in G. Previously, locating-total dominating sets in strips have been studied by Henning and Jafari Rad (2012). In particular,...
We study infinite words u over an alphabet
satisfying the property
,
where denotes the number of
palindromic factors of length n occurring in the language of u.
We study also infinite words satisfying a stronger property
: every palindrome of u has exactly one palindromic extension in u.
For binary words, the properties and
coincide and these properties characterize Sturmian words, i.e.,
words with the complexity C(n) = n + 1 for any . In this paper, we focus on ternary infinite...
Currently displaying 601 –
620 of
893