CS 373: Theory of Computation

Extra Resources

• Notes from the previous semesters

• Alternating finite automata
• Ancient notions of an automaton
• Büchi automata
• Cellular automata
• Finite state machine
• Hybrid automata
• Linear bounded automata
• Pebble automata
• Pushdown automata
• Recursive automata
• Probabilistic automata and stochastic languages
• Quantum finite automata
• Tree walking automata
• Tree automata

• Firing squad synchronization problem
• L-system
• Post correspondence problem
• Tag system
• Turing_machine
• Word problems for groups