Formal languages, automata and numeration systems 2 / / Michel Rigo

• Autore: Rigo Michel
• Pubblicazione: London, England ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014; ©2014
• Descrizione fisica: 1 online resource (274 p.)
• Disciplina: 001.642
• Soggetto topico: Computer programming; Formal languages; Machine theory
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• 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. Büchi's theorem; 3.4.1. Definable sets; 3.4.2. A constructive proof of Bü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
• Sommario/riassunto: The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi) or between combinatorics on words and number theory has paved the way to recent dramatic developments, for example, the transcendence results for the real numbers having a "simple" binary expansion, by B. Adamczewski and Y. Bugeaud. This book is at the heart of this interplay through a unified exposition. Objects are considered with a perspective that comes both from
• Titolo autorizzato: Formal languages, automata and numeration systems 2
• ISBN: 1-119-04286-0; 1-119-04285-2; 1-119-04295-X
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910824922703321
• Lo trovi qui: Univ. Federico II
• Serie: Networks and telecommunications series.