Analyzing Büchi Automata with Graph Neural Networks
B\"uchi 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\"uchi automata are computationally hard, raising the question if a learning-based data-driven analysis might be more efficient than using traditional algorithms. Since B\"uchi 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\"uchi automata when trained on automatically generated random automata datasets.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Mixed Nondeterministic-Probabilistic Automata: Blending graphical probabilistic models with nondeterminism
Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming-graphical models include Bayesian networks and factor graphs. In this paper we develo…
Probabilistic ProgrammingWeighted DAG Automata for Semantic Graphs
Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models invo…
Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata
A current goal in the graph neural network literature is to enable transformers to operate on graph-structured data, given their success on language and vision tasks. Since the transformer's original sinusoidal positiona…
Graph Neural NetworkMachine TranslationPositionComputational Hierarchy of Elementary Cellular Automata
The complexity of cellular automata is traditionally measured by their computational capacity. However, it is difficult to choose a challenging set of computational tasks suitable for the parallel nature of such systems.…
Learning Closed Signal Flow Graphs
We develop a learning algorithm for closed signal flow graphs - a graphical model of signal transducers. The algorithm relies on the correspondence between closed signal flow graphs and weighted finite automata on a sing…