Skip to main content
archive Search
Submit Donate Log in

Press Enter to search · Advanced search

Formal Languages and Automata Theory

Authors and titles for recent submissions

  • Mon, 16 Nov 2026
  • Fri, 13 Nov 2026
  • Wed, 11 Nov 2026
  • Tue, 10 Nov 2026
  • Mon, 9 Nov 2026

See today's new changes

Total of 15 entries
Showing up to 50 entries per page: fewer | more | all

Mon, 16 Nov 2026 (showing 3 of 3 entries )

[1] arXiv:2611.17742 [pdf, html, other]
Title: Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)
James Harland
Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
[2] arXiv:2611.18470 (cross-list from cs.GT) [pdf, html, other]
Title: Stochastic Games with Distributional Entropy Objectives
Shankaranarayanan Krishna, Durgam Latha, Dion Reji, Ashutosh Trivedi
Subjects: Computer Science and Game Theory (cs.GT); Formal Languages and Automata Theory (cs.FL)
[3] arXiv:2611.17999 (cross-list from math.CO) [pdf, html, other]
Title: Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Damien Jamet, Matthieu Rosenfeld
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Formal Languages and Automata Theory (cs.FL)

Fri, 13 Nov 2026 (showing 3 of 3 entries )

[4] arXiv:2611.16562 [pdf, html, other]
Title: The Regular Cover Problem is NP-complete
Stefan Hetzl, Parham Shadman
Subjects: Formal Languages and Automata Theory (cs.FL)
[5] arXiv:2611.17235 (cross-list from cs.AI) [pdf, html, other]
Title: Al-Ghasali: A Computational Framework for Simulating Islamic Jurisprudential Rulings via Finite State Automata and Large Language Models
Elnaserledinellah Mahmoud Abdelwahab
Comments: 18 pages, 1 figure
Subjects: Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL)
[6] arXiv:2611.14887 (cross-list from cs.DS) [pdf, html, other]
Title: Characterizing Local Breadth in Language Generation
Jon Kleinberg, Fan Wei
Subjects: Data Structures and Algorithms (cs.DS); Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG); Machine Learning (stat.ML)

Wed, 11 Nov 2026 (showing 1 of 1 entries )

[7] arXiv:2611.13061 [pdf, html, other]
Title: The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary
Nicklas Nidhögg
Comments: 87 pages, 13 tables. Artifact: this https URL . The programs and their outputs are in the artifact, with a verifier that reruns every program and holds each reported number to the output line it rests on. Companion to arXiv:2608.03473, arXiv:2608.09761, arXiv:2609.10600, arXiv:2610.08854 and arXiv:2610.30168
Subjects: Formal Languages and Automata Theory (cs.FL); Computation and Language (cs.CL); Data Structures and Algorithms (cs.DS); Programming Languages (cs.PL)

Tue, 10 Nov 2026 (showing 6 of 6 entries )

[8] arXiv:2611.11080 [pdf, html, other]
Title: Two barriers for minimal time firing squads, with applications to four and five states
Kia Keng Giam
Comments: 34 pages, 18 figures, accepted (awaiting print) at the Journal of Cellular Automata
Subjects: Formal Languages and Automata Theory (cs.FL); Cellular Automata and Lattice Gases (nlin.CG)
[9] arXiv:2611.10911 [pdf, html, other]
Title: Towards A Parametrized Complexity of Determinization
Ivan Baburin, Ryan Cotterell
Subjects: Formal Languages and Automata Theory (cs.FL)
[10] arXiv:2611.10136 [pdf, html, other]
Title: Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches
Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, Paweł Parys
Journal-ref: 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 21:1-21:24, Schloss Dagstuhl - Leibniz-Zentrum f\"ur Informatik (2026)
Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
[11] arXiv:2611.12618 (cross-list from cs.CC) [pdf, other]
Title: Type-logical grammars and formal languages
Richard Moot (LIRMM,CNRS,LIRMM | PIPL,UM)
Subjects: Computational Complexity (cs.CC); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
[12] arXiv:2611.12315 (cross-list from cs.PL) [pdf, html, other]
Title: Beating Rytter's Bound: All-Pairs CFL Reachability in $O(n^3(\log\log n)^2/(\log n)^2)$ Time
Rupak Majumdar
Comments: 25 pages
Subjects: Programming Languages (cs.PL); Formal Languages and Automata Theory (cs.FL)
[13] arXiv:2611.11572 (cross-list from cs.CC) [pdf, html, other]
Title: Closing the Complexity Gap for Wheeler Graph Recognition on $d$-NFAs
Kengo Hashimoto
Subjects: Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL)

Mon, 9 Nov 2026 (showing 2 of 2 entries )

[14] arXiv:2611.09157 [pdf, html, other]
Title: Word Subtraction Games
Yusuke Inoue, Hiroki Inazu
Subjects: Formal Languages and Automata Theory (cs.FL)
[15] arXiv:2611.09136 [pdf, html, other]
Title: Shortest Synchronizing Words on Product Automata
Henning Fernau, Igor Rystsov
Subjects: Formal Languages and Automata Theory (cs.FL)
Total of 15 entries
Showing up to 50 entries per page: fewer | more | all
We gratefully acknowledge support from our major funders, member institutions, , and all contributors.
About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab)