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.