Tropical Abstractions of Max-Plus Linear Systems

被引：5

作者：

Mufid, Muhammad Syifa'ul ^{[1
]}

Adzkiya, Dieky ^{[2
]}

Abate, Alessandro ^{[1
]}

机构：

[1] Univ Oxford, Dept Comp Sci, Oxford, England

[2] Inst Teknol Sepuluh Nopember, Dept Math, Surabaya, Indonesia

来源：

FORMAL MODELING AND ANALYSIS OF TIMED SYSTEMS, FORMATS 2018 | 2018年 / 11022卷

关键词：

MPL system; Tropical algebra; Definite form; Difference-bound matrix; Abstraction; Reachability; REACHABILITY ANALYSIS;

D O I：

10.1007/978-3-030-00151-3_16

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper describes the development of finite abstractions of Max-Plus-Linear (MPL) systems using tropical operations. The idea of tropical abstraction is inspired by the fact that an MPL system is a discrete-event model updating its state with operations in the tropical algebra. The abstract model is a finite-state transition system: we show that the abstract states can be generated by operations on the tropical algebra, and that the generation of transitions can be established by tropical multiplications of matrices. The complexity of the algorithms based on tropical algebra is discussed and their performance is tested on a numerical benchmark against an existing alternative abstraction approach.

引用

页码：271 / 287

页数：17

共 50 条

[31] Order-reduction abstractions for safety verification of high-dimensional linear systems
Hoang-Dung Tran
Luan Viet Nguyen
Weiming Xiang
Taylor T. Johnson
Discrete Event Dynamic Systems, 2017, 27 : 443 - 461
[32] Algorithms for exact and approximate linear abstractions of polynomial continuous systems
Boreale, Michele
HSCC 2018: PROCEEDINGS OF THE 21ST INTERNATIONAL CONFERENCE ON HYBRID SYSTEMS: COMPUTATION AND CONTROL (PART OF CPS WEEK), 2018, : 207 - 216
[33] Ultra discrete permanent and the consistency of max plus linear equations
Shinzawa, N.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 506 : 445 - 477
[34] Complete abstractions of dynamical systems by timed automata
Sloth, Christoffer
Wisniewski, Rafael
NONLINEAR ANALYSIS-HYBRID SYSTEMS, 2013, 7 (01) : 80 - 100
[35] Hierarchical Abstractions for Reachability Analysis of Probabilistic Hybrid Systems
Lal, Ratan
Prabhakar, Pavithra
2018 56TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), 2018, : 848 - 855
[36] Basic solutions of systems with two max-linear inequalities
Sergeev, Sergei
Wagneur, Edouard
LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (07) : 1758 - 1768
[37] Conic Abstractions for Hybrid Systems
Bogomolov, Sergiy
Giacobbe, Mirco
Henzinger, Thomas A.
Kong, Hui
FORMAL MODELING AND ANALYSIS OF TIMED SYSTEMS (FORMATS 2017), 2017, 10419 : 116 - 132
[38] Discrete abstractions of hybrid systems
Alur, R
Henzinger, TA
Lafferriere, G
Pappas, GJ
PROCEEDINGS OF THE IEEE, 2000, 88 (07) : 971 - 984
[39] Hybrid abstractions of affine systems
Lefebvre, Marie-Anne
Gueguen, Herve
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 2006, 65 (06) : 1150 - 1167
[40] Lyapunov Abstractions for Inevitability of Hybrid Systems
Duggirala, Parasara Sridhar
Mitra, Sayan
HSCC 12: PROCEEDINGS OF THE 15TH ACM INTERNATIONAL CONFERENCE ON HYBRID SYSTEMS: COMPUTATION AND CONTROL, 2012, : 115 - 123

← 1 2 3 4 5 →