Autore	Rigo Michel
Pubbl/distr/stampa	London, England ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2016
Descrizione fisica	1 online resource : illustrations
Disciplina	511.5
Collana	Computer Engineering Series
Soggetto topico	Graph theory Combinatorial analysis
ISBN	1-119-05864-3 1-119-05861-9 1-119-00898-0
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Record Nr.	UNINA-9910153179703321

Autore	Rigo Michel
Edizione	[1st ed.]
Pubbl/distr/stampa	Hoboken, : John Wiley & Sons, Inc., 2014
Descrizione fisica	1 online resource (338 p.)
Disciplina	005.2
Collana	Networks and Telecommunications Series
Soggetto topico	Machine theory Formal languages Computer programming Computational linguistics Computer programming -- Congresses Formal languages -- Congresses Machine theory -- Congresses
ISBN	9781119008224 1119008220 9781119008200 1119008204 9781119008217 1119008212
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Cover page; Half-Title page; Title page; Copyright page; Contents; Foreword; Introduction; I.1. What this book is or is not about; I.2. A few words about what you will find; I.3. How to read this book; I.4. Acknowledgments; 1: Words and Sequences from Scratch; 1.1. Mathematical background and notation; 1.1.1. About asymptotics; 1.1.2. Algebraic number theory; 1.2. Structures, words and languages; 1.2.1. Distance and topology; 1.2.2. Formal series; 1.2.3. Language, factor and frequency; 1.2.4. Period and factor complexity; 1.3. Examples of infinite words; 1.3.1. About cellular automata 1.3.2. Links with symbolic dynamical systems1.3.3. Shift and orbit closure; 1.3.4. First encounter with β-expansions; 1.3.5. Continued fractions; 1.3.6. Direct product, block coding and exercises; 1.4. Bibliographic notes and comments; 2: Morphic Words; 2.1. Formal definitions; 2.2. Parikh vectors and matrices associated with a morphism; 2.2.1. The matrix associated with a morphism; 2.2.2. The tribonacci word; 2.3. Constant-length morphisms; 2.3.1. Closure properties; 2.3.2. Kernel of a sequence; 2.3.3. Connections with cellular automata; 2.4. Primitive morphisms; 2.4.1. Asymptotic behavior 2.4.2. Frequencies and occurrences of factors2.5. Arbitrary morphisms; 2.5.1. Irreducible matrices; 2.5.2. Cyclic structure of irreducible matrices; 2.5.3. Proof of theorem 2.35; 2.6. Factor complexity and Sturmian words; 2.7. Exercises; 2.8. Bibliographic notes and comments; 3: More Material on Infinite Words; 3.1. Getting rid of erasing morphisms; 3.2. Recurrence; 3.3. More examples of infinite words; 3.4. Factor Graphs and special factors; 3.4.1. de Bruijn graphs; 3.4.2. Rauzy graphs; 3.5. From the Thue-Morse word to pattern avoidance; 3.6. Other combinatorial complexity measures 3.6.1. Abelian complexity3.6.2. k-Abelian complexity; 3.6.3. k-Binomial complexity; 3.6.4. Arithmetical complexity; 3.6.5. Pattern complexity; 3.7. Bibliographic notes and comments; Bibliography; Index; Volume 2 - Contents; Volume 2 - Index
Record Nr.	UNINA-9910811182403321

Autore	Rigo Michel
Pubbl/distr/stampa	London, England ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Descrizione fisica	1 online resource (274 p.)
Disciplina	001.642
Collana	Networks and Telecommunications Series
Soggetto topico	Computer programming Formal languages Machine theory
ISBN	1-119-04286-0 1-119-04285-2 1-119-04295-X
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Cover page; Half-Title page; Title page; Copyright page; Contents; Foreword; Introduction; I.1. What this book is or is not about; I.2. A few words about what you will find; I.3. How to read this book; I.4. Acknowledgments; 1: Crash Course on Regular Languages; 1.1. Automata and regular languages; 1.2. Adjacency matrix; 1.3. Multidimensional alphabet; 1.4. Two pumping lemmas; 1.5. The minimal automaton; 1.6. Some operations preserving regularity; 1.7. Links with automatic sequences and recognizable sets; 1.8. Polynomial regular languages; 1.8.1. Tiered words 1.8.2. Characterization of regular languages of polynomial growth 1.8.3. Growing letters in morphic words; 1.9. Bibliographic notes and comments; 2: A Range of Numeration Systems; 2.1. Substitutive systems; 2.2. Abstract numeration systems; 2.2.1. Generalization of Cobham's theorem on automatic sequences; 2.2.2. Some properties of abstract numeration systems; 2.3. Positional numeration systems; 2.4. Pisot numeration systems; 2.5. Back to β-expansions; 2.5.1. Representation of real numbers; 2.5.2. Link between representations of integers and real numbers 2.5.3. Ito-Sadahiro negative base systems 2.6. Miscellaneous systems; 2.7. Bibliographical notes and comments; 3: Logical Framework and Decidability Issues; 3.1. A glimpse at mathematical logic; 3.1.1. Syntax; 3.1.2. Semantics; 3.2. Decision problems and decidability; 3.3. Quantifier elimination in Presburger arithmetic; 3.3.1. Equivalent structures; 3.3.2. Presburger's theorem and quantifier elimination; 3.3.3. Some consequences of Presburger's theorem; 3.4. Büchi's theorem; 3.4.1. Definable sets; 3.4.2. A constructive proof of Büchi's theorem; 3.4.3. Extension to Pisot numeration systems 3.5. Some applications 3.5.1. Properties about automatic sequences; 3.5.2. Overlap-freeness; 3.5.3. Abelian unbordered factors; 3.5.4. Periodicity; 3.5.5. Factors; 3.5.6. Applications to Pisot numeration systems; 3.6. Bibliographic notes and comments; 4: List of Sequences; Bibliography; Index; Volume 1 - Contents; Volume 1 - Index
Record Nr.	UNINA-9910132160303321

Autore	Rigo Michel
Pubbl/distr/stampa	London, England ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014
Descrizione fisica	1 online resource (274 p.)
Disciplina	001.642
Collana	Networks and Telecommunications Series
Soggetto topico	Computer programming Formal languages Machine theory
ISBN	1-119-04286-0 1-119-04285-2 1-119-04295-X
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Nota di contenuto	Cover page; Half-Title page; Title page; Copyright page; Contents; Foreword; Introduction; I.1. What this book is or is not about; I.2. A few words about what you will find; I.3. How to read this book; I.4. Acknowledgments; 1: Crash Course on Regular Languages; 1.1. Automata and regular languages; 1.2. Adjacency matrix; 1.3. Multidimensional alphabet; 1.4. Two pumping lemmas; 1.5. The minimal automaton; 1.6. Some operations preserving regularity; 1.7. Links with automatic sequences and recognizable sets; 1.8. Polynomial regular languages; 1.8.1. Tiered words 1.8.2. Characterization of regular languages of polynomial growth 1.8.3. Growing letters in morphic words; 1.9. Bibliographic notes and comments; 2: A Range of Numeration Systems; 2.1. Substitutive systems; 2.2. Abstract numeration systems; 2.2.1. Generalization of Cobham's theorem on automatic sequences; 2.2.2. Some properties of abstract numeration systems; 2.3. Positional numeration systems; 2.4. Pisot numeration systems; 2.5. Back to β-expansions; 2.5.1. Representation of real numbers; 2.5.2. Link between representations of integers and real numbers 2.5.3. Ito-Sadahiro negative base systems 2.6. Miscellaneous systems; 2.7. Bibliographical notes and comments; 3: Logical Framework and Decidability Issues; 3.1. A glimpse at mathematical logic; 3.1.1. Syntax; 3.1.2. Semantics; 3.2. Decision problems and decidability; 3.3. Quantifier elimination in Presburger arithmetic; 3.3.1. Equivalent structures; 3.3.2. Presburger's theorem and quantifier elimination; 3.3.3. Some consequences of Presburger's theorem; 3.4. Büchi's theorem; 3.4.1. Definable sets; 3.4.2. A constructive proof of Büchi's theorem; 3.4.3. Extension to Pisot numeration systems 3.5. Some applications 3.5.1. Properties about automatic sequences; 3.5.2. Overlap-freeness; 3.5.3. Abelian unbordered factors; 3.5.4. Periodicity; 3.5.5. Factors; 3.5.6. Applications to Pisot numeration systems; 3.6. Bibliographic notes and comments; 4: List of Sequences; Bibliography; Index; Volume 1 - Contents; Volume 1 - Index
Record Nr.	UNINA-9910824922703321