Let $ϵ=({ϵ}_n{)}_{n\ge 0}$ be the Thue-Morse sequence, i.e., the sequence defined by the recurrence equations:$${ϵ}_0=1,{ϵ}_{2n}={ϵ}_n,{ϵ}_{2n+1}=1-{ϵ}_n.$$We consider $\left\{\right|{ℰ}_n^p|{\}}_{n\ge 1,p\ge 0}$, the double sequence of Hankel determinants (modulo 2) associated with the Thue-Morse sequence. Together with three other sequences, it obeys a set of sixteen recurrence equations. It is shown to be automatic. Applications are given, namely to combinatorial properties of the Thue-Morse sequence and to the existence of certain Padé approximants of the power series ${\sum }_{n\ge 0}(-1{)}^{{ϵ}_n}{x}^n$.

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring...

Let $𝒫$ be a hereditary property of words, i.e., 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 $n+1$ words of length $n$ for every $n$ or, for some $N$, it contains at most $N$ words of length $n$ for every $n$. More importantly, we prove the following quantitative extension of this result: if $𝒫$ has $m\le n$ words of length $n$ then, for every $k\ge n+m$, it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2\rfloor$ words of length...

Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most...

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....

We present two methods based on decimation for computing finite billiard words on any finite alphabet. The first method computes finite billiard words by iteration of some transformation on words. The number of iterations is explicitly bounded. The second one gives a direct formula for the billiard words. Some results remain true for infinite standard Sturmian words, but cannot be used for computation as they only are limit results.