Formal Languages and Automata Theory arXiv

An automata-based test for bricks over string algebras Amit Kuber, Annoy Sengupta arxiv.org/abs/2603.18820 [𝚌𝚜.𝙵𝙻 𝚖𝚊𝚝𝚑.𝚁𝚃]

State Complexity of Shifts of the Fibonacci Word Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic arxiv.org/abs/2603.18858 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙽𝚃]

Irreducibility of Semigroup Morphisms Paul C. Bell, Eva Foster, Daniel Reidenbach arxiv.org/abs/2603.15177 [𝚌𝚜.𝙵𝙻]

Visibly Recursive Automata Kévin Dubrulle, Véronique Bruyère, Guillermo A. Pérez, Gaëtan Staquet arxiv.org/abs/2603.11648 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙲𝙲]

The complexity of finite smooth words over binary alphabets Julien Cassaigne, Raphaël Henry arxiv.org/abs/2603.10733 [𝚌𝚜.𝙵𝙻 𝚖𝚊𝚝𝚑.𝙲𝙾 𝚖𝚊𝚝𝚑.𝙳𝚂]

Forgetting Event Order in Higher-Dimensional Automata Safa Zouari arxiv.org/abs/2603.08134 [𝚌𝚜.𝙵𝙻]

Turn Complexity of Context-free Languages, Pushdown Automata and One-Counter Automata Giovanni Pighizzini arxiv.org/abs/2603.08331 [𝚌𝚜.𝙵𝙻]

Context-Free Trees Jan Philipp Wächter arxiv.org/abs/2603.08624 [𝚌𝚜.𝙵𝙻 𝚖𝚊𝚝𝚑.𝙶𝚁]

Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems Yingying Liu, Kuma Fuchiwaki, Kai Cai arxiv.org/abs/2603.05508 [𝚌𝚜.𝙵𝙻 𝚖𝚊𝚝𝚑.𝙾𝙲]

Reachability in VASS Extended with Integer Counters Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg, Jérôme Leroux, Vincent Michielini, Łukasz Orlikowski, Antoni Puch, Henry Sinclair-Banks arxiv.org/abs/2603.05221 [𝚌𝚜.𝙵𝙻]

Algebraic Characterization of Reversible First Degree Cellular Automata over ℤd Baby C. J., Kamalika Bhattacharjee arxiv.org/abs/2603.05253 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙳𝙼]

Computational Complexity of Alignments Christopher T. Schwanen, Wied Pakusa, Wil M. P. van der Aalst arxiv.org/abs/2603.05331 [𝚌𝚜.𝙵𝙻]

History-Deterministic Büchi Automata are Succinct Antonio Casares, Aditya Prakash, K. S. Thejaswini arxiv.org/abs/2603.05380 [𝚌𝚜.𝙵𝙻]

5.2 earthquake 📍 53 km NW of Hirara, Japan 🕒 Mar 5 10:48:21 UTC (19m ago) ⬇️ Depth: 10 km earthquake.usgs.gov/earthquakes/ev…

Localising Stochasticity in Weighted Automata Smayan Agarwal, Aalok Thakkar arxiv.org/abs/2602.23805 [𝚌𝚜.𝙵𝙻]

A quadratic lower bound for 2DFAs against one-way liveness Kehinde Adeogun, Christos Kapoutsis arxiv.org/abs/2602.24279 [𝚌𝚜.𝙵𝙻]

Efficient Constructions of Finite-State Independent Normal Pairs Subin Pulari arxiv.org/abs/2602.23030 [𝚌𝚜.𝙵𝙻]

Expregular functions Thomas Colcombet, Nathan Lhote, Pierre Ohlmann arxiv.org/abs/2602.21019 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙻𝙾]

Automata Learning with an Incomplete but Inductive Teacher Daniel Stan, Adrien Pommellet, Juliette Jacquot arxiv.org/abs/2602.21073 [𝚌𝚜.𝙵𝙻]

NILE: Formalizing Natural-Language Descriptions of Formal Languages Tristan Kneisel, Marko Schmellenkamp, Fabian Vehlken, Thomas Zeume arxiv.org/abs/2602.19743 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙲𝙻 𝚌𝚜.𝙻𝙾]