Radial level planarity testing and embedding in linear time.
Ramanujan grammar and Cayley trees. (Grammaire de Ramanujan et arbres de Cayley.)
Ramsey theory applications.
Ranking and unranking of a generalized Dyck language and the application to the generation of random trees.
Rational approximations to algebraic Laurent series with coefficients in a finite field
We give a general upper bound for the irrationality exponent of algebraic Laurent series with coefficients in a finite field. Our proof is based on a method introduced in a different framework by Adamczewski and Cassaigne. It makes use of automata theory and, in our context, of a classical theorem due to Christol. We then introduce a new approach which allows us to strongly improve this general bound in many cases. As an illustration, we give a few examples of algebraic Laurent series for which...
Rationality, irrationality, and Wilf equivalence in generalized factor order.
Recognizing the -structure of claw-free graphs and a larger graph class.
Reconnaissabilité des substitutions et complexité des suites automatiques
Recouvrement et partition en chaînes des arêtes d'un graphe cubique
Rectilinear Planar Layouts and Bipolar Orientations of Planar Graphs.
Reducing Off-Line to On-Line: an Example and Its Applications
Reducing the adjacency matrix of a tree.
Répartition des suites et substitutions
Repetition thresholds for subdivided graphs and trees
The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
Repetition thresholds for subdivided graphs and trees
The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
Repetitions in the Fibonacci infinite word
Représentation par automate de fonctions continues de tore
Soient et un sous-système. est une représentation en base d’une fonction du tore si pour tout point du tore, ses développements en base sont liés par le couplage aux développements en base de . On prouve que si est représentable en base alors , où . Réciproquement, toutes les fonctions de ce type sont représentables en base par un transducteur. On montre finalement que les fonctions du tore qui peuvent être représentées par automate cellulaire sont exclusivement les multiplications...
Representations of a free group of rank two by time-varying Mealy automata
In the group theory various representations of free groups are used. A representation of a free group of rank two by the so-calledtime-varying Mealy automata over the changing alphabet is given. Two different constructions of such automata are presented.
Restricted permutations from Catalan to Fine and back.
Return words in sturmian and episturmian words