TACAS 2018, the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems took place in Thessaloniki, Greece on April 16–20, 2018, as part of the European Joint Conferences on Theory and Practice of Software (ETAPS). TACAS is a forum for researchers, developers, and users interested in rigorously based tools and algorithms for the construction and analysis of systems. The conference aims to bridge the gaps between different communities with this common interest and to support them in their quest to improve the utility, reliability, flexibility, and efficiency of tools and algorithms for building systems.
This special issue of the Journal of Automated Reasoning contains revised and extended versions of seven papers selected out of 45 papers presented at the conference. The papers that were selected for this special issue all provide new theoretical contributions to the construction and analysis of systems. In addition to this special issue, a companion special issue for TACAS 2018 appears in the journal Software Tools for Technology Transfer (STTT), containing selected papers that report on advances in tools and tool sets in this area. All selected papers underwent a thorough reviewing process, with several iterations, where each paper was reviewed by several external domain experts. As a result of this selection process, this special issue contains the following papers.
Anzeige
Kshitij Bansal, Eric Koskinen, and Omer Tripp propose an algorithm to reason automatically about commutativity (and non-commutativity) conditions for method pairs in a parallel context. They illustrate their approach by synthesizing commutativity conditions for several widely used data structures.
Randal E. Bryant introduces chain reduction to enable reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the others’ ability to symbolically represent Boolean functions in a compact form. He proposes extensions to the standard algorithms for operating on BDDs and ZDDs that enable them to operate on the chain-reduced versions.
Adrien Champion, Tomoya Chiba, Naoki Kobayashi, and Ryosuke Sato propose an extension of the ICE framework for automatically finding refinement types of higher-order function programs. The key idea of their approach is that the generated implication constraints can be generalized to find invariants of recursive functions with multiple function calls.
Peter Chini, Roland Meyer, and Prakash Saivasan study the fine-grained complexity of Leader Contributor Reachability (LCR) and Bounded-Stage Reachability (BSR), two variants of the safety-verification problem for shared-memory concurrent programs, for which they provide new verification algorithms and lower bounds.
Anzeige
Gabriele Costa, Letterio Galletta, Pierpaolo Degano, David Basin, and Chiara Bodei consider the problem of specification decomposition. They consider two different approaches: natural projection and partial model checking, used in different communities, and they show that under certain conditions they are equivalent, building a bridge between the control-theory community and the verification community.
Arnd Hartmanns, Sebastian Junges, Joost-Pieter Katoen, and Tim Quatmann provide a memory-efficient algorithm for multi-objective model-checking problems on Markov decision processes (MDP) with multiple cost structures. The key contribution is that the algorithm can check whether there exists a scheduler for a given MDP such that all objectives over cost vectors are fulfilled.
Daniel Neider, P. Madhusudan, Shambwaditya Saha, Pranav Garg, and Daejun Park propose a framework for synthesizing inductive invariants for incomplete verification engines. Their approach is based on the counter-example guided inductive-synthesis principle, which allows verification engines to communicate non-provability information to guide invariant synthesis.
Finally, we would like to thank all authors and reviewers. All reviewers carefully read the papers and provided constructive feedback to improve the papers. This feedback was carefully taken into account by the authors. This special issue would not have been possible without their efforts.
Guest Editors
Dirk Beyer and Marieke Huisman
LMU Munich and University of Twente
Acknowledgements
Open Access funding provided by Projekt DEAL.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.