Description
Chapters
Description
The first chapter covers some topics from the Chomsky hierarchy: the Myhill-Nerode theorem (how to construct a minimal finite automaton), deterministic PDAs, type 1 languages, normalform for type 0 and type 1 languages, Ehrenfeuchts theorem and Lindenmayer systems, a class of grammars that is orthogonal to parts of the Chomsky hierarchy.
4.2011
Lecture recordings 04.Apr.2011 01:20:22 1.068 The Chomsky Hierarchy 1. The Chomsky Hierarchy: Definition 1.1 (Homomorphism), Definition 1.2 (Isomorphism), Lemma 1.3 (Unique Extension), Definition 1.4 ((Ext.) Regular Expressions Reg), Definition 1.5 (Semantics of Reg), Definition 1.6 (Deterministic Finite Automaton (dfa)). 1.1 Minimal DFA: Definition 1.7 (L), Definition 1.8 (RA), Lemma 1.9, Theorem 1.13 (Myhill-Nerode), Definition 1.14 (ML), Definition 1.15 (Morphisms between dfas), Theroem 1.16 (Minimality of ML), Definition 1.17 (Equivalence of states), Lemma 1.18 (Finite test set), Lemma 1.19. 1.2 cf = hom(Dyck reg): Definition 1.20 (Dycklanguage Dk), Theorem 1.21 (Closed under hom), Theorem 1.22 (CFL=h(Dyck reg)). 06.Apr.2011 01:35:17 249 The Chomsky Hierarchy 1. The Chomsky Hierarchy: 1.2 cf = hom(Dyck reg): Definition 1.23 (Push-Down-Automaton (PDA)), Definition 1.24 (Accepted language of a PDA), Definition 1.25 (Configuration of a PDA), Definition 1.26 (Arbitrary computations Comp(M)), Theroem 1.27 (Comphalt(M)), Theroem 1.28 (Invalid TM computations as a CFL), Theorem 1.29 (Undecidability for CFL Problems), Theorem 1.30 (Valid Computations of a TM), Theorem 1.31 (Ogdens Lemma), Theorem 1.32 (Undecidability for CFL Problems), Lemma 1.33 (Decidable cf problems). 1.3 DPDA/DCFL: Definition 1.34 (DPDA), Theorem 1.35 (DCFL), Lemma 1.36 (DPDA without moves), Theorem 1.37 (DPDA do not hang), Lemma 1.39 (DCFL Regular = DCFL), Theorem 1.41 (Decidability of some DCFL problems), Theorem 1.42 (Undecidability of some DCFL problems), Theorem 1.43 (Senizergues, 1997) 11.Apr.2011 01:30:24 212 The Chomsky Hierarchy 1. The Chomsky Hierarchy: Lemma 1.18 (Finite test set). 1.6 Ehrenfeucht: Definition 1.62, Example 1.63, Lemma 1.64 and 1.65, Lemma 1.66, Definition 1.67 (Test-Set), Lemma 1.68 (Test set for regular languages), Corollary 1.69 (Test set for regular languages), Theorem 1.70 (Test set for contextfree languages), Theorem 1.71 and Corollary 1.72, Theorem 1.73 (Test sets can not be computed), Definition 1.74, Definition 1.75 (Ehrenfeucht for word equations), Lemma 1.76 and 1.77 18.Apr.2011 34:37 152 (Un-) Decidability 2. (Un-) Decidability: 2.2 PCP: Definition 2.5 (Correspondence system, PCP), Definition 2.6 (Variants of PCP), Beispiel 2.8, Lemma 2.9 (PCP over one alphabet), Theorem 2.10 (Undecidability of PCP) 18.Apr.2011 28:45 111 (Un-) Decidability 2. (Un-) Decidability: 2.2 PCP: Theorem 2.10 (Undecidability of PCP), Lemma 2.11, 2.12, 2.13 18.Apr.2011 26:49 95 The Chomsky Hierarchy and (Un-) Decidability 1. The Chomsky Hierarchy: 1.6 Ehrenfeucht: Lemma 1.64 and 1.65, Lemma 1.66 (Undecidability of f=L g). 2. (Un-) Decidability: 2.2 PCP: Theorem 2.10 (Undecidability of PCP), Lemma 2.11, 2.12, 2.13, Theorem 2.14 (Undecidability of various problems) 02.May.2011 01:39:42 118 (Un-) Decidability 2. (Un-) Decidability: 2.2 PCP: Theorem 2.14 (Undecidability of various problems), Corollary 2.15 (Undecidability of various problems), The Domino-Problem, Theorem 2.16 ((Un-)Decidability of Plane Tiling), Domino-Problem for finite areas of the plane. 2.3 Makanins Algorithm: Example 2.17, Definition 2.18 (Word equations, solution), Theorem 2.19 (Makanin (1977)), Lemma 2.20 (Quadratic Equations), Example 2.21 (Illustration of Lemma 2.20) 09.May.2011 01:38:17 102 (Un-) Decidability 2. (Un-) Decidability: 2.3 Makanins Algorithm: Lemma 2.20 (Quadratic Equations), Example 2.21 (Illustration of Lemma 2.20). 2.4 Recursive Functions: Definition 2.22 (Primitive recursive functions PR), Lemma 2.23 (More base functions), Lemma 2.24 (Modifying variables), Definition 2.25 and Lemma 2.26, Definition 2.27 and Lemma 2.28, Definition 2.29 (Simultaneous recursion), Definition 2.30 and Lemma 2.31, Lemma 2.32 (Coding Functions), Definition 2.33 (Ackermann and its Branches), Lemma 2.34 (Monotonicity of Ackermann), Definition 2.35 (Bounded operations), Definition 2.36 (Grzegorczyk Hierarchy), Theorem 2.37 (Growth), Corollary 2.38 (Grzegorczyk Hierarchy is strict), Example 2.39 (Fibonacci), Lemma 2.40, Theorem 2.41 (Grzegorczyk and primitive recursion), Definition 2.42 (Ackermann-Peter function), Lemma 2.43 (Minimal set of initial functions for PR) 16.May.2011 01:31:27 90 (Un-) Decidability 2.4 Recursive Functions: Definition 2.42 (Ackermann-Peter function), Theorem 2.44 (PR = LOOP), Definition 2.45 (Operator), Definition 2.46 (recursive functions, R, Rpart), Theorem 2.47 (R = WHILE, Rpart = WHILEpart), Lemma 2.48 (Minimal set of initial functions for Rpart), Theorem 2.49 (Grzegorczyk and LOOP programs), Theorem 2.50 (R = TM, Rpart = TMpart). 2.5 Random Access Machines: Definition 2.51 (Random Access Machine), Definition 2.52 (LOOP construct), Definition 2.53 (Semantics of LOOP programs), Definition 2.54 (LOOP computable), Definition 2.55 (WHILE construct), Definition 2.56 (Semantics of the WHILE statement), Definition 2.57 (WHILE computable), Definition 2.58 (GOTO construct), Theorem 2.59 (LOOP vs WHILE programs), Theorem 2.60 (WHILE=GOTO), Corollary 2.61 (WHILEtotal=GOTOtotal), Definition 2.62 (WHILEif programs), Lemma 2.63 (WHILE=WHILEif), Theorem 2.64 (One WHILE loop suffices). 2.6 Hilberts 10. Problem: Definition 2.65 (Diophantine Equation), Definition 2.66 (Diophantine Set), Lemma 2.67 (Reduction), Lemma 2.68 (Reduction to diophantine eq. with exp), Theorem 2.69 (Matiyasevich (1970)) 23.May.2011 01:33:45 115 (Un-) Decidability 2. (Un-) Decidability: 2.6 Hilberts 10. Problem: Lemma 2.67 (Reduction), Lemma 2.68 (Reduction to diophantine eq. with exp), Theorem 2.69 (Matiyasevich (1970)), Corollary 2.70 (Hilberts 10th Problem is Undecidable). 2.7 Theorem of Rice: Definition 2.71 (Gödelization, Index), Theorem 2.72 (smn Theorem), Definition 2.73 (Index), Theorem 2.74 (Rice), Lemma 2.75, Theorem 2.78 (Recursion Theorem). 2.8 Oracle TMn: Definition 2.79 (Oracle TM MA), Definition 2.80 (Recursive, re in A), Definition 2.81 (Equivalence wrt. Turing Reducibility) and Definition 2.82 (Hierarchy), Theorem 2.83. 2.9 Reductions: Definition 2.84 (Reductions), Lemma 2.88, Definition 2.89. 30.May.2011 01:31:42 138 SPACE versus TIME 3. SPACE versus TIME: 3.1 Basics: Definition 3.1 (NTIME(T(n)), DTIME(T(n))), Definition 3.2 (NSPACE(S(n)), DSPACE(S(n))), Theorem 3.3 (Tapes, Alphabet, States), Theorem 3.4 (Tape Compression), Corollary 3.5 (Tape Compression), Theorem 3.6 (Time Speed Up), Corollary 3.7 (Time Speed Up), Theorem 3.8 (Tape Reduction for TIME), Theorem 3.9 (Tape Reduction for SPACE), Lemma 3.10 (NTIME vs. DTIME). 3.2 Some Hierarchies: Theorem 3.11 (DSPACE(f(n)) Rec), Definition 3.12/13 ((Fully) Space/Time Constructible), Lemma 3.14, Definition 3.15 (Well-behaved Functions) and Lemma 3.16, Theorem 3.17 (Time/Space Hierarchies), Theorem 3.18 (Nondeterministic Hierarchies), Theorem 3.19 (Deterministic Hierarchies). 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch)) 06.Jun.2011 52:10 67 SPACE versus TIME 3. SPACE versus TIME: 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch)), Theorem 3.22, Lemma 3.23, Theorem 3.24 (Linear det. - linear nondet.). 3.4 More Properties: Theorem 3.25 (Union Theorem for SPACE), Theorem 3.26 (Union Theorem for TIME), Theorem 3.27 (Borodins Gap Theorem), Corollary 3.28 (Unintuitive Consequences), Theorem 3.29 (Blums Speed-Up Theorem). 06.Jun.2011 42:06 65 SPACE versus TIME 3. SPACE versus TIME: 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch)), Theorem 3.22, Lemma 3.23, Theorem 3.24 (Linear det. - linear nondet.). 3.4 More Properties: Theorem 3.25 (Union Theorem for SPACE), Theorem 3.26 (Union Theorem for TIME), Theorem 3.27 (Borodins Gap Theorem), Corollary 3.28 (Unintuitive Consequences), Theorem 3.29 (Blums Speed-Up Theorem). 27.Jun.2011 01:34:42 70 EXPSPACE 4. EXPSPACE: Theorem 3.17 (Time/Space Hierarchies). 4.1 Complexity classes: Definition 4.1 (From L to NEXPSPACE), Definition 4.2 (co-C), Lemma 4.3 (NSPACE(n)=Type-1), Theorem 4.4 (Immermann/Szelepcsenyi), Corollary 4.5 (CSL is closed under complements), Corollary 4.6 (Tight Space Hierarchy for NSPACE(S(n))), Lemma 4.7 (Number of Reachable Nodes), Lemma 4.8 (Rejecting NTM). 4.2 Reductions: Definition 4.9 (P-Time-,log-Space Reducibility), Lemma 4.10 (P-Time-and log Space Reductions), Definition 4.11 (Complete, Hard). 4.3 Structure of NP: Definition 4.12 (Psearch, NPsearch), Theorem 4.13, Definition 4.14 (Reachability: STCON, USTCON), Theorem 4.15 (Completeness of STCON and USTCON), Definition 4.16 (Boolean Expressions) 04.Jul.2011 01:23:34 61 EXPSPACE 4. EXPSPACE: 4.3 Structure of NP: Definition 4.12 (Psearch, NPsearch), Theorem 4.13Definition 4.14 (Reachability: STCON, USTCON), Theorem 4.15 (Completeness of STCON and USTCON), Definition 4.16 (Boolean Expressions), Definition 4.17 (Satisfiability: SAT), Definition 4.18 (SAT, k-CNF, k-DNF), Definition 4.19 (Satisfiability: k-SAT), Lemma 4.20 (DNF and 2-SAT), Theorem 4.21 (Characterization of NP), Theorem 4.22 (SAT is NP-complete), Example 4.23 (More NP-Complete Problems), Lemma 4.24, Lemma 4.25, Lemma 4.26. 4.4 Oracles for P, NP: Definition 4.27 (PA, NPA) 11.Jul.2011 01:36:24 112 EXPSPACE 4.4 Oracles for P, NP: Definition 4.27 (PA, NPA), Theorem 4.28 (Baker/Gill/Solovay). 4.5 PH - Polynomial Hierarchy: Definition 4.29 (LQBF), Definition 4.30 (Satisfiability: TQBF), Theorem 4.31 (LTQBF is PSPACE-complete), Definition 4.32 (Satisfiability: QSAT), Definition 4.33 (Alternating Turing Machine (ATM)), Definition 4.34 (Polynomial Hierarchy, ATM version), Lemma 4.35 (Relation between NTMs and ATMs), Lemma 4.36 (Relation: APTIME(f(n)), DSPACE(f(n))), Corollary 4.37 (PSPACE = APTIME), Corollary 4.38 (Relation between ATMs and TQBF), Definition 4.39 (MinDNF), Lemma 4.40, Definition 4.41 (Polynomial Hierarchy, Oracle version), Theorem 4.42 (ATMs and oracle TMs correspond), Corollary 4.43, Lemma 4.44. 4.6 Structure of PSPACE: Definition 4.45 (LCSG), Lemma 4.46 (CSG PSPACE), Definition 4.47 (Generalized L Tic-Tac-Toe), Theorem 4.48 (PSPACE completeness), Lemma 4.49 (Quasi-fixed rectangle). 4.7 EXPTIME/EXPSPACE: Lemma 4.50 (DTM accepting in k steps LDTM accept), Lemma 4.51 (n x n Checkers), Definition 4.52 (Regular expressions Lregex), Lemma 4.53 (Square Domino), Definition 4.54 (First order logic LFO), Definition 4.55 (Presburger/Peano Arithmetic), Definition 4.56 (R with addition/multiplication), Definition 4.57 (Quantifier Elimination), Lemma 4.58 (Quantifier Elimination (QE)), Lemma 4.59 (Reals with addition), Corollary 4.60 (Q and R are indistinguishable in L), Corollary 4.61 (Axioms for R, Q in L), Lemma 4.62 (Reals with addition and multiplication), Corollary 4.63 (Axioms for R in L), Lemma 4.64 (Presburger arithmetic), Corollary 4.65 (Axioms for N in L), Theorem 4.66 (Complexity of Arithmetic and R)
