Formal Languages and Automata Theory

Authors and titles for cs.FL in Oct 2023

[1]  arXiv:2310.01003 [pdf, other]

Title: Conflict-Aware Active Automata Learning

Authors: Tiago Ferreira (University College London), Léo Henry (University College London), Raquel Fernandes da Silva (University College London), Alexandra Silva (Cornell University)

Comments: In Proceedings GandALF 2023, arXiv:2309.17318; extended version at arXiv:2308.14781

Journal-ref: EPTCS 390, 2023, pp. 150-167

Subjects: Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG)

[2]  arXiv:2310.01941 [pdf, other]

Title: Bandwidth of Timed Automata: 3 Classes

Authors: Eugene Asarin, Aldric Degorre, Catalin Dima, Bernardo Jacobo Inclan

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

[3]  arXiv:2310.01992 [pdf, other]

Title: Acyclic Petri and Workflow Nets with Resets

Authors: Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman, Filip Mazowiecki, Henry Sinclair-Banks

Comments: Preprint for FSTTCS'23 containing 28 pages and 7 figures

Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[4]  arXiv:2310.02204 [pdf, other]

Title: Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata

Authors: Ismaël Jecker, Filip Mazowiecki, David Purser

Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[5]  arXiv:2310.02393 [pdf, ps, other]

Title: Symbolic Automata: $ω$-Regularity Modulo Theories

Authors: Margus Veanes, Thomas Ball, Gabriel Ebner, Olli Saarikivi

Subjects: Formal Languages and Automata Theory (cs.FL); Data Structures and Algorithms (cs.DS)

[6]  arXiv:2310.03817 [pdf, ps, other]

Title: Logical Languages Accepted by Transformer Encoders with Hard Attention

Authors: Pablo Barcelo, Alexander Kozachinskiy, Anthony Widjaja Lin, Vladimir Podolskii

Subjects: Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG)

[7]  arXiv:2310.04764 [pdf, other]

Title: Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs

Authors: Radu Iosif, Florian Zuleger

Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[8]  arXiv:2310.04870 [pdf, other]

Title: Lemur: Integrating Large Language Models in Automated Program Verification

Authors: Haoze Wu, Clark Barrett, Nina Narodytska

Comments: Accepted at ICLR'24

Subjects: Formal Languages and Automata Theory (cs.FL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Logic in Computer Science (cs.LO)

[9]  arXiv:2310.07010 [pdf, ps, other]

Title: The Lexicographically Least Binary Rich Word Achieving the Repetition Threshold

Authors: James Currie, Narad Rampersad

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

[10]  arXiv:2310.08248 [pdf, other]

Title: Visualizing a Nondeterministic to Deterministic Finite-State Machine Transformation

Authors: Tijana Minic, Marco T. Morazán

Comments: Presented at The 2023 Scheme and Functional Programming Workshop (arXiv:cs/0101200)

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

[11]  arXiv:2310.08412 [pdf, other]

Title: Non-reducible Modal Transition Systems

Authors: Davide Basile

Comments: draft

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

[12]  arXiv:2310.09008 [pdf, other]

Title: New Lower Bounds for Reachability in Vector Addition Systems

Authors: Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Jérôme Leroux, Łukasz Orlikowski

Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[13]  arXiv:2310.09115 [pdf, ps, other]

Title: Determinization of Integral Discounted-Sum Automata is Decidable

Authors: Shaull Almagor, Neta Dafni

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

[14]  arXiv:2310.10136 [pdf, other]

Title: Mata, a Fast and Simple Finite Automata Library (Technical Report)

Authors: David Chocholatý, Tomáš Fiedor, Vojtěch Havlena, Lukáš Holík, Martin Hruška, Ondřej Lengál, Juraj Síč

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

[15]  arXiv:2310.11481 [pdf, other]

Title: Contracting Tsetlin Machine with Absorbing Automata

Authors: Bimal Bhattarai, Ole-Christoffer Granmo, Lei Jiao, Per-Arne Andersen, Svein Anders Tunheim, Rishad Shafik, Alex Yakovlev

Comments: Accepted to ISTM2023. 7 pages, 8 figures

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

[16]  arXiv:2310.11825 [pdf, other]

Title: Reduced-Complexity Verification for K-Step and Infinite-Step Opacity in Discrete Event Systems

Authors: Xiaoyan Li, Christoforos N. Hadjicostis, Zhiwu Li

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

[17]  arXiv:2310.13309 [pdf, other]

Title: Enumerating regular languages in radix order : Revisiting the Ackerman-Shallit algorithm

Authors: Nadime Francis, Victor Marsault

Comments: 8 pages

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

[18]  arXiv:2310.13498 [pdf, other]

Title: Checking History-Determinism is NP-hard for Parity Automata

Authors: Aditya Prakash

Comments: Full version of the paper accepted at FoSSaCS 2024. Some minor editorial changes from the previous version following suggestions from anonymous reviewers

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

[19]  arXiv:2310.13897 [pdf, other]

Title: Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages

Authors: Dana Angluin, David Chiang, Andy Yang

Subjects: Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG); Logic in Computer Science (cs.LO)

[20]  arXiv:2310.14114 [pdf, ps, other]

Title: Note on dissecting power of regular languages

Authors: Josef Rukavicka

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

[21]  arXiv:2310.16022 [pdf, other]

Title: A Robust Measure on FDFAs Following Duo-Normalized Acceptance

Authors: Dana Fisman, Emmanuel Goldberg, Oded Zimerman

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

[22]  arXiv:2310.16740 [pdf, ps, other]

Title: Reachability in Fixed VASS: Expressiveness and Lower Bounds

Authors: Andrei Draghici, Christoph Haase, Andrew Ryzhikov

Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)

[23]  arXiv:2310.16798 [pdf, other]

Title: Reachability in Continuous Pushdown VASS

Authors: A. R. Balasubramanian, Rupak Majumdar, Ramanathan S. Thinniyam, Georg Zetzsche

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

[24]  arXiv:2310.17295 [pdf, ps, other]

Title: Normal Forms for Elements of the ${}^*$-Continuous Kleene Algebras $K\mathop{\otimes_{\cal R}} C_2'$

Authors: Mark Hopkins, Hans Leiß

Comments: 32 pages, 4 figures

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

[25]  arXiv:2310.20433 [pdf, other]

Title: Simple and tight complexity lower bounds for solving Rabin games

Authors: Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, K. S. Thejaswini

Comments: 10 pages, 5 figures. To appear in SOSA 2024

Subjects: Formal Languages and Automata Theory (cs.FL); Data Structures and Algorithms (cs.DS)