形式语言与自动机理论

2025年07月 的作者和标题

[1] arXiv:2507.00409 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 埃伦伯格的石识别对应关系 显示英文标题

标题： Eilenberg correspondence for Stone recognition

Jorge Almeida, Ondřej Klíma

主题： 形式语言与自动机理论 (cs.FL)

[2] arXiv:2507.01036 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 不可判定性的系统约束 显示英文标题

标题： Systemic Constraints of Undecidability

Seth Bulin

评论： 提交的版本；包含形式定义和结构嵌入的附录。按照《自然计算科学》格式准备。关键词：可计算性理论，不可判定性，因果系统，结构闭包，递归理论，图灵机，超计算，元不可判定性，认识论限制，意识，建模限制

主题： 形式语言与自动机理论 (cs.FL) ; 人工智能 (cs.AI) ; 逻辑 (math.LO)

[3] arXiv:2507.02491 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 工程化一个LTLf合成工具 显示英文标题

标题： Engineering an LTLf Synthesis Tool

Alexandre Duret-Lutz (LRE), Shufang Zhu, Nir Piterman (Chalmers), Giuseppe de Giacomo (UNIROMA), Moshe Y Vardi

期刊参考： 第29届国际自动机实现与应用会议（CIAA'25），2025年9月，意大利巴勒莫

主题： 形式语言与自动机理论 (cs.FL)

[4] arXiv:2507.03439 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 关于无需完全确定化的非确定性有限自动机的补集（技术报告） 显示英文标题

标题： On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)

Lukáš Holík, Ondřej Lengál, Juraj Major, Adéla Štěpková, Jan Strejček

评论： 已被FCT'25接收

主题： 形式语言与自动机理论 (cs.FL) ; 计算机科学中的逻辑 (cs.LO)

[5] arXiv:2507.03465 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 决定有限树和无限字的正则语言的稀疏性 显示英文标题

标题： Deciding Sparseness of Regular Languages of Finite Trees and Infinite Words

Kord Eickmeyer, Georg Schindling

主题： 形式语言与自动机理论 (cs.FL)

[6] arXiv:2507.06472 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 随机对齐：将观察到的轨迹与随机过程模型进行匹配 显示英文标题

标题： Stochastic Alignments: Matching an Observed Trace to Stochastic Process Models

Tian Li, Artem Polyvyanyy, Sander J.J. Leemans

主题： 形式语言与自动机理论 (cs.FL) ; 机器学习 (cs.LG)

[7] arXiv:2507.09373 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 矩阵集的代数闭包由1-VASS识别 显示英文标题

标题： Algebraic Closure of Matrix Sets Recognized by 1-VASS

Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James Worrell

主题： 形式语言与自动机理论 (cs.FL) ; 计算机科学中的逻辑 (cs.LO) ; 代数几何 (math.AG)

[8] arXiv:2507.09761 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 一种用于判断群细胞自动机动力学的分治算法 显示英文标题

标题： A Divide and Conquer Algorithm for Deciding Group Cellular Automata Dynamics

Niccolo' Castronuovo, Alberto Dennunzio, Luciano Margara

主题： 形式语言与自动机理论 (cs.FL) ; 离散数学 (cs.DM)

[9] arXiv:2507.09764 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 基于规则的德布鲁因序列生成：记忆与学习 显示英文标题

标题： Rule-based Generation of de Bruijn Sequences: Memory and Learning

Francisco J. Muñoz, Juan Carlos Nuño

评论： 9页，2图

主题： 形式语言与自动机理论 (cs.FL) ; 动力系统 (math.DS)

[10] arXiv:2507.10980 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 一种概率 Kleene 代数与天使非确定性的判定过程 显示英文标题

标题： A Decision Procedure for Probabilistic Kleene Algebra with Angelic Nondeterminism

Shawn Ong, Dexter Kozen

主题： 形式语言与自动机理论 (cs.FL)

[11] arXiv:2507.11209 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 非确定性2型有限自动机的1限制自动机多项式补集 显示英文标题

标题： Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata

Bruno Guillon, Luca Prigioniero, Javad Taheri

主题： 形式语言与自动机理论 (cs.FL)

[12] arXiv:2507.11873 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 语法修复作为语言交集 显示英文标题

标题： Syntax Repair as Language Intersection

Breandan Considine

主题： 形式语言与自动机理论 (cs.FL) ; 编程语言 (cs.PL)

[13] arXiv:2507.12102 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 超模式匹配 显示英文标题

标题： Hyper pattern matching

Masaki Waga, Étienne André

评论： 这是同名论文的作者（及扩展）版本，该论文已发表在第25届运行时验证国际会议（RV 2025）论文集上

主题： 形式语言与自动机理论 (cs.FL)

[14] arXiv:2507.14082 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 第15届非经典自动机模型与应用国际研讨会论文集 显示英文标题

标题： Proceedings of the 15th International Workshop on Non-Classical Models of Automata and Applications

Nelma Moreira (Universidade do Porto), Luca Prigioniero (Loughborough University)

期刊参考： EPTCS 422，2025

主题： 形式语言与自动机理论 (cs.FL) ; 计算复杂性 (cs.CC)

[15] arXiv:2507.14526 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 研究带有输出延迟的定时有限状态机的归位和同步序列 显示英文标题

标题： Studying homing and synchronizing sequences for Timed Finite State Machines with output delays

Evgenii Vinarskii, Jakub Ruszil, Adam Roman, Natalia Kushik

主题： 形式语言与自动机理论 (cs.FL) ; 计算复杂性 (cs.CC)

[16] arXiv:2507.15310 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 输入驱动的带有透明输入字母的下推自动机 显示英文标题

标题： Input-Driven Pushdown Automata with Translucent Input Letters

Martin Kutrib, Andreas Malcher, Matthias Wendlandt

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025年，第29-43页

主题： 形式语言与自动机理论 (cs.FL)

[17] arXiv:2507.15312 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： Idefix-闭语言及其在上下文文法中的应用 显示英文标题

标题： Idefix-Closed Languages and Their Application in Contextual Grammars

Marvin Ködding, Bianca Truthe

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025，第1-14页

主题： 形式语言与自动机理论 (cs.FL)

[18] arXiv:2507.15313 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 关于Christoffel树的推广：Epichristoffel树 显示英文标题

标题： On a Generalization of the Christoffel Tree: Epichristoffel Trees

Abhishek Krishnamoorthy (Madras Christian College), Robinson Thamburaj (Madras Christian College), Durairaj Gnanaraj Thomas (Madras Christian College)

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025年，第15-28页

主题： 形式语言与自动机理论 (cs.FL)

[19] arXiv:2507.15314 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 由文法系统编排音乐 显示英文标题

标题： Orchestration of Music by Grammar Systems

Jozef Makiš (Faculty of Information Technology, Brno University of Technology), Alexander Meduna (Faculty of Information Technology, Brno University of Technology), Zbyněk Křivka (Faculty of Information Technology, Brno University of Technology)

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025年，第45-58页

主题： 形式语言与自动机理论 (cs.FL)

[20] arXiv:2507.15315 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 关于带有透明词的重复有限自动机 显示英文标题

标题： On Repetitive Finite Automata with Translucent Words

František Mráz (Charles University in Prague), Friedrich Otto (UniversitätKassel)

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025年，第59-72页

主题： 形式语言与自动机理论 (cs.FL)

[21] arXiv:2507.15316 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 一种2detLIN语言的Myhill-Nerode类型特征化 显示英文标题

标题： A Myhill-Nerode Type Characterization of 2detLIN Languages

Benedek Nagy (Eastern Mediterranean University / Eszterházy Károly Catholic University)

评论： 在《NCMA 2025会议论文集》中，arXiv:2507.14082

期刊参考： EPTCS 422，2025年，第73-88页

主题： 形式语言与自动机理论 (cs.FL) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS)

[22] arXiv:2507.15317 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 关于某些可逆双头自动机类别的研究 显示英文标题

标题： On some Classes of Reversible 2-head Automata

Benedek Nagy (Eastern Mediterranean University / Eszterházy Károly Catholic University), Walaa Yasin (Eastern Mediterranean University)

评论： 在NCMA 2025会议论文集，arXiv:2507.14082

期刊参考： EPTCS 422，2025，第89-103页

主题： 形式语言与自动机理论 (cs.FL)

[23] arXiv:2507.15733 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 可到达性理论在轨迹栈系统中 显示英文标题

标题： The theory of reachability in trace-pushdown systems

Dietrich Kuske

主题： 形式语言与自动机理论 (cs.FL)

[24] arXiv:2507.17354 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 可实现性与互补性多参与方会话类型 显示英文标题

标题： Realisability and Complementability of Multiparty Session Types

Cinzia Di Giusto (C and A, I3S), Etienne Lozes (I3S, Laboratoire I3S - COMRED), Pascal Urso (I3S, SCALE, Laboratoire I3S - COMRED)

主题： 形式语言与自动机理论 (cs.FL)

[25] arXiv:2507.17711 (交叉列表自 cs.FL) [中文pdf, pdf, 其他]

标题： 通过仿射向量空间推理随机向量加法系统中的罕见事件可达性 显示英文标题

标题： Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces

Joshua Jeppson, Landon Taylor, Bingqing Hu, Zhen Zhang

主题： 形式语言与自动机理论 (cs.FL)

[26] arXiv:2507.18205 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 静默时间：通过定时自动机中的超时建模静默行为的测试 显示英文标题

标题： Time for Quiescence: Modelling quiescent behaviour in testing via time-outs in timed automata

Laura Brandán Briones, Marcus Gerhold, Petra van den Bos, Mariëlle Stoelinga

主题： 形式语言与自动机理论 (cs.FL)

[27] arXiv:2507.02464 (交叉列表自 cs.GT) [中文pdf, pdf, html, 其他]

标题： 通过自动机理论经济设计解决CAP：实时分区容忍系统统一数学框架 显示英文标题

标题： Resolving CAP Through Automata-Theoretic Economic Design: A Unified Mathematical Framework for Real-Time Partition-Tolerant Systems

Craig S Wright

评论： 51页 4张表格，包括形式化证明、自动机构造和比特币脚本案例研究

主题： 计算机科学与博弈论 (cs.GT) ; 分布式、并行与集群计算 (cs.DC) ; 形式语言与自动机理论 (cs.FL) ; 信息检索 (cs.IR) ; 一般经济学 (econ.GN)

[28] arXiv:2507.02855 (交叉列表自 cs.LO) [中文pdf, pdf, html, 其他]

标题： DHOL中的子类型——扩展预印本 显示英文标题

标题： Subtyping in DHOL -- Extended preprint

Colin Rothgang, Florian Rabe

评论： 16页的主文档，44页的附录，将发表在FroCoS 2025上

主题： 计算机科学中的逻辑 (cs.LO) ; 人工智能 (cs.AI) ; 形式语言与自动机理论 (cs.FL)

[29] arXiv:2507.03629 (交叉列表自 cs.PL) [中文pdf, pdf, html, 其他]

标题： 面向解析表达式的自动错误恢复 显示英文标题

标题： Towards Automatic Error Recovery in Parsing Expression

Sérgio Queiroz de Medeiros, Fabio Mascarenhas

评论： arXiv管理员注释：与arXiv:1905.02145存在大量文本重叠

主题： 编程语言 (cs.PL) ; 形式语言与自动机理论 (cs.FL)

[30] arXiv:2507.04830 (交叉列表自 cs.LO) [中文pdf, pdf, html, 其他]

标题： 关于并发系统运行时验证的注记 显示英文标题

标题： A Note on Runtime Verification of Concurrent Systems

Martin Leucker

评论： 14页，1图

主题： 计算机科学中的逻辑 (cs.LO) ; 形式语言与自动机理论 (cs.FL) ; 软件工程 (cs.SE)

[31] arXiv:2507.06158 (交叉列表自 math.NT) [中文pdf, pdf, html, 其他]

标题： 加法自动机和对应于扩展有理矩阵的数字系统的吸引子 显示英文标题

标题： Addition Automata and Attractors of Digit Systems Corresponding to Expanding Rational Matrices

Anjelo Gabriel R. Cruz, Manuel Joseph C. Loquias, Jörg M. Thuswaldner

评论： 20页，11图

主题： 数论 (math.NT) ; 形式语言与自动机理论 (cs.FL)

[32] arXiv:2507.09387 (交叉列表自 math.CO) [中文pdf, pdf, html, 其他]

标题： 词的因子复杂度$2n+1$和最小临界指数 显示英文标题

标题： Words with factor somplexity $2n+1$ and minimal critical exponent

James D. Currie

主题： 组合数学 (math.CO) ; 形式语言与自动机理论 (cs.FL)

[33] arXiv:2507.10725 (交叉列表自 math.DS) [中文pdf, pdf, html, 其他]

标题： 可计算动力系统中的普遍性：旧的和新的 显示英文标题

标题： Universality in computable dynamical systems: Old and new

Ángel González-Prieto, Eva Miranda, Daniel Peralta-Salas

评论： 31页，5图

主题： 动力系统 (math.DS) ; 形式语言与自动机理论 (cs.FL) ; 微分几何 (math.DG)

[34] arXiv:2507.11126 (交叉列表自 cs.LO) [中文pdf, pdf, 其他]

标题： HOA自动机的执行与监控与HOAX 显示英文标题

标题： Execution and monitoring of HOA automata with HOAX

Luca Di Stefano

评论： 将出现在RV'25中

主题： 计算机科学中的逻辑 (cs.LO) ; 形式语言与自动机理论 (cs.FL)

[35] arXiv:2507.11352 (交叉列表自 cs.AI) [中文pdf, pdf, html, 其他]

标题： 物流的基础模型：面向可认证的、对话式的规划接口 显示英文标题

标题： Foundation Models for Logistics: Toward Certifiable, Conversational Planning Interfaces

Yunhao Yang, Neel P. Bhatt, Christian Ellis, Alvaro Velasquez, Zhangyang Wang, Ufuk Topcu

主题： 人工智能 (cs.AI) ; 形式语言与自动机理论 (cs.FL)

[36] arXiv:2507.13203 (交叉列表自 math.GR) [中文pdf, pdf, 其他]

标题： 关于有限扩张的灯笼工群 显示英文标题

标题： On finite extensions of lamplighter groups

Corentin Bodart

评论： 27页，6张图。v2：删除了最后一个（错误的）评论，并修正了一个参考文献

主题： 群论 (math.GR) ; 离散数学 (cs.DM) ; 形式语言与自动机理论 (cs.FL)

[37] arXiv:2507.15147 (交叉列表自 cs.LO) [中文pdf, pdf, html, 其他]

标题： STL-GO：具有图运算符的时空逻辑用于具有多种网络拓扑的分布式系统 显示英文标题

标题： STL-GO: Spatio-Temporal Logic with Graph Operators for Distributed Systems with Multiple Network Topologies

Yiqi Zhao, Xinyi Yu, Bardh Hoxha, Georgios Fainekos, Jyotirmoy V. Deshmukh, Lars Lindemann

主题： 计算机科学中的逻辑 (cs.LO) ; 形式语言与自动机理论 (cs.FL) ; 多智能体系统 (cs.MA)