cs.FL papers | Gist.Science

Turn Complexity of Context-free Languages, Pushdown Automata and One-Counter Automata

This paper investigates the computational complexity of context-free, pushdown, and one-counter automata based on the number of "turns" (switches between increasing and decreasing stack height) in accepting computations, proving that determining whether this number is bounded is undecidable, establishing non-recursive trade-offs between automata types, and demonstrating an infinite hierarchy of complexity classes defined by sublinear turn bounds.

Giovanni PighizziniTue, 10 Ma💻 cs

Forgetting Event Order in Higher-Dimensional Automata

This paper resolves the fundamental mismatch between the combinatorial structure and observable behavior of Higher-Dimensional Automata by developing an order-independent semantics based on interval ipomsets, which unifies various categorical presentations and bisimulation concepts while eliminating artificial event ordering artifacts.

Safa ZouariTue, 10 Ma💻 cs

Randomise Alone, Reach as a Team

This paper investigates concurrent graph games with distributed randomization where team players lack a shared random source, establishing that memoryless strategies suffice for the threshold problem (placing it in $\exists\mathbb{R}$ and proving NP-hardness) and that almost-sure reachability is NP-complete, while introducing the IRATL logic and a corresponding solver.

Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri, Ali Shafiee, K. S. ThejaswiniTue, 10 Ma💻 cs

Mining Beyond the Bools: Learning Data Transformations and Temporal Specifications

This paper proposes a novel approach to mining data-aware temporal specifications from execution traces by combining Syntax Guided Synthesis with a finite-prefix interpretation of Temporal Stream Logic (TSL $_f$ ), enabling the robust and sample-efficient synthesis of reactive programs that capture both data transformations and temporal behaviors.

Sam Nicholas Kouteili, William Fishell, Christian Scaff, Mark Santolucito, Ruzica PiskacTue, 10 Ma💻 cs

Complexity of Linear Subsequences of $k$ -Automatic Sequences

This paper investigates the state complexity of automata recognizing relations and operations on $k$ -automatic sequences, establishing a link between the subword complexity of interior sequences and the state complexity of their linear subsequences while resolving a recent question by Zantema and Bosma regarding most-significant-digit-first inputs.

Delaram Moradi, Narad Rampersad, Jeffrey ShallitTue, 10 Ma🔢 math

Context-Free Trees

This paper investigates bona fide context-free trees by demonstrating their finite-state description via multi-edge NFAs and proving that the isomorphism problem for deterministic context-free trees is NL-complete in both rooted and non-rooted cases.

Jan Philipp WächterTue, 10 Ma🔢 math

FATE: A Formal Benchmark Series for Frontier Algebra of Multiple Difficulty Levels

The paper introduces FATE, a new formal algebra benchmark series spanning from undergraduate exercises to PhD-level research problems, which reveals that current state-of-the-art LLMs struggle significantly with formalizing advanced mathematical reasoning, achieving near-zero accuracy on the most difficult tasks despite stronger natural-language performance.

Jiedong Jiang, Wanyi He, Yuefeng Wang, Guoxiong Gao, Yongle Hu, Jingting Wang, Nailin Guan, Peihao Wu, Chunbo Dai, Liang Xiao, Bin DongTue, 10 Ma🤖 cs.LG

New properties of the $\varphi$ -representation of integers

This paper establishes new properties of the $\varphi$ -representation of integers, including a proof of Kimberling's 2012 conjecture, utilizing automated tools such as the Walnut theorem-prover and ChatGPT 5.

Jeffrey Shallit, Ingrid VukusicThu, 12 Ma🔢 math

The complexity of finite smooth words over binary alphabets

This paper establishes that factors of smooth words are f-smooth and advances Sing's conjecture on their complexity by proving the asymptotic growth rate for even alphabets, confirming the lower bound for all binary alphabets, and improving the upper bound for odd alphabets.

Julien Cassaigne, Raphaël HenryThu, 12 Ma🔢 math

The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory

This paper proposes a unified framework for the generation-recognition asymmetry in formal language theory by identifying six distinct dimensions of divergence, challenging the oversimplified view that generation is inherently easy while parsing is hard, and exploring the implications of these operational differences for fields ranging from compiler design to large language models.

Romain PeyrichouThu, 12 Ma💬 cs.CL

Formally Verified Linear-Time Invertible Lexing

This paper presents ZipLex, a formally verified framework in Scala that achieves linear-time invertible lexical analysis with longest-match semantics by combining a novel token sequence abstraction with verified data structures like zippers and memoization, demonstrating performance comparable to unverified tools while providing rigorous proofs of correctness and invertibility.

Samuel Chassot, Viktor KunčakMon, 09 Ma💻 cs

Marking Data-Informativity and Data-Driven Supervisory Control of Discrete-Event Systems

This paper introduces the concept of marking data-informativity and develops corresponding algorithms to design valid nonblocking supervisors for unknown discrete-event systems using available behavioral data, while also addressing cases where data is insufficient through restricted informativity and informatizability frameworks.

Yingying Liu, Kuma Fuchiwaki, Kai CaiMon, 09 Ma🔢 math

Attention Meets Reachability: Structural Equivalence and Efficiency in Grammar-Constrained LLM Decoding

This paper establishes that while language-equivalent context-free grammars yield identical token masks in grammar-constrained decoding, their structural differences significantly impact computational efficiency by introducing variable state-space blowups and ambiguity costs, leading to fundamental lower bounds on decoding work and new distortion metrics for masked sampling.

Faruk Alpay, Bilge SenturkMon, 09 Ma🤖 cs.LG

Warm Starting State-Space Models with Automata Learning

This paper establishes a formal correspondence between Moore machines and state-space models to demonstrate that initializing continuous SSMs with symbolically learned automata significantly improves training efficiency and accuracy compared to random initialization, thereby effectively leveraging symbolic inductive bias for learning complex systems.

William Fishell, Sam Nicholas Kouteili, Mark SantolucitoMon, 09 Ma🤖 cs.LG

History-Deterministic Büchi Automata are Succinct

This paper resolves a decade-old open problem by presenting a 65-state history-deterministic Büchi automaton that is strictly more succinct than any equivalent deterministic Büchi automaton, a result established through a combination of theoretical insights and computational assistance.

Antonio Casares, Aditya Prakash, K. S. Thejaswini2026-03-06💻 cs

Computational Complexity of Alignments

This paper investigates the computational complexity of alignment problems in process mining, establishing that the task is PSPACE-complete for safe Petri nets, NP-complete for various subclasses including process trees and T-systems, and solvable in polynomial time specifically for live, safe S-systems.

Christopher T. Schwanen, Wied Pakusa, Wil M. P. van der Aalst2026-03-06💻 cs

Algebraic Characterization of Reversible First Degree Cellular Automata over $\mathbb{Z}_d$

This paper establishes that the reversibility of any first-degree cellular automaton over $\mathbb{Z}_d$ for arbitrary lattice sizes can be determined in constant time by verifying three specific algebraic conditions on its eight defining parameters, thereby enabling the efficient synthesis and identification of all such reversible rules.

Baby C. J., Kamalika Bhattacharjee2026-03-06💻 cs

Reachability in VASS Extended with Integer Counters

This paper investigates the reachability problem for VASS extended with integer counters (VASS+Z), establishing that the problem is NP-complete for a single nonnegative counter, lies in the complexity class $\mathcal{F}_{d+2}$ for $d \geq 2$ via a KLMST-based algorithm, and significantly lowers the dimension required for PSPACE and TOWER hardness compared to standard VASS.

Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg + 5 more2026-03-06💻 cs

2-Coloring Cycles in One Round

This paper presents a one-round randomized distributed algorithm that 2-colors cycles with an expected monochromatic edge fraction below 0.24118 (improving the previous 0.25 bound) and establishes a new lower bound of 0.23879, with both results discovered by large language models and formalized in Lean 4.

Maxime Flin, Alesya Raevskaya, Ronja Stimpert + 2 more2026-03-06💻 cs

Why Are Linear RNNs More Parallelizable?

This paper establishes a theoretical foundation for the superior parallelizability of linear RNNs by demonstrating that they correspond to log-depth arithmetic circuits ( $\mathsf{NC}^1$ -complete), whereas nonlinear RNNs are fundamentally limited by their ability to solve $\mathsf{L}$ - and $\mathsf{P}$ -complete problems, thereby explaining why linear variants can be efficiently parallelized like transformers while traditional nonlinear RNNs cannot.

William Merrill, Hongjian Jiang, Yanhong Li + 2 more2026-03-06💻 cs

cs.FL