Deciding Reachability for 3-Dimensional Multi-Linear Systems

Autor:	Tveretina, Olga, Funke, Daniel
Rok vydání:	2011
Předmět:	Computer Science - Logic in Computer Science
Zdroj:	EPTCS 54, 2011, pp. 250-262
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.54.18
Popis:	This paper deals with the problem of point-to-point reachability in multi-linear systems. These systems consist of a partition of the Euclidean space into a finite number of regions and a constant derivative assigned to each region in the partition, which governs the dynamical behavior of the system within it. The reachability problem for multi-linear systems has been proven to be decidable for the two-dimensional case and undecidable for the dimension three and higher. Multi-linear systems however exhibit certain properties that make them very suitable for topological analysis. We prove that reachability can be decided exactly in the 3-dimensional case when systems satisfy certain conditions. We show with experiments that our approach can be orders of magnitude more efficient than simulation. Comment: In Proceedings GandALF 2011, arXiv:1106.0814
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1106.1245 Zobrazit plný text záznamu View this record from Arxiv