论文标题
用图神经网络分析Büchi自动机
Analyzing Büchi Automata with Graph Neural Networks
论文作者
论文摘要
无限单词上的Büchi自动机提出了许多有趣的问题，并经常用于程序验证和模型检查。 Büchi自动机上的许多问题在计算上很难，这提出了一个问题，如果基于学习的数据驱动分析可能比使用传统算法更有效。由于Büchi自动机可以用图表示，因此图神经网络是这种基于学习的分析的自然选择。在本文中，我们演示了如何使用图形神经网络可靠地预测Büchi自动机的基本属性。
Büchi Automata on infinite words present many interesting problems and are used frequently in program verification and model checking. A lot of these problems on Büchi automata are computationally hard, raising the question if a learning-based data-driven analysis might be more efficient than using traditional algorithms. Since Büchi automata can be represented by graphs, graph neural networks are a natural choice for such a learning-based analysis. In this paper, we demonstrate how graph neural networks can be used to reliably predict basic properties of Büchi automata when trained on automatically generated random automata datasets.
