Formal Languages and Automata Theory

Authors and titles for recent submissions

• Fri, 17 Apr 2026
• Thu, 16 Apr 2026
• Wed, 15 Apr 2026
• Tue, 14 Apr 2026
• Mon, 13 Apr 2026

See today's new changes

Fri, 17 Apr 2026 (showing 3 of 3 entries )

[1] arXiv:2604.15177 (cross-list from cs.CC) [pdf, other]

Title: Complexity of Fungal Automaton Prediction

Enrico Formenti, Eric Goles, Kévin Perrot, Martín Ríos-Wilson, Domingo Ruiz-Tala

Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)

[2] arXiv:2604.14966 (cross-list from nlin.CG) [pdf, html, other]

Title: Measuring the Computational Power of Finite Patches of Cellular Automata

Attila Egri-Nagy, Chrystopher L. Nehaniv

Comments: 6 pages, 4 figures, final version will be published elsewhere

Subjects: Cellular Automata and Lattice Gases (nlin.CG); Formal Languages and Automata Theory (cs.FL)

[3] arXiv:2604.14512 (cross-list from cs.CR) [pdf, html, other]

Title: CBCL: Safe Self-Extending Agent Communication

Hugo O'Connor

Comments: 10 pages. Accepted at IEEE LangSec Workshop 2026 (camera-ready). Reference implementation, Lean 4 formalization, and verified parser: this https URL ; Nostr transport binding: this https URL

Subjects: Cryptography and Security (cs.CR); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

Thu, 16 Apr 2026

No updates for this time period.

Wed, 15 Apr 2026 (showing 2 of 2 entries )

[4] arXiv:2604.12457 [pdf, other]

Title: Characterizing normality via automata and random matrix products

Laurent Bienvenu (CNRS, LaBRI), Santiago Cifuentes (ICC, UBA), Hugo Gimbert (CNRS, LaBRI)

Subjects: Formal Languages and Automata Theory (cs.FL)

[5] arXiv:2604.11935 (cross-list from cs.PL) [pdf, html, other]

Title: Polyregular equivalence is undecidable in higher-order types

Mikołaj Bojańczyk, Grzegorz Fabiański, Rafał Stefański

Subjects: Programming Languages (cs.PL); Formal Languages and Automata Theory (cs.FL)

Tue, 14 Apr 2026 (showing 3 of 3 entries )

[6] arXiv:2604.11567 [pdf, html, other]

Title: Minimizing Streaming String Transducers: An algebraic approach

Yahia Idriss Benalioua, Nathan Lhote, Pierre-Alain Reynier

Comments: Long version of DLT 2026 paper

Subjects: Formal Languages and Automata Theory (cs.FL)

[7] arXiv:2604.10124 [pdf, html, other]

Title: On a Constraint on Invariant Measures of Certain Cellular Automata

Matan Tal

Subjects: Formal Languages and Automata Theory (cs.FL); Dynamical Systems (math.DS); Probability (math.PR)

[8] arXiv:2604.09678 (cross-list from cs.NI) [pdf, html, other]

Title: NetAgentBench: A State-Centric Benchmark for Evaluating Agentic Network Configuration

Ahmed Twabi, Yepeng Ding, Tohru Kondo

Comments: 9 pages

Subjects: Networking and Internet Architecture (cs.NI); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL)

Mon, 13 Apr 2026 (showing 1 of 1 entries )

[9] arXiv:2604.09318 (cross-list from cs.PL) [pdf, html, other]

Title: CIR+CVN: Bridging LLM Semantic Understanding and Petri-Net Verification for Concurrent Programs

Kaiwen Zhang, Guanjun Liu

Subjects: Programming Languages (cs.PL); Formal Languages and Automata Theory (cs.FL)