- Generating Fibonacci Words via the Prefix--Suffix Duplication Operation
2026/07/22 by Diego Cabrera Salamanca, Taylor J. Smith · 2 voices
#cs.FL #cs.DM
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent
2026/07/22 by Yinfeng Zhu · 1 voice
#cs.FL
- Ultrametric Convergence of Guarded Automata and Applications to Structural Input Validation
2026/07/21 by Atanas Ilchev, Hristo Kiskinov, George Pashev +1 · 1 voice
#cs.FL
- Stringological sequence prediction II: Right-to-left automaticity and related complexity measures
2026/07/19 by Vanessa Kosoy · 1 voice
#cs.FL #cs.DS #cs.LG
- The Σ-Chain Product: A Succinct Model of Automata (De)Composition (Extended Version)
2026/07/18 by Roberto Borelli, Davide Bresolin, Luca Geatti +2 · 1 voice
#cs.FL #cs.LO
- 3-VASS Reachability is in EXPSPACE
2026/07/16 by Weijun Chen, Bo Fu, Yuxi Fu +4 · 1 voice
#cs.FL #cs.LO
- Completely Reachable Road Coloring
2026/07/13 by Mikhail V. Volkov, Yinfeng Zhu · 1 voice
#cs.FL #cs.CC
- An Empirical Comparison of General Context-Free Parsers
2026/06/07 by Huan Vo, Danushka Liyanage, Hong Jin Kang +2 · 2 voices
Computer Science · #cs.FL #cs.PF #cs.PL #cs.SE
- Continuous Diffusion Models Can Obey Formal Syntax
2026/02/12 by Jinwoo Kim, Taylor Berg-Kirkpatrick, Loris D'Antoni · 2 voices
Computer Science · #cs.LG #cs.FL
- Beyond Correctness: Exposing LLM-generated Logical Flaws in Reasoning via Multi-step Automated Theorem Proving
2025/12/29 by Xinyi Zheng, Ningke Li, Zheng, Xinyi +11 · 1 voice
Computer Science · Medicine · #Artificial Intelligence in Healthcare and Education #Explainable Artificial Intelligence (XAI) #Topic Modeling #cs.FL #cs.SE
- Determination of the fifth Busy Beaver value
2025/09/15 by The bbchallenge Collaboration, Justin Blanchard, Blanchard, Justin +34 · 20 voices · 2 citations
Agricultural and Biological Sciences · Environmental Science · #Botany and Plant Ecology Studies #Ecology and biodiversity studies #cs.FL #cs.LO #math.LO
- Topological Kleene Field Theories as a model of computation
2025/03/20 by Ángel González-Prieto, González-Prieto, Ángel, Eva Miranda +4 · 2 voices
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Topological and Geometric Data Analysis #cs.FL #math.CT #math.DG #math.DS
- Tokenisation is NP-Complete
2024/12/19 by Philip Whittington, Gregor Bachmann, Whittington, Philip +3 · 8 voices · 5 citations
#cs.DS #cs.CL #cs.FL
- Simulating Hard Attention Using Soft Attention
2024/12/13 by Andy Yang, Lena Strobl, Yang, Andy +5 · 1 voice · 4 citations
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #cs.CL #cs.FL #cs.LG
- Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues
2024/11/19 by Riccardo Grazzi, Grazzi, Riccardo, Julien Siems +9 · 3 voices · 16 citations
Engineering · Computer Science · #cs.LG #cs.CL #cs.FL
- Verifying Quantum Circuits with Level-Synchronized Tree Automata (Technical Report)
2024/10/24 by Parosh Aziz Abdulla, Yo-Ga Chen, Abdulla, Parosh Aziz +15 · 1 voice · 5 citations
Computer Science · #cs.LO #cs.FL
- SELP: Generating Safe and Efficient Task Plans for Robot Agents with Large Language Models
2024/09/28 by Yi Wu, Zikang Xiong, Wu, Yi +13 · 1 voice · 4 citations
#cs.RO #cs.AI #cs.CL #cs.FL
- Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
2024/02/15 by Nur Lan, Emmanuel Chemla, Lan, Nur +3 · 3 voices · 7 citations
Computer Science · #Natural Language Processing Techniques #cs.CL #cs.FL
- Linear Matching of JavaScript Regular Expressions
2023/11/29 by Aurèle Barrière, Clément Pit-Claudel · 1 voice · 2 citations
Computer Science · #Advanced Malware Detection Techniques #Software Testing and Debugging Techniques #Web Data Mining and Analysis #cs.FL #cs.PL
- Proving Properties of φ-Representations with the Walnut Theorem-Prover
2023/05/04 by Jeffrey Shallit · 1 citation
Computer Science · Mathematics · #math.NT #cs.DM #cs.FL
- Tighter Bounds on the Expressivity of Transformer Encoders
2023/01/25 by David Chiang, Chiang, David, Peter Cholak +3 · 1 voice · 9 citations
#cs.LG #cs.FL #cs.LO
- Stack-Aware Hyperproperties
2023/01/27 by Ali Bajwa, Bajwa, Ali, Minjian Zhang +5 · 1 voice
Computer Science · Social Sciences · #Access Control and Trust #Distributed systems and fault tolerance #Logic, programming, and type systems #cs.CR #cs.FL #cs.LO
- Memory Augmented Large Language Models are Computationally Universal
2023/01/10 by Dale Schuurmans, Schuurmans, Dale · 6 voices · 5 citations
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #Topic Modeling #cs.CL #cs.FL
- Transformers Learn Shortcuts to Automata
2022/10/19 by Bingbin Liu, Jordan T. Ash, Liu, Bingbin +7 · 3 voices · 39 citations
Computer Science · #Algorithms and Data Compression #Machine Learning and Algorithms #Topic Modeling #cs.FL #cs.LG #stat.ML
- Neural Networks and the Chomsky Hierarchy
2022/07/05 by Grégoire Delétang, Delétang, Grégoire, Anian Ruoss +20 · 2 voices · 30 citations
Computer Science · Engineering · #Ferroelectric and Negative Capacitance Devices #Natural Language Processing Techniques #Topic Modeling #cs.AI #cs.CL #cs.FL #cs.LG
- Information dynamics and the arrow of time
2021/09/16 by Aram Ebtekar, Ebtekar, Aram · 1 voice
Computer Science · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Computability, Logic, AI Algorithms #Statistical Mechanics and Entropy #cond-mat.stat-mech #cs.FL #cs.IT #nlin.CG
- Towards an Automatic Proof of Lamport's Paxos
2021/08/19 by Aman Goel, Karem A. Sakallah · 1 voice
Computer Science · #Formal Methods in Verification #Logic, programming, and type systems #Security and Verification in Computing #cs.DC #cs.FL #cs.LO
- Undecidability of Underfitting in Learning Algorithms
2021/02/04 by Sonia Sehra, Sehra, Sonia, David Flores +3 · 1 voice
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Information Theory (cs.IT) #Machine Learning (cs.LG) #cs.AI #cs.FL #cs.IT #cs.LG
- Equivalence of Dataflow Graphs via Rewrite Rules Using a Graph-to-Sequence Neural Model
2020/02/17 by Steve Kommrusch, Théo Barollet, Kommrusch, Steve +3 · 2 voices
Computer Science · #Formal Methods in Verification #Software Engineering Research #Software Testing and Debugging Techniques #cs.FL #cs.LG #stat.ML
- Syntax Error Recovery in Parsing Expression Grammars
2018/06/28 by Sérgio Medeiros, Fabio Mascarenhas · 1 voice
#cs.PL #cs.FL
more