Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Low dimensional hybrid sy… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Low dimensional hybrid systems - decidable, undecidable, don't know

Artikel i vetenskaplig tidskrift
Författare E. Asarin
V. P. Mysore
A. Pnueli
Gerardo Schneider
Publicerad i Information and Computation
Volym 211
Sidor 138-159
ISSN 0890-5401
Publiceringsår 2012
Publicerad vid Institutionen för data- och informationsteknik (GU)
Sidor 138-159
Språk en
Länkar dx.doi.org/10.1016/j.ic.2011.11.006
Ämnesord Hybrid systems, Undecidability, Piece-wise affine maps, (Hierarchical), piece-wise constant derivative systems, dynamical-systems, turing-machines, timed automata, maps, computation
Ämneskategorier

Sammanfattning

Even though many attempts have been made to define the boundary between decidable and undecidable hybrid systems, the affair is far from being resolved. More and more low dimensional systems are being shown to be undecidable with respect to reachability, and many open problems in between are being discovered. In this paper, we present various two-dimensional hybrid systems for which the reachability problem is undecidable. We show their undecidability by simulating Minsky machines. Their proximity to the decidability frontier is understood by inspecting the most parsimonious constraints necessary to make reachability over these automata decidable. We also show that for other two-dimensional systems, the reachability question remains unanswered, by proving that it is as hard as the reachability problem for piecewise affine maps on the real line, which is a well known open problem.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?