Reachability Problems: 12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings (Lecture Notes in Computer Science, 11123)

This book constitutes the refereed proceedings of the 12th International Conference on Reachability Problems, RP 2018, held in Marseille, France, in September 2018. The 11 full papers presented were carefully reviewed and selected from 21 submissions. The papers cover topics such as reachability for infinite state systems; rewriting systems; reachability analysis in counter/timed/cellular/communicating automata; Petri nets; computational aspects of semigroups, groups, and rings; reachability in dynamical and hybrid systems; frontiers between decidable and undecidable reachability problems; complexity and decidability aspects; predictability in iterative maps, and new computational paradigms. Front Matter ....Pages I-XXI Reachability Analysis of Nonlinear ODEs Using Polytopic Based Validated Runge-Kutta (Julien Alexandre dit Sandretto, Jian Wan)....Pages 1-14 The Satisfiability of Word Equations: Decidable and Undecidable Theories (Joel D. Day, Vijay Ganesh, Paul He, Florin Manea, Dirk Nowotka)....Pages 15-29 Left-Eigenvectors Are Certificates of the Orbit Problem (Steven de Oliveira, Virgile Prevosto, Peter Habermehl, Saddek Bensalem)....Pages 30-44 Constrained Dynamic Tree Networks (Matthew Hague, Vincent Penelle)....Pages 45-58 EXPSPACE-Complete Variant of Countdown Games, and Simulation on Succinct One-Counter Nets (Petr Jančar, Petr Osička, Zdeněk Sawa)....Pages 59-74 Revisiting MU-Puzzle. A Case Study in Finite Countermodels Verification (Alexei Lisitsa)....Pages 75-86 Knapsack in Hyperbolic Groups (Markus Lohrey)....Pages 87-102 Generalized Tag Systems (Turlough Neary, Matthew Cook)....Pages 103-116 Certain Query Answering on Compressed String Patterns: From Streams to Hyperstreams (Iovka Boneva, Joachim Niehren, Momar Sakho)....Pages 117-132 Büchi VASS Recognise \(\mathbf {\Sigma }^{1}_{1}\)-complete \({\omega }\)-languages (Michał Skrzypczak)....Pages 133-145 Qualitative Reachability for Open Interval Markov Chains (Jeremy Sproston)....Pages 146-160 Back Matter ....Pages 161-161 This book constitutes the refereed proceedings of the 7th International Workshop on Reachability Problems, RP 2013, held in Uppsala, Sweden, in September 2013. The 19 revised papers (The 14 revised papers were carefully reviewed and selected from 24 submissions in addition to 5 invited talks) were carefully reviewed and selected from 24 submissions. Topics of interest include reachability for finite state systems; rewriting systems, reachability analysis in counter/timed/cellular/communicating automata; Petri-nets; computational aspects of semigroups, groups and rings; reachability in dynamical and hybrid systems; frontiers between decidable and undecidable reachability problems; complexity and decidability aspects, predictability in iterative maps and new computational paradigms.