Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
本文从形式语言理论的角度重新审视 Emil Post 提出的“生产性集合”(productive set) 概念，并据此构造出本质上不可判定的形式文法。背景上，Post 证明存在这样一类自然数集合：它们不是递归可枚举的，甚至连半可计算都做不
#cs.FL
共收录 5 条相关情报。
← 返回所有主题Verification of $K$- and Infinite-Step Strong/Weak Anonymity Using Concurrent Compositions
本文研究部分可观测离散事件系统中的匿名性验证问题。匿名性是一种信息流安全属性，其核心思想是：在外部观察者通过系统输出（观测）推断系统内部状态时，系统不应让某一时刻的状态被唯一确定，从而保护用户隐私。在离散事件系统框架下，已有 K-步匿名性和
Synthesizing Probabilistic Saturating Counters with Differentially Private Formal Guarantees
现代处理器的分支预测器利用饱和计数器来提升指令级并行性，但传统饱和计数器是确定性的，容易受到侧信道攻击：攻击者可通过操作计数器状态并观察缓存行为（如Prime+Probe）推断受害进程的分支方向。为缓解该泄漏，已有研究提出概率饱和计数器（P
Right Divisibility in Erasing Semi-Thue Systems: A Minimal View of Intruder Deduction
本文研究符号安全协议分析中的入侵者推导问题，即判断攻击者能否利用其掌握的操作从已观测消息中推导出目标消息。尽管收敛重写系统能够提供规范形式，但模收敛理论的推导一般不可判定，现有可判定片段多由实际密码学示例驱动。本文从最小结构视角出发：当所有
Layer Order Semantics for Automata-Based Cybersecurity
本文提出了一种基于自动机理论的形式化框架，用于分析和理解分层网络安全流水线中顺序敏感的安全故障。当前网络安全架构通常采用多阶段流水线来处理证据并做出决策，但不同阶段的转换顺序会显著影响哪些安全事实被暴露给哪些层级。作者给出了层顺序的有限状态