Finite abstractions are discrete approximations of dynamical systems, such that the set of abstraction trajectories contains, in a formal sense, all system trajectories. There is a consensus that abstractions suffer from the curse of dimensionality: for the same ``accuracy" (how closely the abstraction represents the system), the abstraction size scales poorly with system dimensions. And, yet, after decades of research on abstractions, there are no formal results concerning their accuracy-size tradeoff. In this work, we derive a statistical, quantitative theory of abstractions' accuracy-size tradeoff and uncover fundamental limits on their scalability, through rate-distortion theory -- the branch of information theory studying lossy compression. Abstractions are viewed as encoder-decoder pairs, encoding trajectories of dynamical systems in a higher-dimensional ambient space. Rate represents abstraction size, while distortion describes abstraction accuracy, defined as the spatial average deviation between abstract trajectories and system ones. We obtain a fundamental lower bound on the minimum abstraction distortion, given the system dynamics and a threshold on abstraction size. The bound depends on the complexity of the dynamics, through generalized entropy. We demonstrate the bound's tightness on certain dynamical systems. Finally, we showcase how the developed theory can be employed to construct optimal abstractions, in terms of the size-accuracy tradeoff, through an example on a chaotic system.

翻译：有限抽象是动力系统的离散近似，其抽象轨迹集合在形式意义上包含所有系统轨迹。学界普遍认为抽象存在维度灾难：在相同“精度”（抽象表示系统的接近程度）下，抽象规模随系统维度增长而急剧劣化。然而，经过数十年的抽象研究，关于其精度-规模权衡仍缺乏形式化结论。本研究通过率失真理论——信息论中研究有损压缩的分支——推导出抽象精度-规模权衡的统计量化理论，并揭示其可扩展性的基本极限。抽象被视为编码器-解码器对，用于编码高维环境空间中的动力系统轨迹。率代表抽象规模，失真描述抽象精度，定义为抽象轨迹与系统轨迹间空间平均偏差。在给定系统动力学和抽象规模阈值条件下，我们获得了最小抽象失真的基本下界。该下界通过广义熵依赖于动力学复杂性。我们在特定动力系统上证明了该下界的紧致性。最后，通过混沌系统示例，展示了如何运用该理论构建精度-规模权衡意义下的最优抽象。