There exist binary circular power free words of every length.
Three complexity functions
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
Three complexity functions
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
Three complexity functions
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
Three generators for minimal writing-space computations
Three generators for minimal writing-space computations
We construct, for each integer n, three functions from {0,1}n to {0,1} such that any boolean mapping from {0,1}n to {0,1}n can be computed with a finite sequence of assignations only using the n input variables and those three functions.
Three new heuristics for the Steiner problem in graphs.
Three-dimensional 1-bend graph drawings.
Tilings associated with beta-numeration and substitutions.
TimGA: A genetic algorithm for drawing undirected graphs.
Torus knots extremizing the Möbius energy.
Totally greedy coin sets and greedy obstructions.
Tournaments as feedback arc sets.
Towards parametrizing word equations
Classically, in order to resolve an equation over a free monoid , we reduce it by a suitable family of substitutions to a family of equations , , each involving less variables than , and then combine solutions of into solutions of . 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 . We carry out such a parametrization in the case the prime equations in the graph...
Towards parametrizing word equations
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...
Traces of term-automatic graphs
In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...
Track layouts of graphs.
Trajectories of rotations
Transcendence of numbers with an expansion in a subclass of complexity 2n + 1
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.
Transitive Hall sets.