跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2408.14443 · v3

Ensemble Logic

首次提交 2024-08-27 01:36
版本更新 2026-11-19 20:53
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

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 ∃N ∃n Ψ\exists N\,\exists n\,Ψ 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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 ∃N ∃n Ψ\exists N\,\exists n\,Ψ 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.

查看此版本解读 →查看此版本原文 ↗