Computation and AutomataCambridge University Press, 23.05.1985 - 284 Seiten In this book, which was originally published in 1985, Arto Salomaa gives an introduction to certain mathematical topics central to theoretical computer science: computability and recursive functions, formal languages and automata, computational complexity and cryptography. |
Inhalt
Foreword by G Rozenberg | 5 |
3 | 74 |
Turing Machines and Recursive Functions | 76 |
Famous Decision Problems | 116 |
Computational Complexity | 139 |
Cryptography | 186 |
Trends in Automata and Language Theory | 231 |
Historical and Bibliographical Remarks | 266 |
| 279 | |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
a₁ arbitrary assume automata automaton axiom Church's thesis Clearly complexity computation Consequently Consider consists construct context-free grammar context-free languages cryptanalysis cryptography cryptotext decidable decryption defined definition denoted deterministic Diophantine discussed empty encryption key equals equation equivalent Example finite formal function g G₂ given grammar G graph guage Hence holds input instance integers intuitive knapsack problem Lemma letter Markov algorithm morphisms nodes nondeterministic nonnegative nonterminal notation notion NP-complete obtained output pair partial recursive function Petri net plaintext polynomial Post correspondence problem Post system productions proof protocol public key cryptosystems pushdown automaton pushdown tape reachability reader recursively enumerable set regular expression regular languages resp result rewriting system satisfying sequence solution specific subset subword systolic tree terminal alphabet Theorem theory tion transition trapdoor trellis Turing machine TM undecidable values variables vector w₁ wffpc word x₁ y₁
Beliebte Passagen
Seite 274 - MAURER, A. SALOMAA and D. WOOD. Context-free grammar forms with strict interpretations.