Lecture 5 [slides]

summary

• State-space reduction of finite automata over finite and infinite words
• Simulations and bisimulations for finite and Büchi automata

  references

• “On the Origins of Bisimulation and Coinduction”, Sangiorgi, 2009
• “Three partition-refinement algorithms”, Paige and Tarjan, 1987
• “Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata”, Etessami, Wilke, and Schüller, 2005
• “Concurrency and automata on infinite sequences”, David Park, 1981