Formal Languages and Automata Theory

Authors and titles for cs.FL in Feb 2024

[1]  arXiv:2402.00502 [pdf, ps, other]

Title: Axiomatizing NFAs Generated by Regular Grammars

Authors: Roberto Gorrieri

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

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

[2]  arXiv:2402.01372 [pdf, other]

Title: The Freeness Problem for Automaton Semigroups

Authors: Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter

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

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

Title: Backward Responsibility in Transition Systems Using General Power Indices

Authors: Christel Baier, Roxane van den Bossche, Sascha Klüppelholz, Johannes Lehmann, Jakob Piribauer

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

[4]  arXiv:2402.02979 [pdf, other]

Title: Fully Generalized Reactivity(1) Synthesis

Authors: Rüdiger Ehlers, Ayrat Khalimov

Comments: This is an extended version of the paper accepted at TACAS'24

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

[5]  arXiv:2402.04972 [pdf, other]

Title: Distributed Fair Assignment and Rebalancing for Mobility-on-Demand Systems via an Auction-based Method

Authors: Kaier Liang, Cristian-Ioan Vasile

Subjects: Formal Languages and Automata Theory (cs.FL); Computer Science and Game Theory (cs.GT)

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

Title: q-Parikh Matrices and q-deformed binomial coefficients of words

Authors: Antoine Renard, Michel Rigo, Markus A. Whiteland

Comments: 26 pages, submitted

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

[7]  arXiv:2402.05854 [pdf, other]

Title: (Almost) Affine Higher-Order Tree Transducers

Authors: Lê Thành Dũng Tito Nguyên, Gabriele Vanoni

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

[8]  arXiv:2402.06591 [pdf, other]

Title: Random DFA With One Added Transition

Authors: Arnaud Carayol, Philippe Duchon, Florent Koechlin, Cyril Nicaud

Comments: 32 pages, 4 figures, extended version of STACS'2023

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

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

Title: Inform: From Compartmental Models to Stochastic Bounded Counter Machines

Authors: Tim Leys, Guillermo A. Perez

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

[10]  arXiv:2402.09185 [pdf, other]

Title: Flattability of Priority Vector Addition Systems

Authors: Roland Guttenberg

Comments: 24 pages, 2 figures, full version of paper at ICALP 2024

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

[11]  arXiv:2402.10080 [pdf, other]

Title: Temporal hierarchies of regular languages

Authors: Thomas Place, Marc Zeitoun

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

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

Title: Kleene Theorems for Lasso Languages and $ω$-Languages

Authors: Mike Cruchten

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

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

Title: Probabilistic automatic complexity of finite strings

Authors: Kenneth Gill

Comments: 45 pages, 5 figures. This work extends Chapter 2 of the author's PhD dissertation at Penn State

Subjects: Formal Languages and Automata Theory (cs.FL); Logic (math.LO)

[14]  arXiv:2402.13385 [pdf, ps, other]

Title: Regular Languages in the Sliding Window Model

Authors: Moses Ganardi, Danny Hucke, Markus Lohrey, Konstantinos Mamouras, Tatiana Starikovskaya

Comments: arXiv admin note: text overlap with arXiv:1909.10261

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

[15]  arXiv:2402.17000 [pdf, other]

Title: On the Complexity of Initial-and-Final-State Opacity for Discrete Event Systems

Authors: Tomáš Masopust, Petr Osička

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

[16]  arXiv:2402.17015 [pdf, other]

Title: Tree-Verifiable Graph Grammars

Authors: Mark Chimes, Radu Iosif, Florian Zuleger

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

[17]  arXiv:2402.19089 [pdf, ps, other]

Title: Around Don's conjecture for binary completely reachable automata

Authors: Yinfeng Zhu

Comments: 10 pages, 2 figures

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

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

Title: Formal-LLM: Integrating Formal Language and Natural Language for Controllable LLM-based Agents

Authors: Zelong Li, Wenyue Hua, Hao Wang, He Zhu, Yongfeng Zhang

Comments: 21 pages, 6 figures; comments and suggestions are welcome

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL)

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

Title: Bisimulations and Logics for Higher-Dimensional Automata

Authors: Safa Zouari, Krzysztof Ziemianski, Uli Fahrenberg

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

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

Title: $L^*LM$: Learning Automata from Examples using Natural Language Oracles

Authors: Marcell Vazquez-Chanlatte, Karim Elmaaroufi, Stefan J. Witwicki, Sanjit A. Seshia

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL)

[21]  arXiv:2402.07433 (cross-list from cs.DC) [pdf, other]

Title: Logical Synchrony Networks: A formal model for deterministic distribution

Authors: Logan Kenwright, Partha Roop, Nathan Allen, Sanjay Lall, Calin Cascaval, Tammo Spalink, Martin Izzard

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

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

Title: MUSTARD: Mastering Uniform Synthesis of Theorem and Proof Data

Authors: Yinya Huang, Xiaohan Lin, Zhengying Liu, Qingxing Cao, Huajian Xin, Haiming Wang, Zhenguo Li, Linqi Song, Xiaodan Liang

Journal-ref: ICLR 2024 spotlight

Subjects: Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG); Programming Languages (cs.PL)

[23]  arXiv:2402.10013 (cross-list from cs.CL) [pdf, other]

Title: Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length

Authors: Nur Lan, Emmanuel Chemla, Roni Katzir

Comments: 9 pages, 5 figures, 3 appendix pages

Subjects: Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL)

[24]  arXiv:2402.10067 (cross-list from cs.DC) [pdf, other]

Title: LLM-based policy generation for intent-based management of applications

Authors: Kristina Dzeparoska, Jieyu Lin, Ali Tizghadam, Alberto Leon-Garcia

Comments: This article has been accepted for publication in 2023 19th International Conference on Network and Service Management (CNSM), 3rd International Workshop on Analytics for Service and Application Management (AnServApp 2023)

Journal-ref: 2023 19th International Conference on Network and Service Management (CNSM), 2023, pp. 1-7

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL); Human-Computer Interaction (cs.HC); Machine Learning (cs.LG)

[25]  arXiv:2402.10668 (cross-list from eess.SY) [pdf, other]

Title: Data-Driven Abstractions for Control Systems

Authors: Rudi Coppola, Andrea Peruffo, Manuel Mazo Jr

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