## A Half-century of Automata Theory: Celebration and InspirationThis 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 beginning of the new millennium. Contents: Hazard Algebras (Extended Abstract) (J Brzozowski & Z esik); Undecidability and Incompleteness Results in Automata Theory (J Hartmanis); Automata Theory: Its Past and Future (J Hopcroft); Forty Years of Formal Power Series in Automata Theory (W Kuich); Playing Infinite Games in Finite Time (R McNaughton); Gene Assembly in Ciliates: Computing by Folding and Recombination (G Rozenberg); Compositions over a Finite Domain: From Completeness to Synchronizable Automata (A Salomaa). Readership: Computer scientists, mathematicians, theoretical biologists, and educated laymen." |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Undecidability and Incompleteness Results in Automata Theory | 21 |

Its Past and Future | 37 |

Playing Infinite Games in Finite Time | 73 |

Computing by Folding | 93 |

From Completeness | 131 |

### Other editions - View all

A Half-century of Automata Theory: Celebration and Inspiration Arto Salomaa,Derick Wood,Sheng Yu Limited preview - 2001 |

A Half-Century of Automata Theory: Celebration and Inspiration A Salomaa,D Wood,S Yu Limited preview - 2001 |

### Common terms and phrases

Algebra Ck algebraic system Algorithm applicable Arto Salomaa assembly in ciliates automata theory binary bipartite Black Boolean ciliates circuit complete composition sequence consider context-free grammar context-free languages Corollary defined definition denoted depth deterministic dlad DNA computing dynamic hazard example Figure finite automata formal languages formal power series gate gene assembly given GPRS grammar G Hartmanis Hopcroft Ilfc incompleteness results infinite game integer Kuich L(Gi language theory LAR strategy mathematical MDS structure MDSs memoryless game micronuclear gene molecular operations monoid node node(t notation nucleotide output paper permset play players pointer reduction principal cone problem proof in F pts(p pushdown automaton realistic MDS descriptor recursively reduction rule Rozenberg Salomaa score(a score(a,t Section semiring signed graph signed overlap graph SPRS stranded DNA molecule subset substring successful reduction ternary simulation Theorem theoretical computer science transient Turing machines unary functions undecidability University variables winner word