Collaborative Research: Piecewise Linear Hybrid Systems

该建议涉及一类称为（离散时间）分段线性（PL）系统的混合系统的有效算法的设计和分析。混杂系统领域涉及到联合收割机离散和连续部件相结合的系统的建模、计算和控制问题。PL系统的子类，我们在这个项目中研究，提供了一个系统的方法来离散时间混杂系统，自然地混合切换机制与经典的线性部件。PL系统作为控制器和识别模型是令人感兴趣的，它们可以被认为是有限自动机和线性系统的任意互连。自动机理论，逻辑和计算机科学和有限数学的相关领域的工具用于PL系统的研究，结合线性代数技术，所有这些都在“PL代数”形式主义的背景下。在这个项目中，我们将研究这些问题的基本算法和计算问题，并将其应用于生物系统的建模。更具体地说，任何一类系统的基本问题都是等价问题，特别是状态空间在变量变化下是否等价。这个项目将解决PL系统的状态空间等价和同构问题相关的各种算法和计算挑战，以及这些系统的可学习性和可表示性的问题。该项目还建议使用PL模型进行差异基因表达测试。

This proposal deals with the design and analysis of efficient algorithms forthe class of hybrid systems called (discrete-time) piecewise linear (PL)systems. The area of hybrid systems concerns issues of modeling, computation andcontrol for systems which combine discrete and continuous components.The subclass of PL systems, which we investigate in this project,provides one systematic approachto discrete-time hybrid systems, naturally blending switching mechanisms withclassical linear components.PL systems are of interest as controllers as well as identification models,and they can be thought of as arbitrary interconnections of finite automataand linear systems. Tools from automata theory, logic and related areas of computerscience and finite mathematics are used in the study of PL systems, inconjunction with linear algebra techniques, all in the context of a ``PLalgebra'' formalism. In this project, we will study basic algorithmicand computational problems for these problems with applications tomodelling of biological systems.More concretely, basic questions for any class of systems are those of equivalence, and, inparticular, whether state spaces are equivalent under a change of variables.This project will address various algorithmic and computational challengesrelated to this state-space equivalence and isomorphism problem for PLsystems, as well as questions of learnability and representability for suchsystems. The project also suggests the use of PL models for differential geneexpression testing.