Towards Selecting the Informative Alternative Relational Query Plans for Database Education
本文提出并解决了面向数据库教育的“信息性计划选择（TIPS）”问题，通过设计具有理论保证的高效近似算法，从海量备选查询计划中筛选出最具代表性的子集，以辅助学习者理解优化器决策并提升教学效果。
💻 Category
cs
5674 篇论文
An Elementary Proof of the FMP for Kleene Algebra
本文通过引入变换自动机表示法，提出了一种不依赖自动机极小化或双模拟的初等证明，确立了 Kleene 代数关于有限关系模型的完备性，从而统一并推广了 Palka 和 Pratt 的相关定理。
Dyck Words, Pattern Avoidance, and Automatic Sequences
本文研究了二进制序列中的 Dyck 词，证明了 $7/32nf(n)$ 的紧确上下界。
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 算法的局限性。
Asynchronous Composition of LTL Properties over Infinite and Finite Traces
本文提出了一种针对通过数据端口交互的异步软件组件的 LTL 属性异步组合方法，该方法利用符号模型检查技术，通过一种新颖的 LTL 重写算法将局部属性转换为全局属性，同时支持无限和有限轨迹语义，并已在 OCRA 工具中实现与验证。
Pattern Avoidance for Fibonacci Sequences using -Regular Words
本文通过简洁证明确立了-正则词中避免特定模式集合的计数分别对应于两类-阶斐波那契递推数列，并提出了关于vincular模式避免数与斐波那契数平方关系的猜想。
Positional -regular languages
本文通过刻画识别位置性语言的奇偶自动机，为-正则语言的位置性提供了完整刻画，从而证明了其判定问题的多项式时间可解性、有限到无限及单玩家到双玩家的提升性质，并证实了前缀独立位置性目标在并运算下的封闭性，解决了 Kopczyński 在-正则情形下的猜想。
Representing Guardedness in Call-by-Value and Guarded Parametrized Monads
本文通过将 Uustalu 的参数化单子推广至 Freyd 范畴，证明了在值调用语言中表示受保护的效应函数空间需要特定的参数化单子，从而将受保护性从范畴上的谓词描述提升为程序的内蕴范畴性质。
Enumeration for MSO-Queries on Compressed Trees
该论文提出了一种针对由直线性程序（SLP）压缩的无秩森林的 MSO 查询枚举算法，仅需线性预处理时间和输出线性延迟，显著提升了压缩数据下的查询效率，并支持对顶点重标号的快速更新。