Formal analysis of piecewise affine systems through formula-guided refinement

YORDANOV, Boyan, Jana TŮMOVÁ, Ivana ČERNÁ, Jiří BARNAT and Calin BELTA. Formal analysis of piecewise affine systems through formula-guided refinement. Automatica. Elsevier, 2013, vol. 49, No 1, p. 261-266. ISSN 0005-1098. Available from: https://dx.doi.org/10.1016/j.automatica.2012.09.027.

Basic information

• Original name: Formal analysis of piecewise affine systems through formula-guided refinement
• Authors: YORDANOV, Boyan (100 Bulgaria), Jana TŮMOVÁ (203 Czech Republic, guarantor, belonging to the institution), Ivana ČERNÁ (203 Czech Republic, belonging to the institution), Jiří BARNAT (203 Czech Republic, belonging to the institution) and Calin BELTA (840 United States of America).
• Edition: Automatica, Elsevier, 2013, 0005-1098.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Czech Republic
• Confidentiality degree: is not subject to a state or trade secret
• Impact factor: Impact factor: 3.132
• RIV identification code: RIV/00216224:14330/13:00065966
• Organization unit: Faculty of Informatics
• Doi: http://dx.doi.org/10.1016/j.automatica.2012.09.027
• UT WoS: 000313772600029
• Keywords in English: Piecewise linear analysis; Temporal logic; Verification; Biotechnology
• Tags: International impact, Reviewed

Abstract

We present a computational framework for identifying a set of initial states from which all trajectories of a piecewise affine (PWA) system with additive uncertainty satisfy a linear temporal logic (LTL) formula over a set of linear predicates in its state variables. Our approach is based on the construction and refinement of finite abstractions of infinite systems. We derive conditions guaranteeing the equivalence of an infinite system and its finite abstraction with respect to a specific LTL formula and propose a method for the construction of such formula-equivalent abstractions. While provably correct, the overall method is conservative and expensive. A tool for PWA systems implementing the proposed procedure using polyhedral operations and analysis of finite graphs is made available. Examples illustrating the analysis of PWA models of gene networks are included. (C) 2012 Elsevier Ltd. All rights reserved.

Links

• GAP202/11/0312, research and development project: Name: Vývoj a verifikace softwarových komponent v zapouzdřených systémech (Acronym: Components in Embedded Systems)

Investor: Czech Science Foundation

• GD102/09/H042, research and development project: Name: Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů

Investor: Czech Science Foundation

• LH11065, research and development project: Name: Řízení a ověřování vlastností komplexních hybridních systémů (Acronym: Řízení a ověřování vlastností komplexních hybridní)

Investor: Ministry of Education, Youth and Sports of the CR

• MUNI/A/0758/2011, interní kód MU: Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

• MUNI/A/0760/2012, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)

Investor: Masaryk University, Category A

• MUNI/A/0914/2009, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)

Investor: Masaryk University, Category A