Modern applications of automata theory / editors, Deepak D'Souza, Priti Shankar.

Format:

Book

Contributor:

D'Souza, Deepak.

Shankar, P. (Priti)

Series:

IISc research monograph series ; v. 2.

IISc research monographs series ; 2

Language:

English

Subjects (All):

Machine theory.

Computational complexity.

Physical Description:

1 online resource (673 p.)

Place of Publication:

Singapore : World Scientific, c2012.

Language Note:

English

Summary:

Automata theory has come into prominence in recent years with a plethora of applications in fields ranging from verification to XML processing and file compression. In fact, the 2007 Turing Award was awarded to Clarke, Emerson and Sifakis for their pioneering work on model-checking techniques. To the best of our knowledge, there is no single book that covers the vast range of applications of automata theory targeted at a mature student audience. This book is intended to fill that gap and can be used as an intermediate-level textbook. It begins with a detailed treatment of foundational material

Contents:

Preface; Foreword; Contents; Part I: Basic Chapters; 1. An Introduction to Finite Automata and their Connection to Logic Howard Straubing and Pascal Weil; 1.1. Introduction; 1.1.1. Motivation; 1.1.2. Plan of the chapter; 1.1.3. Notation; 1.1.4. Historical note and references; 1.2. Automata and rational expressions; 1.2.1. Operations on languages; 1.2.2. Automata; 1.2.2.1. The language accepted by an automaton; 1.2.2.2. Complete automata; 1.2.2.3. Trim automata; 1.2.2.4. Epsilon-automata; 1.2.3. Deterministic automata; 1.3. Logic: Buchi's sequential calculus; 1.3.1. First-order formulas

1.3.1.1. Syntax1.3.1.2. Interpretation of formulas; 1.3.2. Monadic second-order formulas; 1.4. The Kleene-Buchi theorem; 1.4.1. From automata to monadic second-order formulas; 1.4.2. From formulas to extended rational expressions; 1.4.2.1. The auxiliary alphabets Bp,q; 1.4.2.2. The language associated with a formula; 1.4.2.3. The MSO(<)-definable languages are extended rational; 1.4.3. From extended rational expressions to automata; 1.4.4. From automata to rational expressions; 1.4.5. Closure properties; 1.5. Pumping lemmas; 1.6. Minimal automaton and syntactic monoid

1.6.1. Myhill-Nerode equivalence and the minimal automaton1.6.2. Uniqueness and minimality of Amin(L); 1.6.3. An algorithm for computing the minimal automaton; 1.6.4. The transition monoid of an automaton; 1.6.5. The syntactic monoid; 1.7. First-order definable languages; References; 2. Finite-State Automata on Infinite Inputs Madhavan Mukund; Introduction; Notation; 2.1. Buchi automata; 2.1.1. Characterizing Buchi-recognizable languages; 2.1.2. Constructions on Buchi automata; 2.2. The logic of sequences; 2.3. Stronger acceptance conditions; 2.4. Determinizing Buchi automata; 2.5. Discussion

AcknowledgmentsReferences; 3. Basics on Tree Automata Christof Loding; 3.1. Introduction; 3.2. Trees; 3.2.1. Ranked trees; 3.2.2. Hedges and unranked trees; 3.3. Ranked Tree Automata; 3.3.1. Determinization and closure properties; 3.3.2. Decision problems and algorithms; 3.3.3. Congruences and minimization; 3.3.4. Logic; 3.4. Hedge automata; 3.4.1. Relation to ranked tree automata; 3.4.2. Grammar based formalisms; 3.5. Tree-walking automata; 3.5.1. Streams; 3.6. Conclusion; Acknowledgements; References; 4. An Introduction to Timed Automata Paritosh K. Pandya and P. Vijay Suman

4.1. Introduction4.2. Timed Automata; 4.2.1. Semantics; 4.2.2. Closure Properties; 4.2.2.1. Union and Intersection; 4.2.2.2. Complementation; 4.3. Language Emptiness and Location Reachability; 4.3.1. Region Equivalence; 4.3.2. Region Automaton; 4.3.3. Complexity; 4.4. Universality and Language Inclusion; 4.5. Deterministic Timed Automata (DTA); 4.5.1. Closure Properties, Decision Problems and Expressiveness; 4.5.2. Determinizability; 4.5.3. Event-Recording Automata (ERA); 4.5.3.1. Determinization of ERA; 4.5.3.2. ERA and DTA; 4.6. Clock Reduction; 4.7. Integer Timed Automata and Digitization

4.7.1. Integer Timed Automata

Notes:

Description based upon print version of record.

Includes bibliographical references and index.

ISBN:

9786613906014

9781283593564

1283593564

9789814271059

9814271055

OCLC:

819613075