Wed 20 Jun 2018 15:15 - 15:40 at Grand Ballroom AB - Concurrency and Termination Chair(s): Iulian Neamtiu

In 2014, Heizmann et al. proposed a novel framework for program termination analysis. The analysis starts with a termination proof of a sample path. The path is generalized to a Buchi automaton (BA) whose language (by construction) represents a set of terminating paths. All these paths can be safely removed from the program. The removal of paths is done using automata difference, implemented via BA complementation and intersection. The analysis constructs in this way a set of BAs that jointly "cover" the behavior of the program, thus proving its termination. An implementation of the approach in Ultimate Automizer won the 1st place in the Termination category of SV-COMP 2017.

In this paper, we exploit advanced automata-based algorithms and propose several non-trivial improvements of the framework. To alleviate the complementation computation for BAs—one of the most expensive operations in the framework—, we propose a multi-stage generalization construction. We start with generalizations producing subclasses of BAs (such as deterministic BAs) for which efficient complementation algorithms are known, and proceed to more general classes only if necessary. Particularly, we focus on the quite expressive subclass of semideterministic BAs and provide an improved complementation algorithm for this class. Our experimental evaluation shows that the proposed approach significantly improves the power of termination checking within the Ultimate Automizer framework.

Conference Day
Wed 20 Jun

Displayed time zone: Eastern Time (US & Canada) change

14:00 - 15:40
Concurrency and TerminationPLDI Research Papers at Grand Ballroom AB
Chair(s): Iulian NeamtiuNew Jersey Institute of Technology
14:00
25m
Talk
Static Serializability Analysis for Causal Consistency
PLDI Research Papers
Lucas BrutschyETH Zurich, Dimitar DimitrovETH Zurich, Switzerland, Peter MüllerETH Zurich, Martin VechevETH Zürich
14:25
25m
Talk
CUBA: Interprocedural Context-UnBounded Analysis of Concurrent Programs
PLDI Research Papers
Peizun LiuNortheastern University, USA, Thomas WahlNortheastern University
Media Attached
14:50
25m
Talk
Symbolic Reasoning for Automatic Signal Placement
PLDI Research Papers
Kostas FerlesUT Austin, Jacob Van GeffenUT Austin, Isil DilligUT Austin, Yannis SmaragdakisUniversity of Athens
Media Attached
15:15
25m
Talk
Advanced Automata-Based Algorithms for Program Termination Checking
PLDI Research Papers
Yu-Fang Chen, Matthias HeizmannUniversity of Freiburg, Germany, Ondřej LengálBrno University of Technology , Yong LiInstitute of Software, Chinese Academy of Sciences, Ming-Hsien TsaiAcademia Sinica, Taiwan, Andrea TurriniState Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Lijun ZhangInstitute of Software, Chinese Academy of Sciences
Media Attached