This is an old revision of the document!


Buchi Automata

Here are some current tools for checking language inclusion of Buchi automata.

  1. RABIT (Ramsey-based Buchi automata Inclusion Testing).

It implements a generalized version of the Ramsey-based method for Buchi automata inclusion checking with additional subsumption techniques using backward and forward simulation preorder. The latest version of the tool additionally uses generalized automata minimization techniques using good approximations of multipebble simulations and trace inclusions (see the LMCS 2019 on the RABIT tool page). Most recent version of the RABIT tool.

- GOAL tool. There are many other methods for checking Buchi automata inclusion/equivalence, e.g., Safra-based constructions, Muller-Schupp constructions, Safra-Pieteman construction, and Slice-based constructions. The GOAL tool implements many of these. On most instances RABIT performs better than GOAL and thus it can solve much larger instances.

People

Parosh Aziz AbdullaYu-Fang ChenLorenzo Clemente

Lukas HolikChih-Duo HongRichard MayrTomas Vojnar

References

ramseysimsub.1662653951.txt.gz · Last modified: (external edit)