References of "Berthé, Valérie"
     in
Bookmark and Share    
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 (in press)

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

in Discrete Mathematics (in press)

Detailed reference viewed: 8 (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 (in press)

Detailed reference viewed: 7 (0 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 (in press)

Detailed reference viewed: 6 (0 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: 52 (4 ULg)
Full Text
See detailIndex and References
Berthé, Valérie; Rigo, Michel ULg

in Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 7 (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: 6 (2 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: 17 (4 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: 14 (1 ULg)