Foundations of Software Science and Computational Structures : 15th International Conference, FOSSACS 2012, Held As Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 -- April 1, 2012, Proceed

Annotation This book constitutes the proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, held as part of the joint European Conference on Theory and Practice of Software, ETAPS 2012, which took place in Tallinn, Estonia, in March/April 2012. The 29 papers presented in this book together with two invited talks in full paper length were carefully reviewed and selected from 100 full paper submissions. The papers deal with theories and methods to support analysis, synthesis, transformation and verification of programs and software systems Front Matter....Pages - Querying UML Class Diagrams....Pages 1-25 Bicategories of Concurrent Games....Pages 26-41 Fibrational Induction Meets Effects....Pages 42-57 A Coalgebraic Perspective on Minimization and Determinization....Pages 58-73 When Is a Container a Comonad?....Pages 74-88 Well-Pointed Coalgebras (Extended Abstract)....Pages 89-103 Combining Interactive and Automatic Reasoning in First Order Theories of Functional Programs....Pages 104-118 Applicative Bisimulations for Delimited-Control Operators....Pages 119-134 Effective Characterizations of Simple Fragments of Temporal Logic Using Prophetic Automata....Pages 135-149 Improved Ramsey-Based Büchi Complementation....Pages 150-164 Extending ${\cal H}_1$ -Clauses with Path Disequalities....Pages 165-179 Brookes Is Relaxed, Almost!....Pages 180-194 Revisiting Trace and Testing Equivalences for Nondeterministic and Probabilistic Processes....Pages 195-209 Is It a “Good” Encoding of Mixed Choice?....Pages 210-224 Event Structure Semantics of Parallel Extrusion in the Pi-Calculus....Pages 225-239 Narcissists Are Easy, Stepmothers Are Hard....Pages 240-254 On Nominal Regular Languages with Binders....Pages 255-269 Robustness of Structurally Equivalent Concurrent Parity Games....Pages 270-285 Subgame Perfection for Equilibria in Quantitative Reachability Games....Pages 286-300 Concurrent Games with Ordered Objectives....Pages 301-315 Full Abstraction for Set-Based Models of the Symmetric Interaction Combinators....Pages 316-330 On Distributability of Petri Nets....Pages 331-345 Functions as Session-Typed Processes....Pages 346-360 Deriving Bisimulation Congruences for Conditional Reactive Systems....Pages 361-375 First-Order Model Checking on Nested Pushdown Trees is Complete for Doubly Exponential Alternating Time....Pages 376-390 Model Checking Languages of Data Words....Pages 391-405 Branching-Time Model Checking of Parametric One-Counter Automata....Pages 406-420 Synthesizing Probabilistic Composers....Pages 421-436 On the Complexity of Computing Probabilistic Bisimilarity....Pages 437-451 Probabilistic Transition System Specification: Congruence and Full Abstraction of Bisimulation....Pages 452-466 On the Complexity of the Equivalence Problem for Probabilistic Automata....Pages 467-481 Back Matter....Pages -