dorsal/arxiv
View SchemaOn the Computation and Approximation of Backward Reachable Sets for Max-Plus Linear Systems using Polyhedras
| Authors | Yuda Li, Shaoyuan Li, Xiang Yin |
|---|---|
| Categories | |
| ArXiv ID | 2601.10095vv1 |
| URL | https://arxiv.org/abs/2601.10095 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
This paper investigates reachability analysis for max-plus linear systems (MPLS), an important class of dynamical systems that model synchronization and delay phenomena in timed discrete-event systems. We specifically focus on backward reachability analysis, i.e., determining the set of states that can reach a given target set within a certain number of steps. Computing backward reachable sets presents significant challenges due to the non-convexity of max-plus dynamics and the complexity of set complement operations. To address these challenges, we propose a novel approximation framework that efficiently computes backward reachable sets by exploiting the structure of tropical polyhedra. Our approach reformulates the problem as a sequence of symbolic operations and approximates non-convex target sets through closure operations on unions of tropical polyhedra. We develop a systematic algorithm that constructs both outer (M-form) and inner (V-form) representations of the resulting sets, incorporating extremal filtering to reduce computational complexity. The proposed method offers a scalable alternative to traditional DBM-based approaches, enabling reliable approximate backward reachability analysis for general target regions in MPLS.
{
"annotation_id": "ae861e81-efe7-4e71-a156-7e1d24fddef4",
"date_created": "2026-02-17T05:53:23.269000Z",
"date_modified": "2026-02-17T05:53:23.269000Z",
"file_hash": "91f73fefadc62bfa6d3f5b11d66d53ca7acfb320fad6655fe0b487f371616f6d",
"private": false,
"record": {
"abstract": "This paper investigates reachability analysis for max-plus linear systems (MPLS), an important class of dynamical systems that model synchronization and delay phenomena in timed discrete-event systems. We specifically focus on backward reachability analysis, i.e., determining the set of states that can reach a given target set within a certain number of steps. Computing backward reachable sets presents significant challenges due to the non-convexity of max-plus dynamics and the complexity of set complement operations. To address these challenges, we propose a novel approximation framework that efficiently computes backward reachable sets by exploiting the structure of tropical polyhedra. Our approach reformulates the problem as a sequence of symbolic operations and approximates non-convex target sets through closure operations on unions of tropical polyhedra. We develop a systematic algorithm that constructs both outer (M-form) and inner (V-form) representations of the resulting sets, incorporating extremal filtering to reduce computational complexity. The proposed method offers a scalable alternative to traditional DBM-based approaches, enabling reliable approximate backward reachability analysis for general target regions in MPLS.",
"arxiv_id": "2601.10095",
"authors": [
"Yuda Li",
"Shaoyuan Li",
"Xiang Yin"
],
"categories": [
"eess.SY",
"cs.SY"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "On the Computation and Approximation of Backward Reachable Sets for Max-Plus Linear Systems using Polyhedras",
"url": "https://arxiv.org/abs/2601.10095",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "231607a2-c7a5-4647-9a0b-2fc386c8fe05",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}