RNN Generalization to Omega-Regular Languages

Charles Pert, Dalal Alrajeh, Alessandra Russo · 2025

Read RNN Generalization to Omega-Regular Languages by Charles Pert, Dalal Alrajeh, Alessandra Russo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02491.txt.

Description

Charles Pert, Dalal Alrajeh, and Alessandra Russo present a 2025 computer science paper testing whether recurrent neural networks can learn omega-regular languages, the infinite-word languages used to specify reactive system behaviour. Such languages are usually handled by Büchi automata, which face scaling problems.

Networks were trained on eventually repeating infinite words to mimic target automata built from temporal logic formulas. Test automata ranged from a handful of states to over a hundred. Networks were then judged on sequences far longer than any training example. Most tasks reached perfect or near-perfect generalisation at eight times the training length. The authors present this as the first such study, supporting neural components inside verification tools that mix learning with logic.

Catalog record

CREATORCharles Pert, Dalal Alrajeh, Alessandra Russo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-02491

Browse the full library · About the Tower of Babel