Module checking of pushdown multi-agent systems
本文研究了推多代理系统（PMS）的模块检查问题，证明了针对 ATL 规范的检查是 2EXPTIME 完全的，而针对 ATL* 规范的检查则是 4EXPTIME 完全的，后者比前两者在计算复杂度上高出指数级，是少数具有初等但超过三重指数时间复杂度的自然判定问题之一。
💻 Category
cs
8097 篇论文
Probabilistic Counters for Privacy Preserving Data Aggregation
本文从差分隐私角度深入分析了概率计数器（如 Morris 和 MaxGeo 计数器），证明了其内在随机化足以在无需额外噪声的情况下保护隐私，并提出了基于这些计数器的隐私保护数据聚合协议，用于分布式调查并与传统拉普拉斯方法进行了对比。
Homomorphisms of (n,m)-graphs with respect to generalised switch
本文通过提出一种囊括所有已知情形的广义切换操作，以公理化方式系统研究了-图的同态性质，解决了多个长期未决的开放问题，构建了具有反直觉顶点规模的范畴积，并利用群论确定了森林类图的广义切换色数。
Excess demand in public transportation systems: The case of Pittsburgh's Port Authority
该论文针对公交数据中因车辆满载而遗漏的乘客信息（截断数据）会导致需求被低估的问题，提出了一种结合潜在超额需求识别机制与泊松回归模型的框架，并通过模拟验证及在匹兹堡港务局真实数据上的应用，成功实现了对公共交通系统超额需求的准确估算。
Implicit Biases in Refereeing: Lessons from NBA Referees
该研究利用 NBA 比赛数据重新审视了裁判的隐性偏见，发现主客场偏见（尤其是季后赛中）存在但随疫情有所减弱，特定球员确实受益于裁判判罚，但未发现针对特定球员、球队或种族的负面偏见。
Towards Selecting the Informative Alternative Relational Query Plans for Database Education
本文提出并解决了面向数据库教育的“信息性计划选择（TIPS）”问题，通过设计具有理论保证的高效近似算法，从海量备选查询计划中筛选出最具代表性的子集，以辅助学习者理解优化器决策并提升教学效果。
An Elementary Proof of the FMP for Kleene Algebra
本文通过引入变换自动机表示法，提出了一种不依赖自动机极小化或双模拟的初等证明，确立了 Kleene 代数关于有限关系模型的完备性，从而统一并推广了 Palka 和 Pratt 的相关定理。
Dyck Words, Pattern Avoidance, and Automatic Sequences
本文研究了二进制序列中的 Dyck 词，证明了 -无幂二进制词具有有界嵌套深度，刻画了 Thue-Morse 词中 Dyck 因子的特征并给出了计数方法，同时确定了长度为 的 Thue-Morse 词中 Dyck 因子数量 的紧确上下界。
Proving Properties of -Representations with the Walnut Theorem-Prover
本文利用 Walnut 定理证明器，以计算更直接的方式重新证明了 Frougny 和 Sakarovitch 关于-表示自动机的经典定理，并借此统一、简洁地推导出了 Dekking 和 Van Loon 等人的现有成果以及若干新结论。
Universal quantification makes automatic structures hard to decide
本文证明了在自动结构中消除单个全称量词时，最小非确定性有限自动机（NFA）的规模不可避免地会出现双指数级爆炸，且判定该语言是否为空是 EXPSPACE 完全的，从而否定了在受限场景下避免这一复杂度的可能性。
Termination of Graph Transformation Systems via Generalized Weighted Type Graphs
本文通过改进加权类型图技术，增强了其在图终止性证明中的能力，并将其推广至其他范畴及 DPO 变体。
BOPIM: Bayesian Optimization for influence maximization on temporal networks
本文提出了 BOPIM，一种针对时序网络影响力最大化问题的贝叶斯优化算法，通过设计基于汉明距离或杰卡德系数的核函数及改进的采集函数，在显著降低计算成本的同时实现了与黄金标准贪婪算法相当的影响力传播效果，并首次实现了对最优种子集不确定性的量化。
Robustness Over Time: Understanding Adversarial Examples' Effectiveness on Longitudinal Versions of Large Language Models
本文通过对 GPT、Llama 和 Qwen 三大主流大语言模型家族的纵向研究，揭示了模型版本迭代并不总能提升对抗鲁棒性（包括误分类、越狱和幻觉），且更大的模型规模或更新未必能解决现有安全问题，甚至可能加剧某些风险。
Cardinality and Representation of Stone Relation Algebras
本文通过将基数运算公理推广至刻画加权图的斯通关系代数，研究了不同公理间的关系并简化了传统关系代数的公理，同时给出了斯通关系代数的可表示性及其转化为关系代数的充分条件。
Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
本文通过结合 Courcelle 与 Engelfriet 关于树到图定义转换的逻辑刻画，以及 Bojanczyk 与 Pilipczuk 关于最优树宽分解可定义构建的结论，证明了可数单调二阶逻辑（CMSO）可定义且上下文无关的图集等价于具有有界树宽的 HR-代数可识别集、可解析集以及特定定义转换下的可识别无秩树集图像。
Interpolation and the Exchange Rule
该论文通过考察交换律的作用，证明了非交换情形下存在连续统多个具有 amalgamation 性质（对应演绎插值性质）的幂等半线性剩余格变体，而交换情形下则恰好存在六十个此类变体。
Normal Forms for Elements of -Continuous Kleene Algebras Representing the Context-Free Languages
本文通过利用-连续 Kleene 代数与双括号多项式 Kleene 代数张量积中的自动机表示及正规形定理，构建了无需变量绑定器的上下文无关表达式演算基础，并探讨了相关代数结构及其完备性方程。
Minimum Star Partitions of Simple Polygons in Polynomial Time
该论文提出了一种多项式时间算法，解决了简单多边形最小星形划分这一悬置四十余年的开放问题，填补了从禁止 Steiner 点到允许 Steiner 点以及从凸划分到星形划分的研究空白。
Summing the sum of digits
本文通过引用 Mohanty 等人 2023 年关于基因型 - 表型映射最大突变稳健性的定理，重新审视并推广了整数进制下数位和累加函数的不等式，从而推导出了多个已知结论。
Isomorphism for Tournaments of Small Twin Width
本文证明了双宽度有界竞赛图的同构判定可在 时间内完成，从而确立了该类问题的多项式时间可解性，并揭示了竞赛图同构问题在群论方法下的固定参数易解性及其对组合式 Weisfeiler-Leman 算法的局限性。