Atnaujinkite slapukų nuostatas

Combinatorics, Words and Symbolic Dynamics [Kietas viršelis]

Edited by (Université de Ličge, Belgium), Edited by (Université de Paris VII (Denis Diderot))
  • Formatas: Hardback, 496 pages, aukštis x plotis x storis: 242x163x37 mm, weight: 940 g, Worked examples or Exercises; 23 Halftones, unspecified; 112 Line drawings, unspecified
  • Serija: Encyclopedia of Mathematics and its Applications
  • Išleidimo metai: 26-Feb-2016
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1107077028
  • ISBN-13: 9781107077027
Kitos knygos pagal šią temą:
Combinatorics, Words and Symbolic DynamicsDidesnis paveikslėlis
  • Formatas: Hardback, 496 pages, aukštis x plotis x storis: 242x163x37 mm, weight: 940 g, Worked examples or Exercises; 23 Halftones, unspecified; 112 Line drawings, unspecified
  • Serija: Encyclopedia of Mathematics and its Applications
  • Išleidimo metai: 26-Feb-2016
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1107077028
  • ISBN-13: 9781107077027
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9781107077027.html
Raktažodžiai:
"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"--

Daugiau informacijos

Surveys trends arising from the applications and interactions between combinatorics, symbolic dynamics and theoretical computer science.
List of contributors
ix
Preface xi
Acknowledgments xix
1 Preliminaries
1(17)
V. Berthe
M. Rigo
1.1 Conventions
1(1)
1.2 Words
1(3)
1.3 Morphisms
4(1)
1.4 Languages and machines
5(5)
1.5 Symbolic dynamics
10(8)
2 Expansions in non-integer bases
18(41)
M. De Vries
V. Komornik
2.1 Introduction
18(1)
2.2 Greedy and lazy expansions
19(3)
2.3 On the cardinality of the sets εβ(x)
22(4)
2.4 The random map Kβ and infinite Bernoulli convolutions
26(9)
2.5 Lexicographic characterisations
35(4)
2.6 Univoque bases
39(11)
2.7 Univoque sets
50(5)
2.8 A two-dimensional univoque set
55(1)
2.9 Final remarks
56(1)
2.10 Exercises
57(2)
3 Medieties, end-first algorithms, and the case of Rosen continued fractions
59(42)
B. Rittaud
3.1 Introduction
59(3)
3.2 Generalities
62(6)
3.3 Examples
68(8)
3.4 End-first algorithms
76(6)
3.5 Medieties with k letters
82(7)
3.6 An end-first algorithm for k-medieties
89(3)
3.7 Exercises
92(8)
3.8 Open problems
100(1)
4 Repetitions in words
101(50)
N. Rampersad
J. Shallit
4.1 Introduction
101(1)
4.2 Avoidability
102(12)
4.3 Dejean's theorem
114(6)
4.4 Avoiding repetitions in arithmetic progressions
120(3)
4.5 Patterns
123(1)
4.6 Abelian repetitions
123(11)
4.7 Enumeration
134(9)
4.8 Decidability for automatic sequences
143(2)
4.9 Exercises
145(1)
4.10 Notes
146(5)
5 Text redundancies
151(24)
G. Badkobeh
M. Crochemore
C. S. Iliopoulos
M. Kubica
5.1 Redundancy: a versatile notion
151(2)
5.2 Avoiding repetitions and repeats
153(4)
5.3 Finding repetitions and runs
157(6)
5.4 Finding repeats
163(4)
5.5 Finding covers and seeds
167(4)
5.6 Palindromes
171(4)
6 Similarity relations on words
175(38)
V. Halava
T. Harju
T. Karki
6.1 Introduction
175(1)
6.2 Preliminaries
176(5)
6.3 Coding
181(5)
6.4 Relational periods
186(18)
6.5 Repetitions in relational words
204(7)
6.6 Exercises and problems
211(2)
7 Synchronised automata
213(28)
M.-P. Beal
D. Perrin
7.1 Introduction
213(1)
7.2 Definitions
214(1)
7.3 Cerny's conjecture
215(14)
7.4 Road colouring
229(12)
8 Cellular automata, tilings and (un)computability
241(55)
J. Kari
8.1 Cellular automata
242(18)
8.2 Tilings and undecidability
260(19)
8.3 Undecidability concerning cellular automata
279(14)
8.4 Conclusion
293(1)
8.5 Exercises
293(3)
9 Multidimensional shifts of finite type and sofic shifts
296(63)
M. Hochman
9.1 Introduction
296(1)
9.2 Shifts of finite type and sofic shifts
297(8)
9.3 Basic constructions and undecidability
305(12)
9.4 Degrees of computability
317(9)
9.5 Slices and subdynamics of sofic shifts
326(16)
9.6 Frequencies, word growth and periodic points
342(17)
10 Linearly recursive sequences and Dynkin diagrams
359(42)
C. Reutenauer
10.1 Introduction
359(1)
10.2 SL2-tilings of the plane
360(1)
10.3 SL2-tiling associated with a bi-infinite discrete path
361(2)
10.4 Proof of Theorem 10.3.1
363(2)
10.5 N-rational sequences
365(4)
10.6 N-rationality of the rays in SL2-tilings
369(1)
10.7 Friezes
370(7)
10.8 Dynkin diagrams
377(5)
10.9 Rational frieze implies Dynkin diagram
382(3)
10.10 Rationality for Dynkin diagrams of type A and A
385(2)
10.11 Further properties of SL2-tilings
387(10)
10.12 The other extended Dynkin diagrams
397(1)
10.13 Problems and conjectures
397(1)
10.14 Exercises
398(3)
11 Pseudo-randomness of a random Kronecker sequence. An instance of dynamical analysis
401(42)
E. Cesaratto
B. Vallee
11.1 Introduction
401(3)
11.2 Five parameters for Kronecker sequences
404(11)
11.3 Probabilistic models
415(2)
11.4 Statements of the main results
417(6)
11.5 Dynamical analysis
423(7)
11.6 Balanced costs
430(6)
11.7 Unbalanced costs
436(2)
11.8 Summary of functional analysis
438(3)
11.9 Conclusion and open problems
441(2)
Bibliography 443(21)
Notation index 464(2)
General index 466
Valérie Berthé is a CNRS Research Director at LIAFA (Laboratoire d'Informatique Algorithmique: Fondements et Applications) at the Université Paris Diderot, Paris 7. She is Deputy Director of the Fondation Sciences Mathématiques de Paris and has authored 70 journal or conference papers. Her main research interests are tilings, numeration systems, substitutive dynamicals systems and symbolic dynamics. Michel Rigo is a full professor in the Department of Mathematics at the Université de Ličge, Belgium, and head of the research group in discrete mathematics. He has authored more than 50 journal or conference papers and two books. His main research interests are formal language theory, numeration systems and combinatorics on words.