Reachability problems for systems with linear dynamics
Reachability problems for systems with linear dynamics
复制标题
线性动力学系统的可达性问题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shang Chen
中科院分区：
文献类型：
--
作者：
Shang Chen
本文研究线性动态系统的可达性和自由度问题，包括混杂系统和矩阵半群。混杂系统是一类同时具有连续和离散动态特性的动态系统。因此，他们是特别有用的，在模拟实际的真实的世界系统，既可以流动（连续行为）和跳跃（离散行为）。矩阵半群的决策问题在数学界和理论计算机科学界都引起了极大的关注。它们也可用于仅使用分立元件的应用建模。
对于一个计算模型，可达性问题问的是我们是否可以从一个初始点开始到达一个目标点，这在理论研究和现实世界的应用中都是一个自然的问题。通过研究这个问题及其变化，我们将在形式数学意义上证明许多问题是难以解决的，甚至是无法解决的。因此，我们知道当这样的问题出现在其他领域，如生物学，物理学或化学，要么问题本身需要简化，要么应该通过近似来研究。
在这篇论文中，我们集中在一个特定的混合系统模型，称为HPCD，和它的变化。研究这个模型的目的是双重的：获得最有表现力的系统，可达性是算法可解的，并探索最简单的系统，它是不可能解决的。对于可解的子情形，我们还将通过确定问题属于哪种复杂性类（如P、NP（-hard）和PSPACE（-hard））来研究可达性在某种意义上是容易还是困难。同时给出了矩阵半群的一些不可判定性结果，这些结果既加强了我们对矩阵半群结构的认识，又引出了其它模型的一些不可判定性结果。
This thesis deals with reachability and freeness problems for systems with linear dynamics, including hybrid systems and matrix semigroups. Hybrid systems are a type of dynamical system that exhibit both continuous and discrete dynamic behaviour. Thus they are particularly useful in modelling practical real world systems which can both flow (continuous behaviour) and jump (discrete behaviour). Decision questions for matrix semigroups have attracted a great deal of attention in both the Mathematics and Theoretical Computer Science communities. They can also be used to model applications with only discrete components.
For a computational model, the reachability problem asks whether we can reach a target point starting from an initial point, which is a natural question both in theoretical study and for real-world applications. By studying this problem and its variations, we shall prove in a formal mathematical sense that many problems are intractable or even unsolvable. Thus we know when such a problem appears in other areas like Biology, Physics or Chemistry, either the problem itself needs to be simplified, or it should by studied by approximation.
In this thesis we concentrate on a specific hybrid system model, called an HPCD, and its variations. The objective of studying this model is twofold: to obtain the most expressive system for which reachability is algorithmically solvable and to explore the simplest system for which it is impossible to solve. For the solvable sub-cases, we shall also study whether reachability is in some sense easy or hard by determining which complexity classes the problem belongs to, such as P, NP(-hard) and PSPACE(-hard). Some undecidable results for matrix semigroups are also shown, which both strengthen our knowledge of the structure of matrix semigroups, and lead to some undecidability results for other models.