RNN Generalization to Omega-Regular Languages
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912567072391168 |
|---|---|
| author | Pert, Charles Alrajeh, Dalal Russo, Alessandra |
| author_facet | Pert, Charles Alrajeh, Dalal Russo, Alessandra |
| contents | Büchi automata (BAs) recognize $ω$-regular languages defined by formal specifications like linear temporal logic (LTL) and are commonly used in the verification of reactive systems. However, BAs face scalability challenges when handling and manipulating complex system behaviors. As neural networks are increasingly used to address these scalability challenges in areas like model checking, investigating their ability to generalize beyond training data becomes necessary. This work presents the first study investigating whether recurrent neural networks (RNNs) can generalize to $ω$-regular languages derived from LTL formulas. We train RNNs on ultimately periodic $ω$-word sequences to replicate target BA behavior and evaluate how well they generalize to out-of-distribution sequences. Through experiments on LTL formulas corresponding to deterministic automata of varying structural complexity, from 3 to over 100 states, we show that RNNs achieve high accuracy on their target $ω$-regular languages when evaluated on sequences up to $8 \times$ longer than training examples, with $92.6\%$ of tasks achieving perfect or near-perfect generalization. These results establish the feasibility of neural approaches for learning complex $ω$-regular languages, suggesting their potential as components in neurosymbolic verification methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02491 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | RNN Generalization to Omega-Regular Languages Pert, Charles Alrajeh, Dalal Russo, Alessandra Machine Learning Formal Languages and Automata Theory Logic in Computer Science Büchi automata (BAs) recognize $ω$-regular languages defined by formal specifications like linear temporal logic (LTL) and are commonly used in the verification of reactive systems. However, BAs face scalability challenges when handling and manipulating complex system behaviors. As neural networks are increasingly used to address these scalability challenges in areas like model checking, investigating their ability to generalize beyond training data becomes necessary. This work presents the first study investigating whether recurrent neural networks (RNNs) can generalize to $ω$-regular languages derived from LTL formulas. We train RNNs on ultimately periodic $ω$-word sequences to replicate target BA behavior and evaluate how well they generalize to out-of-distribution sequences. Through experiments on LTL formulas corresponding to deterministic automata of varying structural complexity, from 3 to over 100 states, we show that RNNs achieve high accuracy on their target $ω$-regular languages when evaluated on sequences up to $8 \times$ longer than training examples, with $92.6\%$ of tasks achieving perfect or near-perfect generalization. These results establish the feasibility of neural approaches for learning complex $ω$-regular languages, suggesting their potential as components in neurosymbolic verification methods. |
| title | RNN Generalization to Omega-Regular Languages |
| topic | Machine Learning Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2509.02491 |