Under Construction.

Topic Comment PDF More
Primitive Recursive Functions Clones, closure, bounded search, coding, Ackermann function. pdf   6up  
LOOP Programs Comparison to prec functions, levels 0, 1, 2. pdf   6up  
Register Machines Universality and undecidability. pdf   6up  
Turing Machines Universality and undecidability. pdf   6up   pdf   pdf   
Decidability Decision algorithms, semidecidability. pdf   6up   pdf   
Fundamentals Stages, indices, recursion theorem. pdf   6up  
Reductions Turing, many-one, one-one reductions, degrees. pdf   6up  
Arithmetical Hierarchy Projections and complements, definability theory. pdf   6up   pdf   
Intermediate Sets Post's problem, intermediate re sets. pdf   6up   pdf   
Kolmogorov Complexity Program size complexity, incompressibility, Omega. pdf   6up  
Hypercomputation Generalized computability, Turing barrier. pdf   6up  
Deterministic Complexity Tractable problems, deterministic complexity classes. pdf   6up  
Space Complexity Polynomial space, logarithmic space. pdf   6up  
Cook-Levin Polynomial time reductions, NP-completeness. pdf   6up   pdf   
Randomness Block counting, von Mises, Per-Lof. pdf   6up  
Random Classes Schwartz-Zippel, Solovey-Strassen, RP, BPP. pdf   6up  
Rewrite Systems Rewrite systems, Thue systems, Post systems. pdf   6up  
Context-Free Grammars Formal grammars, Thue-systems, Church-Rosser, Post tag systems. pdf   6up  
Parsing Parsing context-free languages, CYK algorithm. pdf   6up  
Context-Sensitive Grammars Linear bounded automata, Immerman-Szelepsenyi pdf   6up  
Finite State Machines  
Deterministic Machines Transition systems, scan algorithms, state complexity. pdf   6up  
Nondeterministic Machines Rabin-Scott determinization, products, pebble arguments. pdf   6up   pdf   
State Complexity Transition monoids, blow-up, alternating automata. pdf   6up  
Minimization Quotients and covers, Moore's and Brzozowski's algorithms. pdf   6up  
More Minimization Partition refinement, Hopcroft's and Valmari-Lehtinen algorithm. pdf   6up   pdf   pdf   
Minimization and NFAs Paige-Tarjan, minimizing NFAs, hardness. pdf   6up  
Regular Expressions Kleene's theorem, Floyd-Warshall algorithm, Arden's lemma. pdf   6up  
String Matching KMP, Aho-Corasick, Baeza-Yates-Gonnet, Rabin-Karp. pdf   6up  
Monadic Second-Order Logic Buechi-Elgot theorem, Schuetzenberger's theorem. pdf   6up  
Omega Automata Buechi, Muller and Rabin automata, conversion algorithms. pdf   6up  
Omega Determinization McNaughton's theorem, Safra's algorithm. pdf   6up  
Automatic Sequences Prouhet-Thue-Morse word, decimations and kernels. pdf   6up  
Invertible Invertible Mealy machines, automata groups, orbit rationality. pdf   6up  
Elementary Cellular Automata Automtic structures, model checking ECA. pdf   6up  
Propositional Logic Boolean functions, propositional formulae, normal forms. pdf   6up  
Satisfiability DPLL, Resolution, Horn clauses. pdf   6up  
Boolean Algebra Duality, partial orders, Stone representation. pdf   6up  
Boolean Functions Clones, Post's theorem. pdf   6up  
Boolean Decision Diagrams Minimial automata, if-then-else normal form, ROBDDs. pdf   6up  
Equational Logic Equational reasoning, Birkhoff's theorem, Boolean algebras. pdf   6up  
First-Order Logic Signatures, first-order structures, Tarski truth, computable structures. pdf   6up  
FO Theories Elementary equivalence, Goedel completeness, Goedel incompleteness. pdf   6up  
Proof Theory Derivations, proofs, proof assistants, provers. pdf   6up  
Peano Arithmetic Axiomatizing arithmetic, induction, Tennenbaum's theorem. pdf   6up  
Model Checking Verification, Kripke structures, CTL, LTL. pdf   6up  
Set Theory Zermelo-Fraenkel, Neumann-Bernays-Goedel, Banach-Tarski. pdf   6up  
Cardinality Cantor-Schroeder-Bernstein theorem, continuum hypothesis. pdf   6up  
Relations Properties, orders, equivalence relations, composition. pdf   6up  
Functions Types, kernels, closures, fixed points. pdf   6up  
Hash Functions Universal hashing, perfect hashing.
Ordinals von Neumann ordinals, well-orderings, transfinite induction. pdf   6up  
Induction IND, LEP, well-orders, recursive datatypes, recursive functions. pdf   6up  
Recursion Sierpinski graphs, Hanoi transducer, Lucas theorem. pdf   6up  
Iteration Orbits and fixed points, Floyd's trick, Goodstein sequences. pdf   6up  
Iteration Ducci sequences, Pollard's rho method, Collatz problem. pdf   6up  
Iteration Mandelbrot, decidability, Knaster-Tarski. pdf   6up  
Combinatorics Combinations, permutations, binomials, ranking. pdf   6up  
Enumerations Semigroup actions, enumeration, ranking, unranking. pdf   6up  
Fibonacci Recurrence equations, Fibonacci numbers, Fibonacci field. pdf   6up  
Inclusion/Exclusion Pigeon Hole Principle, Erdos-Szekeres, integer solutions. pdf   6up  
Moebius Necklaces, bracelets, Lyndon words, Moebius inversion. pdf   6up  
Generating Functions Polynomials, power series, growth functions. pdf   6up  
Number Theory Euclidean algorithm, Chinese remainder, Wilson, Fermat. pdf   6up  
Number Theory Groups, Cayley tables, Fibonacci monoid, SLPs. pdf   6up  
Groups Abelian, symmetric, dihedral, normal subgroups. pdf   6up  
Groups Group presentations, Cayley graphs, Novikov-Boone-Britton. pdf   6up  
Actions Polya counting, Burnside's lemma. pdf   6up  
Polya-Redfield Cycle index polynomials, pattern inventory, lamplighter group. pdf   6up  
Semi-Rings Rings, polynomial rings, Schwartz's method. pdf   6up  
Polynomials Evaluation, interpolation, roots, Schwartz's method. pdf   6up  
Finite Fields Integral domains, irreducible polynomials, primitive elements. pdf   6up  
FF Applications Montgomery reduction, linear feedback shift registers, AES Rijndael. pdf   6up  
FF Codes Shannon, linear codes, syndrome, Hamming codes. pdf   6up  
Feedback Shift Registers GPS, Fibonacci, Galois feedback shift registers, feedback polynomial. pdf   6up  
Symbolic Dynamics Sofic systems, one-dimensional cellular automata. pdf   6up  
Ehrenfeucht-Mycielsky Non-learning, disjunctiveness, balance. pdf   pdf   
Sigma Automata Additive cellular automata, Fibonacci polynomials. pdf   6up