Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Combinatorics, Words and Symbolic Dynamics ; Rigo, Michel 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)Specular sets ; ; 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)Factor Complexity of S-adic words generated by the Arnoux-Rauzy-Poincaré Algorithm Labbé, Sébastien ; in Advances in Applied Mathematics (2015), 63 Detailed reference viewed: 7 (0 ULg)Acyclic, connected and tree sets ; ; et al in Monatshefte für Mathematik (2015), 176(4), 521550 Detailed reference viewed: 13 (1 ULg)Bifix codes and interval exchanges ; ; et al in Journal of Pure and Applied Algebra (2015), 219(7), 27812798 Detailed reference viewed: 12 (2 ULg)Maximal bifix decoding ; ; et al in Discrete Mathematics (2015), 338(5), 725742 Detailed reference viewed: 16 (5 ULg)The finite index basis property ; ; et al in Journal of Pure and Applied Algebra (2015), 219(7), 25212537 Detailed reference viewed: 13 (2 ULg)On the concrete complexity of the successor function ; ; Rigo, Michel et al Conference (2012, September 11) We consider two kinds of questions about the successor function. The ﬁrst 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 ﬁrst 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)Index and References ; Rigo, Michel in Combinatorics, Automata and Number Theory (2010) Detailed reference viewed: 11 (1 ULg)Preliminaries (Chapter 1) ; Rigo, Michel in Berthé, Valérie; Rigo, Michel (Eds.) Combinatorics, Automata and Number Theory (2010) Detailed reference viewed: 10 (2 ULg)Introduction ; Rigo, Michel in Rigo, Michel; Berthé, Valérie (Eds.) Combinatorics, Automata and Number Theory (2010) Detailed reference viewed: 10 (3 ULg)Combinatorics, Automata and Number Theory 2006 ; Lecomte, Pierre ; Rigo, Michel in Theoretical Computer Science (2008), 391 Detailed reference viewed: 21 (6 ULg)On the cost and complexity of the successor function ; ; Rigo, Michel 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) |
||