Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

State of B\"uchi Complementation

Ming-Hsien Tsai ; Seth Fogarty ; Moshe Y. Vardi ; Yih-Kuen Tsay.
Complementation of B\"uchi automata has been studied for over five decades since the formalism was introduced in 1960. Known complementation constructions can be classified into Ramsey-based, determinization-based, rank-based, and slice-based approaches. Regarding the performance of these&nbsp;[&hellip;]
Published on December 18, 2014
Volume 10, Issue 4

B\"uchi Complementation and Size-Change Termination

Seth Fogarty ; Moshe Y. Vardi.
We compare tools for complementing nondeterministic B\"uchi automata with a recent termination-analysis algorithm. Complementation of B\"uchi automata is a key step in program verification. Early constructions using a Ramsey-based argument have been supplanted by rank-based constructions with&nbsp;[&hellip;]
Published on February 27, 2012
Volume 8, Issue 1
  • < Previous
  • 1
  • Next >