This book constitutes the research papers presented at the 4th International Workshop, RP 2010 held in Brno, Czech Republic, August 28-29, 2010 and was co-located with Joint MFCS and CSL 2010 (35th International Symposiums on Mathematical Foundations of Computer Science and 19th EACSL Annual Conferences on Computer Science Logic). The revised 9 full papers and the 4 invited talks of this workshop reflect reachability problems that appear in algebraic structures, computational models, hybrid systems and verification. Reachability is a fundamental problem in the context of many models and abstractions which are describing various computational processes. Topics of interest include reachability problems in infinite state systems, rewriting systems, dynamical and hybrid systems, reachability problems in logic and verification, reachability analysis in different computational models, counter, timed, cellular, communicating automata, Petri-Nets, computational aspects of algebraic structures (semigroups, groups and rings), frontiers between decidable and undecidable reachability problems, predictability in iterative maps and new computational paradigms.
Author(s): Markus Holzer, Martin Kutrib (auth.), Antonín Kučera, Igor Potapov (eds.)
Series: Lecture Notes in Computer Science 6227 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 199
Tags: Logics and Meanings of Programs; Software Engineering; Mathematical Logic and Formal Languages; Programming Languages, Compilers, Interpreters; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices
Front Matter....Pages -
Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata....Pages 1-23
Symbolic and Compositional Reachability for Timed Automata....Pages 24-28
Temporal Logics over Linear Time Domains Are in PSPACE....Pages 29-50
Lossy Counter Machines Decidability Cheat Sheet....Pages 51-75
Behavioral Cartography of Timed Automata....Pages 76-90
On the Joint Spectral Radius for Bounded Matrix Languages....Pages 91-103
Z -Reachability Problem for Games on 2-Dimensional Vector Addition Systems with States Is in P ....Pages 104-119
Towards the Frontier between Decidability and Undecidability for Hyperbolic Cellular Automata....Pages 120-132
Rewriting Systems for Reachability in Vector Addition Systems with Pairs....Pages 133-145
The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions....Pages 146-160
Depth Boundedness in Multiset Rewriting Systems with Name Binding....Pages 161-175
Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA....Pages 176-182
Efficient Graph Reachability Query Answering Using Tree Decomposition....Pages 183-197
Back Matter....Pages -
