Formal Languages and Automata Theory

Authors and titles for cs.FL in Apr 2024

[1]  arXiv:2404.02040 [pdf, other]

Title: Transformers as Transducers

Authors: Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, Ashish Sabharwal

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

[2]  arXiv:2404.03039 [pdf, ps, other]

Title: Illustrating Finite Automata with Grail+ and TikZ

Authors: Alastair May, Taylor J. Smith

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

[3]  arXiv:2404.07823 [pdf, ps, other]

Title: Learning Deterministic Multi-Clock Timed Automata

Authors: Yu Teng, Miaomiao Zhang, Jie An

Comments: 12 pages. It is an author version of the paper with the same title accepted by HSCC 2024

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

[4]  arXiv:2404.08469 [pdf, ps, other]

Title: Supervisory Control Theory with Event Forcing

Authors: Michel Reniers, Kai Cai

Comments: 12 pages, 7 figures

Subjects: Formal Languages and Automata Theory (cs.FL); Systems and Control (eess.SY)

[5]  arXiv:2404.09862 [pdf, other]

Title: A Uniform Framework for Language Inclusion Problems

Authors: Kyveli Doveri, Pierre Ganty, Chana Weil-Kennedy

Comments: Published as part of the Festschrift for Javier Esparza "Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday"

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

[6]  arXiv:2404.09888 [pdf, other]

Title: Flow-Based Synthesis of Reactive Tests for Discrete Decision-Making Systems with Temporal Logic Specifications

Authors: Josefine B. Graebener, Apurva S. Badithela, Denizalp Goktas, Wyatt Ubellacker, Eric V. Mazumdar, Aaron D. Ames, Richard M. Murray

Comments: Manuscript

Subjects: Formal Languages and Automata Theory (cs.FL); Robotics (cs.RO); Systems and Control (eess.SY)

[7]  arXiv:2404.10516 [pdf, other]

Title: Exact descriptional complexity of determinization of input-driven pushdown automata

Authors: Olga Martynova

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

[8]  arXiv:2404.10653 [pdf, other]

Title: Context-Free Languages of String Diagrams

Authors: Matt Earnshaw, Mario Román

Subjects: Formal Languages and Automata Theory (cs.FL); Category Theory (math.CT)

[9]  arXiv:2404.10752 [pdf, other]

Title: Computing Inductive Invariants of Regular Abstraction Frameworks

Authors: Philipp Czerner, Javier Esparza, Valentin Krasotin, Christoph Welzel-Mohr

Comments: 24 pages

Subjects: Formal Languages and Automata Theory (cs.FL); Distributed, Parallel, and Cluster Computing (cs.DC)

[10]  arXiv:2404.11096 [pdf, ps, other]

Title: Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples

Authors: Farah Haneef

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

[11]  arXiv:2404.11746 [pdf, ps, other]

Title: On the Representation of Block Languages

Authors: Guilherme Duarte, Nelma Moreira, Luca Prigioniero, Rogério Reis

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

[12]  arXiv:2404.13577 [pdf, ps, other]

Title: Characterization of Isometric Words based on Swap and Mismatch Distance

Authors: M. Anselmo, G. Castiglione, M. Flores, D. Giammarresi, M. Madonia, S. Mantaci

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

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

Title: Opacity complexity of automatic sequences. The general case

Authors: J.-P. Allouche, J.-Y. Yao

Subjects: Formal Languages and Automata Theory (cs.FL); Combinatorics (math.CO); Number Theory (math.NT)

[14]  arXiv:2404.15052 [pdf, other]

Title: Finite Automata for Efficient Graph Recognition

Authors: Frank Drewes, Berthold Hoffmann, Mark Minas

Comments: 23 pages, accepted for publication in the Postproceedings of the 14th International Workshop on Graph Computational Models (GCM 2023)

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

[15]  arXiv:2404.15496 [pdf, other]

Title: The Algebras for Automatic Relations

Authors: Rémi Morvan

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

[16]  arXiv:2404.16492 [pdf, ps, other]

Title: On the topology of concurrent systems

Authors: Catarina Faustino, Thomas Kahl, Rodrigo Lopes

Comments: 24 pages

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

[17]  arXiv:2404.16518 [pdf, other]

Title: Edit Distance of Finite State Transducers

Authors: C. Aiswarya, Amaldev Manuel, Saina Sunny

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

[18]  arXiv:2404.16624 [pdf, ps, other]

Title: Development of parallel programs on shared data-structures -- Revised version

Authors: Ketil Stølen

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

[19]  arXiv:2404.17492 [pdf, other]

Title: Regular Expressions with Backreferences and Lookaheads Capture NLOG

Authors: Yuya Uezato

Comments: Author's version of a paper accepted at ICALP 2024

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

[20]  arXiv:2404.17530 [pdf, other]

Title: Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata

Authors: Rohan Acharya, Marcin Jurdziński, Aditya Prakash

Comments: Full version of paper accepted at ICALP 2024

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

[21]  arXiv:2404.18282 [pdf, other]

Title: Monitoring Real-Time Systems under Parametric Delay

Authors: Martin Fränzle, Thomas M. Grosen, Kim G. Larsen, Martin Zimmermann

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

[22]  arXiv:2404.01219 (cross-list from cs.RO) [pdf, other]

Title: LTL-D*: Incrementally Optimal Replanning for Feasible and Infeasible Tasks in Linear Temporal Logic Specifications

Authors: Jiming Ren, Haris Miller, Karen M. Feigh, Samuel Coogan, Ye Zhao

Comments: 8 pages,9 figures

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

[23]  arXiv:2404.03430 (cross-list from cs.PL) [pdf, ps, other]

Title: Equivalence and Similarity Refutation for Probabilistic Programs

Authors: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Đorđe Žikelić

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

[24]  arXiv:2404.03985 (cross-list from cs.LO) [pdf, ps, other]

Title: Implicit automata in λ-calculi III: affine planar string-to-string functions

Authors: Cécilia Pradic, Ian Price

Comments: 17+3 pages, 7 figures

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

[25]  arXiv:2404.04201 (cross-list from cs.PL) [pdf, ps, other]

Title: V-Star: Learning Visibly Pushdown Grammars from Program Inputs

Authors: Xiaodong Jia, Gang Tan

Comments: PLDI '24

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