Automata, Computability and Complexity
Pearson (Verlag)
978-0-13-228806-4 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
The core material includes discussions of finite state machines, Markov models, hidden Markov models (HMMs), regular expressions, context-free grammars, pushdown automata, Chomsky and Greibach normal forms, context-free parsing, pumping theorems for regular and context-free languages, closure theorems and decision procedures for regular and context-free languages, Turing machines, nondeterminism, decidability and undecidability, the Church-Turing thesis, reduction proofs, Post Correspondence problem, tiling problems, the undecidability of first-order logic, asymptotic dominance, time and space complexity, the Cook-Levin theorem, NP-completeness, Savitch's Theorem, time and space hierarchy theorems, randomized algorithms and heuristic search. Throughout the discussion of these topics there are pointers into the application chapters. So, for example, the chapter that describes reduction proofs of undecidability has a link to the security chapter, which shows a reduction proof of the undecidability of the safety of a simple protection framework.
Elaine Rich received her Ph.D. in Computer Science from Carnegie-Mellon in 1979. Her thesis, Building and Exploiting User Models, laid the groundwork for the next twenty years of work on personalizing information systems to meet the needs of individual users. Over twenty years later, she still gets requests for her thesis and the papers based on it. Dr. Rich joined the UT CS faculty in 1979. She continued her work in the area of human/machine interfaces, with a focus on the use of knowledge-based systems. She was PI on an NSF grant, "Individual Models in Computer Systems", $56,000, NSF, 1980, which supported that work. She was also co-PI on two other grants while at UT: "An Experimental Computing Facility to Support the Design and Analysis of Reliable, High Performance Computing Systems", with J. C. Browne, A. G. Dale, D. I. Good, and A. Silberschatz, $3,700,000, NSF, 1982 and "Support for an AI Laboratory", with G. Novak, R. Simmons, and V. Kumar, $1,300,000, Army Research Office, 1984. The $3.7M NSF grant is particularly significant. It supported, for the first time in our department's history, a significant investment in the computing and networking infrastructure required to enable research groups to cooperate in work that required building large software systems. In 1985, Dr. Rich left UT for the Microelectronic and Computing Technology Corporation (MCC). She served first as a Member of the Technical Staff, then Associate Director of the Human Interface Lab, then Director of the Artificial Intelligence Lab. At MCC, she was responsible for attracting and maintaining support, from MCC's corporate shareholders, for the research projects in her lab. Dr. Rich was responsible for setting research agendas, for enabling technology transfer from MCC to the shareholder companies, and for managing the lab's annual budgets (between $1M and $3M per year). In 1998, Dr. Rich returned to the CS department at UT Austin as a Senior Lecturer. She has taught Automata Theory, Artificial Intelligence, and Natural Language Processing. She served for two years as Associate Chair for Academic Affairs in the department. During that time, she oversaw a major redesign of the undergraduate curriculum, as well as the launch of several new programs including Turing Scholars, an undergraduate honors program and First Bytes, a summer camp for high school girls to encourage their interest in computer science. In 1983, Dr. Rich published her textbook, Artificial Intelligence, from which at least a decade of the world's computer scientists learned AI. The book was translated into Japanese, French, Spanish, German, Italian and Portugese. In 1991, with Kevin Knight, she published a second edition. The two editions have sold over 250,000 copies. Dr. Rich has published nine book chapters and 24 refereed papers. She has served as Editor of AI Magazine and on the editorial boards of Artificial Intelligence Review, The Knowledge Engineering Review, User Modeling and User-Adapted Interaction, and Applied Intelligence. She has served on numerous review panels for NSF and on the Discipline Advisory Committee of the Council of International Exchange of Scholars. In 1991, she was elected a Fellow of the American Association for Artificial Intelligence.
PART I: INTRODUCTION
1 Why Study Automata Theory?
2 Review of Mathematical Concepts
2.1 Logic
2.2 Sets
2.3 Relations
2.4 Functions
2.5 Closures
2.6 Proof Techniques
2.7 Reasoning about Programs
2.8 References
3 Languages and Strings
3.1 Strings
3.2 Languages
4 The Big Picture: A Language Hierarchy
4.1 Defining the Task: Language Recognition
4.2 The Power of Encoding
4.3 A Hierarchy of Language Classes
5 Computation
5.1 Decision Procedures
5.2 Determinism and Nondeterminism
5.3 Functions on Languages and Programs
PART II: FINITE STATE MACHINES AND REGULAR LANGUAGES
6 Finite State Machines
6.2 Deterministic Finite State Machines
6.3 The Regular Languages
6.4 Programming Deterministic Finite State Machines
6.5 Nondeterministic FSMs
6.6 Interpreters for FSMs
6.7 Minimizing FSMs
6.8 Finite State Transducers
6.9 Bidirectional Transducers
6.10 Stochastic Finite Automata
6.11 Finite Automata, Infinite Strings: Büchi Automata
6.12 Exercises
7 Regular Expressions
7.1 What is a Regular Expression?
7.2 Kleene’s Theorem
7.3 Applications of Regular Expressions
7.4 Manipulating and Simplifying Regular Expressions
8 Regular Grammars
8.1 Definition of a Regular Grammar
8.2 Regular Grammars and Regular Languages
8.3 Exercises
9 Regular and Nonregular Languages
9.1 How Many Regular Languages Are There?
9.2 Showing That a Language Is Regular.124
9.3 Some Important Closure Properties of Regular Languages
9.4 Showing That a Language is Not Regular
9.5 Exploiting Problem-Specific Knowledge
9.6 Functions on Regular Languages
9.7 Exercises
10 Algorithms and Decision Procedures for Regular Languages
10.1 Fundamental Decision Procedures
10.2 Summary of Algorithms and Decision Procedures for Regular Languages
10.3 Exercises
11 Summary and References
PART III: CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA 144
12 Context-Free Grammars
12.1 Introduction to Grammars
12.2 Context-Free Grammars and Languages
12.3 Designing Context-Free Grammars
12.4 Simplifying Context-Free Grammars
12.5 Proving That a Grammar is Correct
12.6 Derivations and Parse Trees
12.7 Ambiguity
12.8 Normal Forms
12.9 Stochastic Context-Free Grammars
12.10 Exercises
13 Pushdown Automata
13.1 Definition of a (Nondeterministic) PDA
13.2 Deterministic and Nondeterministic PDAs
13.3 Equivalence of Context-Free Grammars and PDAs
13.4 Nondeterminism and Halting
13.5 Alternative Definitions of a PDA
13.6 Exercises
14 Context-Free and Noncontext-Free Languages
14.1 Where Do the Context-Free Languages Fit in the Big Picture?
14.2 Showing That a Language is Context-Free
14.3 The Pumping Theorem for Context-Free Languages
14.4 Some Important Closure Properties of Context-Free Languages
14.5 Deterministic Context-Free Languages
14.6 Other Techniques for Proving That a Language is Not Context-Free
14.7 Exercises
15 Algorithms and Decision Procedures for Context-Free Languages
15.1 Fundamental Decision Procedures
15.2 Summary of Algorithms and Decision Procedures for Context-Free Languages
16 Context-Free Parsing
16.1 Lexical Analysis
16.2 Top-Down Parsing
16.3 Bottom-Up Parsing
16.4 Parsing Natural Languages
16.5 Stochastic Parsing
16.6 Exercises
17 Summary and References
PART IV: TURING MACHINES AND UNDECIDABILITY
18 Turing Machines
18.1 Definition, Notation and Examples
18.2 Computing With Turing Machines
18.3 Turing Machines: Extensions and Alternative Definitions
18.4 Encoding Turing Machines as Strings
18.5 The Universal Turing Machine
18.6 Exercises
19 The Church-Turing
19.1 The Thesis
19.2 Examples of Equivalent Formalisms
20 The Unsolvability of the Halting Problem
20.1 The Language H is Semidecidable but Not Decidable
20.2 Some Implications of the Undecidability of H
20.3 Back to Turing, Church, and the Entscheidungsproblem
21 Decidable and Semidecidable Languages
21.2 Subset Relationships between D and SD
21.3 The Classes D and SD Under Complement
21.4 Enumerating a Language
21.5 Summary
21.6 Exercises
22 Decidability and Undecidability Proofs
22.1 Reduction
22.2 Using Reduction to Show that a Language is Not Decidable
22.3 Rice’s Theorem
22.4 Undecidable Questions About Real Programs
22.5 Showing That a Language is Not Semidecidable
22.6 Summary of D, SD/D and ®SD Languages that Include Turing Machine Descriptions
22.7 Exercises
23 Undecidable Languages That Do Not Ask Questions about Turing Machines
23.1 Hilbert’s 10th Problem
23.2 Post Correspondence Problem
23.3 Tiling Problems
23.4 Logical Theories
23.5 Undecidable Problems about Context-Free Languages
APPENDIX C: HISTORY, PUZZLES, AND POEMS
43 Part I: Introduction
43.1 The 15-Puzzle
Part II: Finite State Machines and Regular Languages
44.1 Finite State Machines Predate Computers
44.2 The Pumping Theorem Inspires Poets
REFERENCES
INDEX
Appendices for Automata, Computability and Complexity: Theory and Applications:
Math Background
Working with Logical Formulas
Finite State Machines and Regular Languages
Context-Free Languages and PDAs
Turing Machines and Undecidability
Complexity
Programming Languages and Compilers
Tools for Programming, Databases and Software Engineering
Networks
Security
Computational Biology
Natural Language Processing
Artificial Intelligence and Computational Reasoning
Art & Entertainment: Music & Games
Using Regular Expressions
Using Finite State Machines and Transducers
Using Grammars
| Erscheint lt. Verlag | 12.10.2007 |
|---|---|
| Sprache | englisch |
| Maße | 190 x 242 mm |
| Gewicht | 1530 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Theorie / Studium |
| Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre | |
| ISBN-10 | 0-13-228806-0 / 0132288060 |
| ISBN-13 | 978-0-13-228806-4 / 9780132288064 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
