Formal Languages and Automata Theory

Authors and titles for cs.FL in Mar 2024

[1]  arXiv:2403.02019 [pdf, other]

Title: Active Learning of Mealy Machines with Timers

Authors: Véronique Bruyère, Bharat Garhewal, Guillermo A. Pérez, Gaëtan Staquet, Frits W. Vaandrager

Comments: 77 pages, 19 figures

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

[2]  arXiv:2403.03057 [pdf, other]

Title: Efficient Interaction-Based Offline Runtime Verification of Distributed Systems with Lifeline Removal

Authors: Erwan Mahe, Boutheina Bannour, Christophe Gaston, Pascale Le Gall

Comments: 38 pages (31 in the article proper, 1 page of references, 6 pages in appendices), 18 figures, submitted to Science of Computer Programming journal

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

[3]  arXiv:2403.03067 [pdf, other]

Title: Enumeration for MSO-Queries on Compressed Trees

Authors: Markus Lohrey, Markus L. Schmid

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

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

Title: Characterizations of Controlled Generation of Right Linear Grammars with Unknown Behaviors

Authors: Daihei Ise, Satoshi Kobayashi

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

[5]  arXiv:2403.05088 [pdf, other]

Title: Semidirect Product Decompositions for Periodic Regular Languages

Authors: Yusuke Inoue, Kenji Hashimoto, Hiroyuki Seki

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

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

Title: On Graph Grammars and Games

Authors: Jayakrishna Vijayakumar, Lisa Mathew

Comments: 14 pages, 10 figures

Subjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[7]  arXiv:2403.15899 [pdf, ps, other]

Title: A short survey around the pumping lemma for context-free languages

Authors: Gabriele Gullà

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

[8]  arXiv:2403.16626 [pdf, ps, other]

Title: Presenting Interval Pomsets with Interfaces

Authors: Amazigh Amrane, Hugo Bazille, Emily Clement, Uli Fahrenberg, Krzysztof Ziemianski

Comments: Submitted to RAMICS 2024, 16 pages + reference

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

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

Title: Logic and Languages of Higher-Dimensional Automata

Authors: Amazigh Amrane, Hugo Bazille, Uli Fahrenberg, Marie Fortin

Comments: Submission to DLT24, 12 pages + references + appendix

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

[10]  arXiv:2403.00169 (cross-list from cs.LO) [pdf, other]

Title: Quantitative Assurance and Synthesis of Controllers from Activity Diagrams

Authors: Kangfeng Ye, Fang Yan, Simos Gerasimou

Comments: 43 pages, 29 figures, 5 tables, submitted to Journal of Systems and Software (JSS)

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

[11]  arXiv:2403.01632 (cross-list from cs.LG) [pdf, other]

Title: SynCode: LLM Generation with Grammar Augmentation

Authors: Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, Gagandeep Singh

Subjects: Machine Learning (cs.LG); Formal Languages and Automata Theory (cs.FL); Programming Languages (cs.PL); Software Engineering (cs.SE)

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

Title: Unknown Biases and Timing Constraints in Timed Automata

Authors: Darion Haase, Joost-Pieter Katoen

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

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

Title: Robust MITL planning under uncertain navigation times

Authors: Alexis Linard, Anna Gautier, Daniel Duberg, Jana Tumova

Comments: ICRA 2024

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

[14]  arXiv:2403.04777 (cross-list from cs.DM) [pdf, other]

Title: Specifying and Verifying the Convergence Stairs of the Collatz Program

Authors: Ali Ebnenasir

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

[15]  arXiv:2403.08707 (cross-list from cs.DS) [pdf, ps, other]

Title: Improved Randomized Approximation of Hard Universality and Emptiness Problems

Authors: Pantelis Andreou, Stavros Konstantinidis, Taylor J. Smith

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

[16]  arXiv:2403.09145 (cross-list from cs.CC) [pdf, ps, other]

Title: Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems

Authors: Tomoyuki Yamakami

Comments: (A4, 10pt, 17 pages) An extended abstract of this current article is scheduled to appear in the Proceedings of the 12th Computing Conference, London, UK, July 11--12, 2024, Lecture Notes in Networks and Systems, Springer-Verlag, 2024

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

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

Title: Preference-Based Planning in Stochastic Environments: From Partially-Ordered Temporal Goals to Most Preferred Policies

Authors: Hazhar Rahmani, Abhishek N. Kulkarni, Jie Fu

Comments: arXiv admin note: substantial text overlap with arXiv:2209.12267

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

[18]  arXiv:2403.11148 (cross-list from math.GR) [pdf, ps, other]

Title: The word problem and growth of groups

Authors: Ievgen Bondarenko

Comments: 14 pages

Subjects: Group Theory (math.GR); Formal Languages and Automata Theory (cs.FL)