Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
ramseysimsub [2022/09/09 00:50] rmayr |
ramseysimsub [2023/07/05 20:42] (current) |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| Here are some current tools for checking language inclusion of nondeterministic Buchi automata. | Here are some current tools for checking language inclusion of nondeterministic Buchi automata. | ||
| - | * [[tools | 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. Newer versions 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). | ||
| * [[http://goal.im.ntu.edu.tw|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. | * [[http://goal.im.ntu.edu.tw|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. | ||
| * [[https://github.com/Mazzocchi/FORKLIFT | FORKLIFT.]] It uses a subsumption-based technique, different from the Ramsey-based method. See [[https://doi.org/10.1007/978-3-031-13188-2_6 | CAV'22 paper]] and [[https://arxiv.org/abs/2207.13549 | the full version of the paper]] and [[https://github.com/parof/buchi-automata-benchmark | some benchmarks]]. The older [[https://github.com/parof/bait | BAIT tool]] by same authors uses similar methods, see [[https://doi.org/10.4230/LIPIcs.CONCUR.2021.3 | CONCUR 2021 paper]]. | * [[https://github.com/Mazzocchi/FORKLIFT | FORKLIFT.]] It uses a subsumption-based technique, different from the Ramsey-based method. See [[https://doi.org/10.1007/978-3-031-13188-2_6 | CAV'22 paper]] and [[https://arxiv.org/abs/2207.13549 | the full version of the paper]] and [[https://github.com/parof/buchi-automata-benchmark | some benchmarks]]. The older [[https://github.com/parof/bait | BAIT tool]] by same authors uses similar methods, see [[https://doi.org/10.4230/LIPIcs.CONCUR.2021.3 | CONCUR 2021 paper]]. | ||
| + | * [[tools | 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. Newer versions of the tool additionally use generalized automata minimization techniques using good approximations of multipebble simulations and trace inclusions (see the LMCS 2019 on the RABIT tool page). | ||
| Note: Subsumption-based techniques and simulation-based techniques are very different from each other. Thus the performance of the above tools can vary a lot between different (classes of) instances. I.e., instances that are hard for one tool may be easy for another, and vice-versa. So you might want to try out different tools, to see what works best for your particular automata. | Note: Subsumption-based techniques and simulation-based techniques are very different from each other. Thus the performance of the above tools can vary a lot between different (classes of) instances. I.e., instances that are hard for one tool may be easy for another, and vice-versa. So you might want to try out different tools, to see what works best for your particular automata. | ||