形式语言与自动机理论

2025年10月 的作者和标题

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

标题： MightyPPL：带有过去和Pnueli模态的MITL验证 显示英文标题

标题： MightyPPL: Verification of MITL with Past and Pnueli Modalities

Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya

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

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

标题： 迭代非聚合结构组合 显示英文标题

标题： Iterating Non-Aggregative Structure Compositions

Marius Bozga, Radu Iosif, Florian Zuleger

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

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

标题： 低自动复杂度词语的语言很难计算 显示英文标题

标题： Languages of Words of Low Automatic Complexity Are Hard to Compute

Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara, Linus Richter, Frank Stephan

评论： 22页，1图

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

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

标题： 关于概率词语言成员关系的复杂性 显示英文标题

标题： On the Complexity of Language Membership for Probabilistic Words

Antoine Amarilli, Mikaël Monet, Paul Raphaël, Sylvain Salvati

评论： 35页，包括1页标题页、15页正文、4页参考文献和附录

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

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

标题： 三步数常数和有限自动机 显示英文标题

标题： The Tribonacci constant and finite automata

Jeffrey Shallit

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

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

标题： 将代数分层分解带入连接式函数语言 显示英文标题

标题： Bringing Algebraic Hierarchical Decompositions to Concatenative Functional Languages

Attila Egri-Nagy

评论： 7页，6图，最终版本将在其他地方发表

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

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

标题： 可判定性与群细胞自动机扩张性的表征 显示英文标题

标题： Decidability and Characterization of Expansivity for Group Cellular Automata

Niccolo' Castronuovo, Alberto Dennunzio, Luciano Margara

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

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

标题： 在逐点语义下对过去度量时间性质的高效验证 显示英文标题

标题： Efficient Verification of Metric Temporal Properties with Past in Pointwise Semantics

S. Akshay, Prerak Contractor, Paul Gastin, R. Govind, B. Srivathsan

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

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

标题： 关于惰性细胞自动机的顺序 显示英文标题

标题： On the order of lazy cellular automata

Edgar Alcalá-Arroyo, Alonso Castillo-Ramirez

评论： 12页

主题： 形式语言与自动机理论 (cs.FL) ; 动力系统 (math.DS) ; 群论 (math.GR) ; 细胞自动机与格子气体 (nlin.CG)

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

标题： 通过Q学习推断确定性有限自动机 显示英文标题

标题： Inference of Deterministic Finite Automata via Q-Learning

Elaheh Hosseinkhani, Martin Leucker

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

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

标题： Castor Ministerialis 显示英文标题

标题： Castor Ministerialis

Christian Hercher

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

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

标题： 有界标记Petri网的非干扰性分析 显示英文标题

标题： Non-interference analysis of bounded labeled Petri nets

Ning Ran, Zhengguang Wu, Shaokang Zhang, Zhou He, Carla Seatzu

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

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

标题： 图灵机计算原始递归函数的特征 显示英文标题

标题： A Characterization of Turing Machines that Compute Primitive Recursive Functions

Daniel G. Schwartz

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

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

标题： 随机语言在次随机成本下 显示英文标题

标题： Stochastic Languages at Sub-stochastic Cost

Smayan Agarwal, Aalok Thakkar

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

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

标题： 变压器本质上是简洁的 显示英文标题

标题： Transformers are Inherently Succinct

Pascal Bergsträßer, Ryan Cotterell, Anthony W. Lin

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

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

标题： 高斯整数的科布姆定理 显示英文标题

标题： Cobham's theorem for the Gaussian integers

Álvaro Bustos-Gajardo, Robbert Fokkink, Reem Yassawi

评论： 15页，2图

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

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

标题： 解析语法：语言模型如何学习上下文无关文法 显示英文标题

标题： Unraveling Syntax: How Language Models Learn Context-Free Grammars

Laura Ying Schulz, Daniel Mitropolsky, Tomaso Poggio

评论： LYS和DM共同贡献

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

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

标题： 共同达成：种群如何在重复博弈中获胜 显示英文标题

标题： Reach together: How populations win repeated games

Nathalie Bertrand, Patricia Bouyer, Luc Lapointe, Corto Mascle

主题： 计算机科学与博弈论 (cs.GT) ; 形式语言与自动机理论 (cs.FL)

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

标题： 实用通信系统子类中的不可靠性 显示英文标题

标题： Unreliability in Practical Subclasses of Communicating Systems

Amrita Suresh, Nobuko Yoshida

评论： 同一标题的论文全文发表于FSTTCS'25会议论文集

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

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

标题： 图数据库和自动结构中的同态问题 显示英文标题

标题： Homomorphism Problems in Graph Databases and Automatic Structures

Rémi Morvan

评论： 博士论文，法语语言，于2025年7月3日在波尔多大学答辩

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

[21] arXiv:2510.08342 (交叉列表自 nlin.CG) [中文pdf, pdf, html, 其他]

标题： 自复制与计算普遍性 显示英文标题

标题： Self-replication and Computational Universality

Jordan Cotler, Clément Hongler, Barbora Hudcová

评论： 9+67页，32图

主题： 细胞自动机与格子气体 (nlin.CG) ; 形式语言与自动机理论 (cs.FL) ; 适应性与自组织系统 (nlin.AO)

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

标题： Psi图灵机：复杂性障碍和预言机分离的有界内省 显示英文标题

标题： Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations

Rafig Huseynzade

评论： 60页，6个图。包含Lean和Isabelle中的双重形式化，一个零风险图附录，以及基于CI的压力测试；规范陈述已修复；备选方案已记录。补充代码和脚本：https://github.com/Acloyer/Psi-TM

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

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

标题： MASA：用于自动形式化的LLM驱动的多智能体系统 显示英文标题

标题： MASA: LLM-Driven Multi-Agent Systems for Autoformalization

Lan Zhang, Marco Valentino, André Freitas

评论： EMNLP 2025 展示版已定稿。代码和数据可在以下链接获取：https://github.com/lanzhang128/multi_agent_autoformalization

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

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

标题： RegexPSPACE：一种用于评估大语言模型在PSPACE完全正则表达式问题上的推理能力的基准 显示英文标题

标题： RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems

Hyundong Jin, Joonghyuk Hahn, Yo-Sub Han

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

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

标题： 摘要 用字方程定义的字符串域作为约简乘积（扩展版本） 显示英文标题

标题： Abstract String Domain Defined with Word Equations as a Reduced Product (Extended Version)

Antonina Nepeivoda, Ilya Afanasyev

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

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

标题： 关于 Kimberling 的一个序列及其与 Tribonacci 字的关联 显示英文标题

标题： On a sequence of Kimberling and its relationship to the Tribonacci word

Lubomíra Dvořáková, Edita Pelantová, Jeffrey Shallit

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

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

标题： 超逻辑中的量词类型 显示英文标题

标题： Flavors of Quantifiers in Hyperlogics

Marek Chalupa, Thomas A. Henzinger, Ana Oliveira da Costa

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

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

标题： 带有运行时监控语言的表达奖励合成 显示英文标题

标题： Expressive Reward Synthesis with the Runtime Monitoring Language

Daniel Donnelly, Angelo Ferrando, Francesco Belardinelli

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

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

标题： 多头有限状态压缩 显示英文标题

标题： Multihead Finite-State Compression

Neil Lutz

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

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

标题： ZipLex：带记忆导数和Zippers的可逆词法分析验证 显示英文标题

标题： ZipLex: Verified Invertible Lexing with Memoized Derivatives and Zippers

Samuel Chassot, Viktor Kunčak

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

[31] arXiv:2510.20692 (交叉列表自 cs.SE) [中文pdf, pdf, html, 其他]

标题： 探索大型语言模型在访问控制策略合成和总结中的应用 显示英文标题

标题： Exploring Large Language Models for Access Control Policy Synthesis and Summarization

Adarsh Vatsa, Bethel Hall, William Eiers

评论： 20页，7图

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