References of "Berthé, Valérie"
     in
Bookmark and Share    
See detailCombinatorics, Words and Symbolic Dynamics
Berthé, Valérie; Rigo, Michel ULg

Book published by Cambridge University Press (2016)

Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear ... [more ▼]

Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear exposition of some recent results, and emphasise the emerging connections between these different fields. Topics include combinatorics on words, pattern avoidance, graph theory, tilings and theory of computation, multidimensional subshifts, discrete dynamical systems, ergodic theory, numeration systems, dynamical arithmetics, automata theory and synchronised words, analytic combinatorics, continued fractions and probabilistic models. Each topic is presented in a way that links it to the main themes, but then they are also extended to repetitions in words, similarity relations, cellular automata, friezes and Dynkin diagrams. The book will appeal to graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, tilings and stringology. It will also interest biologists using text algorithms. [less ▲]

Detailed reference viewed: 19 (0 ULg)
Full Text
Peer Reviewed
See detailSpecular sets
Berthé, Valérie; Felice, Clelia; Delecroix, Vincent et al

in Manea, Florin; Nowotka, Dirk (Eds.) Combinatorics on Words: 10th International Conference, WORDS 2015, Kiel, Germany, September 14-17, 2015, Proceedings (2015)

Detailed reference viewed: 11 (5 ULg)
Full Text
Peer Reviewed
See detailFactor Complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré Algorithm
Labbé, Sébastien ULg; Berthé, Valérie

in Advances in Applied Mathematics (2015), 63

Detailed reference viewed: 7 (0 ULg)
Full Text
Peer Reviewed
See detailAcyclic, connected and tree sets
Berthé, Valérie; De Felice, Clelia; Dolce, Francesco et al

in Monatshefte für Mathematik (2015), 176(4), 521550

Detailed reference viewed: 13 (1 ULg)
Full Text
Peer Reviewed
See detailBifix codes and interval exchanges
Berthé, Valérie; De Felice, Clelia; Dolce, Francesco et al

in Journal of Pure and Applied Algebra (2015), 219(7), 27812798

Detailed reference viewed: 12 (2 ULg)
Full Text
Peer Reviewed
See detailMaximal bifix decoding
Berthé, Valérie; De Felice, Clelia; Dolce, Francesco et al

in Discrete Mathematics (2015), 338(5), 725742

Detailed reference viewed: 16 (5 ULg)
Full Text
Peer Reviewed
See detailThe finite index basis property
Berthé, Valérie; De Felice, Clelia; Dolce, Francesco et al

in Journal of Pure and Applied Algebra (2015), 219(7), 25212537

Detailed reference viewed: 13 (2 ULg)
Full Text
Peer Reviewed
See detailOn the concrete complexity of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel ULg et al

Conference (2012, September 11)

We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n ... [more ▼]

We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n integers (or more generally on the first n elements in a given language). This leads to the notion of amortized (or average) carry propagation when applying the successor function. The second question is a computational issue: estimating the number of operations (in classical terms of Turing machines complexity) required to compute the representations of the first n integers from the first one by applying n times the successor function. This leads to the notion of (amortized) complexity, i.e., the average amount of computations required to obtain the successor of an element. [less ▲]

Detailed reference viewed: 84 (5 ULg)
Full Text
See detailIndex and References
Berthé, Valérie; Rigo, Michel ULg

in Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 11 (1 ULg)
Full Text
See detailPreliminaries (Chapter 1)
Berthé, Valérie; Rigo, Michel ULg

in Berthé, Valérie; Rigo, Michel (Eds.) Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 10 (2 ULg)
Full Text
See detailIntroduction
Berthé, Valérie; Rigo, Michel ULg

in Rigo, Michel; Berthé, Valérie (Eds.) Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 10 (3 ULg)
Full Text
Peer Reviewed
See detailCombinatorics, Automata and Number Theory 2006
Berthé, Valérie; Lecomte, Pierre ULg; Rigo, Michel ULg

in Theoretical Computer Science (2008), 391

Detailed reference viewed: 21 (6 ULg)
Full Text
Peer Reviewed
See detailOn the cost and complexity of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel ULg et al

in Arnoux, P.; Bédaride, N. (Eds.) Proceedings of WORDS 2007 (2007)

For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word ... [more ▼]

For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word of a genealogically ordered language L onto the (n+1)-th word of L. We show that, if the ratio of the number of elements of length n + 1 over the number of elements of length n of the language has a limit b> 1, then the amortized cost of the successor function is equal to b/(b − 1). From this, we deduce the value of the amortized cost for several classes of numeration systems (integer base systems, canonical numeration systems associated with a Parry number, abstract numeration systems built on a rational language, and rational base numeration systems). [less ▲]

Detailed reference viewed: 15 (1 ULg)