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.
Traversing directed Eulerian mazes.
Treewidth and minimum fill-in on -trapezoid graphs.
Triangle-free planar graphs and segment intersection graphs.
Two linear time algorithms for MST on minor closed graph classes
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.
Two sided Sand Piles Model and unimodal sequences
We introduce natural generalizations of two well-known dynamical systems, the Sand Piles Model and the Brylawski's model. We describe their order structure, their reachable configuration's characterization, their fixed points and their maximal and minimal length's chains. Finally, we present an induced model generating the set of unimodal sequences which amongst other corollaries, implies that this set is equipped with a lattice structure.
Two-variable word equations
Two-variable word equations
We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In particular,...
Un algorithme sous-optimal pour construire un graphe -arête connexe de coût minimal
Un nouveau type de preuve mathématique : le théorème des quatre couleurs. I - Exposé préliminaire
Un nouveau type de preuve mathématiques : II - Le théorème des quatre couleurs
Un théorème de décomposition des questionnaires optimaux identifiant des monômes booléens. Applications
Unambiguous erasing morphisms in free monoids
This paper discusses the fundamental combinatorial question of whether or not, for a given string α, there exists a morphism σ such that σ is unambiguous with respect to α, i.e. there exists no other morphism τ satisfying τ(α) = σ(α). While Freydenberger et al. [Int. J. Found. Comput. Sci. 17 (2006) 601–628] characterise those strings for which there exists an unambiguous nonerasing morphism σ, little is known about the unambiguity of erasing morphisms, i.e. morphisms that map symbols...