关于一阶级数的尺寸复杂性和可判定性

摘要

12691v1 Announce Type: new Abstract: Progression, the task of updating a knowledge base to reflect action effects, generally requires second-order logic。

the order first action that

2026-05-14 1 阅读约1分钟阅读 Jens Classen, Daxin Liu

arXiv:2605.12691v1 公告类型：new 摘要：进度，更新知识库以反映动作效果的任务，通常需要二阶逻辑。通过限制知识库或动作效果来识别一阶特殊情况，长期以来一直是动作推理的中心主题。众所周知，局部效应、正常和非循环动作这三个表现力日益增强的类别都允许一阶级数。然而，对于实际应用至关重要的对此类级数大小的系统分析却一直缺失。在本文中，使用情境微积分的框架，我们表明在合理的假设下，这些动作类别的一阶级数仅以多项式增长。此外，我们表明，当知识库属于可判定片段（例如二变量一阶逻辑或具有常数的普遍理论）时，级数保持在同一片段内，确保了可判定性和实际适用性。

订阅66必读