1.

Record Nr.

UNINA9910450501403321

Titolo

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

Pubbl/distr/stampa

River Edge, N.J., : World Scientific, c2001

ISBN

1-281-95168-4

9786611951689

981-281-016-1

Descrizione fisica

1 online resource (164 p.)

Altri autori (Persone)

SalomaaArto

WoodDerick <1940->

YuSheng

Disciplina

511.3

Soggetti

Machine theory

Algebra

Electronic books.

Lingua di pubblicazione

Inglese

Formato

Materiale a stampa

Livello bibliografico

Monografia

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