Algebraic Characterizations of Classes of Regular Languages in DynFO
Corentin Barloy, Felix Tschirbs, Nils Vortmeier, Thomas Zeume · 2026
Read Algebraic Characterizations of Classes of Regular Languages in DynFO by Corentin Barloy, Felix Tschirbs, Nils Vortmeier, Thomas Zeume (2026) 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-2601-18429.txt.
Description
Corentin Barloy and three colleagues study how small logic rules can keep track of sets of words as they change. The frame is a live one: a word list is kept up to date while bits flip one by one. A rule set counts as fit if it can state, after each flip, which words still pass a fixed test. Past work showed the full set of plain word tests can be kept in this way.
The team sort the word tests into finer ranks. For each rank they ask what kind of maths the rules must hold to stay in step. Their ranks use forms from algebra, the study of sets with rules for join and swap. The work ties two fields that seem far apart: the shape of words and the shape of change. That tie may help in checks on live data streams.
Catalog record
| CREATOR | Corentin Barloy, Felix Tschirbs, Nils Vortmeier, Thomas Zeume |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-18429