paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Reachability in Injective Piecewise Affine Maps

单射分段仿射映射的可达性
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 3/10 · 论文研究单射一维两区间分段仿射映射的可达性判定及相关丢番图与拓扑性质,属于动力系统与自动机理论,与用户关注的 LLM/Agent 与静态分析/形式化验证交叉、浮点程序分析、贝叶斯程序分析没有直接关联,仅与形式化验证的理论基础存在间接联系。引用 1 inbox
Faraz Ghahremani, Edon Kelmendi, Joël Ouaknine
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:证明单射的一维两区间分段仿射映射可达性可判定,并揭示相关问题的丢番图与拓扑性质。

本文研究一维分段仿射映射的可达性问题。该问题在仅有两个区间时长期悬而未决:判定给定轨道是否可达另一状态。作者证明,对于单射分段仿射映射,可达性是可判定的。文章还考察若干相关问题,或给出可判定性结果,或表明它们与某些超越数的丢番图性质密切相关,其形式类似线性递推序列的正性问题。最后,作者研究不限于两个区间的一维分段仿射映射的轨道拓扑性质,并否定回答了 Bournez、Kurganskyy 与 Potapov 关于扩张映射轨道集合的问题。

问题
一维两区间分段仿射映射的可达性是否可判定,是该领域长期未决的基本问题;相关判定问题及轨道拓扑性质也尚不清楚。
方法
证明单射情形下的可判定性;将若干相关问题归约到或联系到特定超越数的丢番图性质,类似线性递推序列正性问题;并分析一般一维分段仿射映射轨道的拓扑性质。
评估
以理论证明为主:给出单射情形的可达性判定定理,对相关问题的可判定性或丢番图联系进行刻画,并否定回答 Bournez 等人关于扩张映射轨道集合的问题。
原文摘要(Abstract)

One of the most basic, longstanding open problems in the theory of dynamical systems is whether reachability is decidable for one-dimensional piecewise affine maps with two intervals. In this paper we prove that for injective maps, it is decidable.We also study various related problems, in each case either establishing decidability, or showing that they are closely connected to Diophantine properties of certain transcendental numbers, analogous to the positivity problem for linear recurrence sequences. Lastly, we consider topological properties of orbits of one-dimensional piecewise affine maps, not necessarily with two intervals, and negatively answer a question of Bournez, Kurganskyy, and Potapov, about the set of orbits in expanding maps.

链接与引用

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

BibTeX
@inproceedings{abs-2301-09752,
  title = {Reachability in Injective Piecewise Affine Maps},
  author = {Faraz Ghahremani and Edon Kelmendi and Joël Ouaknine},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175723}
}