Finite abstractions are discrete approximations of dynamical systems, such that the set of abstraction trajectories contains 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 on 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 information theory of lossy compression. Abstractions are viewed as encoder-decoder pairs, encoding trajectories of dynamical systems. Rate measures abstraction size, while distortion describes accuracy, defined as the spatial average deviation between abstract trajectories and system ones. We obtain a fundamental lower bound on the minimum achievable abstraction distortion, given the system dynamics and the abstraction size; and vice-versa a lower bound on the minimum size, for given distortion. The bound depends on the complexity of the dynamics, through trajectory entropy. We demonstrate its tightness on some dynamical systems. Finally, we showcase how this new theory enables constructing minimal abstractions, optimizing the size-accuracy tradeoff, through an example on a chaotic system.

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