← 研踪 PaperTrailarXiv:2408.14443 · v3
Ensemble Logic
首次提交 2024-08-27 01:36
版本更新 2026-11-19 20:53
雷达观测 2026-11-20 16:53
摘要
Ensemble Logic (EL) is a family of modal logics whose modal parameters are terms with quantified variables. We interpret formulas over metric monoids, that is, commutative monoids equipped with translation-invariant metrics. Displacement evaluates a formula at a translated point, while bounded existence and bounded universality evaluate it at some or every point of a window of prescribed length. Quantification over points and lengths allows the same variable to occur in the parameters of several operators. This provides a common framework for temporal and spatial reasoning in discrete, dense and multi-dimensional settings. Our main result establishes a sharp undecidability boundary for satisfiability over the natural numbers: satisfiability is undecidable already for formulas in which is built from the letters of a fixed alphabet by conjunction, disjunction, displacement and bounded universality. We prove this by a reduction from Post's Correspondence Problem. We also present results, in part from companion work, that place this theorem in the general theory of EL. These include an atomic-displacement normal form for covariant windows and composition laws for discrete and dense time. The discrete logic admits an embedding of linear temporal logic, defines the accepting runs of every Büchi automaton, and has a sound equational calculus. For the rational logic, we show that every fixed formula can be evaluated in polynomial time on interval models in which atomic propositions are interpreted by finite unions of intervals. Finally, we represent timed words over positions and real time and compare two window geometries; with rectangular windows, two shared lengths yield undecidability on finite timed words.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-19 20:53 · 最新观测版本
Ensemble Logic
Ensemble Logic (EL) is a family of modal logics whose modal parameters are terms with quantified variables. We interpret formulas over metric monoids, that is, commutative monoids equipped with translation-invariant metrics. Displacement evaluates a formula at a translated point, while bounded existence and bounded universality evaluate it at some or every point of a window of prescribed length. Quantification over points and lengths allows the same variable to occur in the parameters of several operators. This provides a common framework for temporal and spatial reasoning in discrete, dense and multi-dimensional settings. Our main result establishes a sharp undecidability boundary for satisfiability over the natural numbers: satisfiability is undecidable already for formulas in which is built from the letters of a fixed alphabet by conjunction, disjunction, displacement and bounded universality. We prove this by a reduction from Post's Correspondence Problem. We also present results, in part from companion work, that place this theorem in the general theory of EL. These include an atomic-displacement normal form for covariant windows and composition laws for discrete and dense time. The discrete logic admits an embedding of linear temporal logic, defines the accepting runs of every Büchi automaton, and has a sound equational calculus. For the rational logic, we show that every fixed formula can be evaluated in polynomial time on interval models in which atomic propositions are interpreted by finite unions of intervals. Finally, we represent timed words over positions and real time and compare two window geometries; with rectangular windows, two shared lengths yield undecidability on finite timed words.
查看此版本解读 →查看此版本原文 ↗