paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Minimality Notions via Factorization Systems and Examples

通过因子分解系统与实例的极小性概念
LMCS vol.Volume 18, Issue 32022匹配度 3/10 · 该论文属于纯范畴论/余代数形式语义,研究状态系统最小化的抽象理论,与用户主攻的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接交集。它仅与形式化验证/AI→PL 的底层理论有较弱的间接关联,不构成核心研究方向。引用 0 inbox
Thorsten Wißmann
crossref: 2026-09-10

AI 速览

一句话:在带因子分解系统的范畴中统一刻画余代系统的极小性与最小化,并给出可达性与可观测性最小化及可顺序化条件。

论文研究基于状态的系统最小化,即在不改变语义的前提下减少状态数,并将其分解为删除不必要状态与合并冗余状态两个方面。作者在余代数框架下,于配备因子分解系统的一般范畴中定义抽象的极小性与最小化概念,给出保证最小化唯一性、存在性与函子性的范畴条件。这些结果的证明可实例化为标准余代文献中的可达性最小化与可观测性最小化。最后,文章分析两个最小化方面的交互,并给出它们能以任意顺序复合(如自动机最小化)的判别条件。该更新版修正了图 10 中的错误。

问题
如何在不改变语义的情况下统一理解状态系统的最小化,包括删除不必要状态与合并冗余状态两个方面。
方法
在配备因子分解系统的一般范畴中对余代数定义抽象的极小性与最小化,并给出保证唯一性、存在性和函子性的范畴条件。
评估
通过将证明实例化为标准余代文献中的可达性与可观测性最小化,并分析两个方面能以任意顺序复合的条件(如自动机最小化)来验证理论结果。
原文摘要(Abstract)

For the minimization of state-based systems (i.e. the reduction of the number of states while retaining the system's semantics), there are two obvious aspects: removing unnecessary states of the system and merging redundant states in the system. In the present article, we relate the two minimization aspects on coalgebras by defining an abstract notion of minimality. The abstract notions minimality and minimization live in a general category with a factorization system. We will find criteria on the category that ensure uniqueness, existence, and functoriality of the minimization aspects. The proofs of these results instantiate to those for reachability and observability minimization in the standard coalgebra literature. Finally, we will see how the two aspects of minimization interact and under which criteria they can be sequenced in any order, like in automata minimization. This is an updated version that fixes a mistake in Figure 10

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1655,
  title = {Minimality Notions via Factorization Systems and Examples},
  author = {Thorsten Wißmann},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:31)2022}
}