Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
3 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

Unifying B\"uchi Complementation Constructions

Seth J. Fogarty ; Orna Kupferman ; Thomas Wilke ; Moshe Y. Vardi.
Complementation of B\"uchi automata, required for checking automata containment, is of major theoretical and practical interest in formal verification. We consider two recent approaches to complementation. The first is the rank-based approach of Kupferman and Vardi, which operates over a DAG that&nbsp;[&hellip;]
Published on March 27, 2013
Volume 9, Issue 1
  • < Previous
  • 1
  • Next >