Computation and Automata

by Arto Salomaa

Overview

This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.

Product Details

ISBN-13:	9780521302456
Publisher:	Cambridge University Press
Publication date:	05/23/1985
Series:	Encyclopedia of Mathematics and its Applications , #25
Pages:	300
Product dimensions:	6.38(w) x 9.21(h) x 0.87(d)

Table of Contents

Editor's statement; Foreword G. Rozenberg; Acknowledgements; 1. Introduction: models of computation; 2. Rudiments of language theory; 3. Restricted automata; 4. Turing machines and recursive functions; 5. Famous decision problems; 6. Computational complexity; 7. Cryptography; 8. Trends in automata and language theory; Historical and bibliographical remarks