LEADER 04601nam 2200685 450 001 9910824922703321 005 20200520144314.0 010 $a1-119-04286-0 010 $a1-119-04285-2 010 $a1-119-04295-X 035 $a(CKB)3710000000239199 035 $a(EBL)1784151 035 $a(SSID)ssj0001376223 035 $a(PQKBManifestationID)11773082 035 $a(PQKBTitleCode)TC0001376223 035 $a(PQKBWorkID)11360191 035 $a(PQKB)10733910 035 $a(MiAaPQ)EBC1784151 035 $a(Au-PeEL)EBL1784151 035 $a(CaPaEBR)ebr10930299 035 $a(CaONFJC)MIL646261 035 $a(OCoLC)898157454 035 $a(PPN)191455660 035 $a(EXLCZ)993710000000239199 100 $a20140926h20142014 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt 182 $cc 183 $acr 200 10$aFormal languages, automata and numeration systems 2 /$fMichel Rigo 210 1$aLondon, England ;$aHoboken, New Jersey :$cISTE :$cWiley,$d2014. 210 4$dİ2014 215 $a1 online resource (274 p.) 225 1 $aNetworks and Telecommunications Series 300 $aDescription based upon print version of record. 311 $a1-322-15006-0 311 $a1-84821-788-9 320 $aIncludes bibliographical references and index. 327 $aCover 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 327 $a1.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 327 $a2.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 327 $a3.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 330 $aThe 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. Bu?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 410 0$aNetworks and telecommunications series. 606 $aComputer programming 606 $aFormal languages 606 $aMachine theory 615 0$aComputer programming. 615 0$aFormal languages. 615 0$aMachine theory. 676 $a001.642 700 $aRigo$b Michel$0888777 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910824922703321 996 $aFormal languages, automata and numeration systems 2$93951843 997 $aUNINA