Minimisation questions on semi-linear sets and infinite-state systems

半线性集和无限状态系统的最小化问题

• 批准号: 2436353
• 金额: --
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2436353
• 关键词: Minimisation; questions; semi; linear; sets

Semi-linear sets are a generalisation of ultimately periodic sets of integers to higher dimensions. They appear in a variety of Theoretical Computer Science topics; for instance, the Frobenius coin problem can be interpreted as the problem of finding the largest integer not contained in a given (1-dimensional) semi-linear set of a restricted form. In formal verification, the family of semi-linear sets forms a theoretical basis for a range of verification algorithms, by the virtue of coinciding with the family of sets definable in Presburger arithmetic, the first-order theory of the integers with addition and order. Periodic behaviour in software systems, especially those featuring concurrency, can often be captured by this logic, and then automated decision procedures (such as those implemented in satisfiability modulo theory solvers) pave the way for verification of these systems.Because of the high computational complexity of the underlying decision problems, this approach relies on small representations of inputs. Depending on the exact setup, the semi-linear set may be represented using its generators (explicitly), by a formula in Presburger arithmetic, or even as an automaton or grammar arising as a formal model of a computer program. Succinct representations may, however, bring the complexity further up, which means that a tradeoff needs to be sought. However, for any given representation formalism, this raises the question of minimising representation size.This project looks at minimisation and economy of description questions for semi-linear sets in several key representations, with the goals of finding (1) new characterizations, (2) efficient minimisation procedures, and (3) lower bound arguments. Lower bounds on representation size are of particular interest: for modeling formalisms that involve nondeterministic choice (such as automata, and non-deterministic infinite-state systems more widely) obtaining tight lower bounds on the representation size is a well-known challenge. In the present context, we expect to take advantage of the link to logic and geometry and of the new developments in the understanding of Presburger arithmetic, not explored previously in the context of minimisation and economy of description. We will consider several complexity measures, such as the number of bits and the number of sets in generator representation, the number of states of automata (such as counter automata, register machines, etc.). We will also be able to capitalise on recent advances in the theory of verification of infinite-state systems, such as the nonelementary lower bound for the reachability problem in vector addition systems.

半线性集合是最终周期性整数集合到更高维度的概括。它们出现在各种理论计算机科学主题中。例如，Frobenius硬币问题可以解释为找到在给定（一维）半线性限制形式中未包含的最大整数的问题。在正式验证中，半线性集合的家族构成了一系列验证算法的理论基础，这是由于与Presburger算术中可以定义的集合的家族相吻合，这是整数的一阶理论，即添加和秩序。软件系统中的周期性行为，尤其是具有并发性的人，通常可以被此逻辑捕获，然后可以自动化决策程序（例如在满意度模型理论求解器中实施的程序）为验证这些系统的验证铺平了道路。由于潜在的决策问题的高计算复杂性，这种方法依赖于输入的小代表。根据确切的设置，可以使用其发电机（明确），公式算术中的公式，甚至是作为计算机程序正式模型引起的自动机或语法。但是，简洁的表示可能会进一步提高复杂性，这意味着需要寻求权衡。然而，对于任何给定的形式形式，这提出了最小化表示规模的问题。本项目着眼于在几个关键表示中的半线性集合的最小化和描述问题的经济性问题，其目标是（1）新的特征，（2）有效的最小化程序，以及（3）较低的界限。表示尺寸的下限特别值得注意：用于建模涉及非确定性选择的形式主义（例如自动机和非确定性的无限状态系统），在表示大小上获得紧密的下限是一个众所周知的挑战。在当前情况下，我们希望利用与逻辑和几何形状的链接以及在理解前爆发算术中的新发展的链接，而不是在最小化和描述经济的背景下探索。我们将考虑几种复杂性度量，例如位数量和发电机表示中的集合数，自动机的状态（例如计数器自动机，寄存器等）。我们还将能够利用无限国家系统验证理论的最新进展，例如添加矢量添加系统中可达性问题的非元素下限。