A half-century of automata theory [[electronic resource] ] : celebration and inspiration / / editors, A. Salomaa, D. Wood, S. Yu

• Pubblicazione: River Edge, N.J., : World Scientific, c2001
• Descrizione fisica: 1 online resource (164 p.)
• Disciplina: 511.3
• Soggetto topico: Machine theory; Algebra
• Soggetto genere / forma: Electronic books.
• Altri autori: SalomaaArto WoodDerick <1940-> YuSheng
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references.
• Nota di contenuto: CONTENTS ; Preface ; Hazard Algebras (Extended Abstract) ; 1 Introduction ; 2 Transients ; 3 Change-Counting Algebra ; 4 Counting Changes to a Threshold ; 5 Circuit Simulations ; 6 Extensions of Boolean Functions ; 7 Complexity Issues ; 8 Conclusions ; References ; Undecidability and Incompleteness Results in Automata Theory 1 Introduction ; 2 Basic Concepts and II2-Completeness; 3 Undecidability and Incompleteness Results ; 4 Representation Independent Incompleteness Results ; 5 Incomplete Languages ; 6 Minimal Automata and Incompleteness ; 7 Succinctness Results ; 8 Conclusion References ; Automata Theory: Its Past and Future ; 1 Introduction ; 2 Beginnings of Automata Theory ; 3 External Changes Impacting Future Directions ; 4 Conclusions ; References ; Forty Years of Formal Power Series in Automata Theory ; 1 Introduction ; 2 Continuous monoids and semirings 3 Automata and the Theorem of Kleene ; 4 Algebraic systems and pushdown automata ; 5 Principal cones of algebraic power series ; 6 Decidability questions ; References ; Playing Infinite Games in Finite Time ; 1 Infinite games ; 2 The score function ; 3 Theoretical results about scoring 4 When to end the play ; 5 Finding playable games ; 6 A specific suggestion ; References ; Gene Assembly in Ciliates: Computing by Folding and Recombination ; Introduction. ; 1 Preliminaries. ; 2 DNA molecules: structure and notation. ; 3 Gene assembly in ciliates.
• Sommario/riassunto: This volume gathers lectures by 8 distinguished pioneers of automata theory, including two Turing Award winners. In each contribution, the early developments of automata theory are reminisced about and future directions are suggested. Although some of the contributions go into rather intriguing technical details, most of the book is accessible to a wide audience interested in the progress of the age of computers. The book is a must for professionals in theoretical computer science and related areas of mathematics. For students in these areas it provides an exceptionally deep view at the begi
• Titolo autorizzato: A half-century of automata theory
• ISBN: 1-281-95168-4; 9786611951689; 981-281-016-1
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910450501403321
• Lo trovi qui: Univ. Federico II