A new termination analysis approach based on the generation of well-founded transition invariants that leverages Craig interpolation for transition invariant generation, capturing the structural reasons for termination.
Abstract
Termination and nontermination of infinite-state systems are complementary problems that, despite their close connection, are typically addressed by separate techniques. The core idea of this paper is to connect termination and nontermination analysis, enabling the two to share intermediate results and guide one another. We present a new termination analysis approach based on the generation of well-founded transition invariants. It leverages Craig interpolation for transition invariant generation, capturing the structural reasons for termination. The proposed technique extends safety-based nontermination analysis, enabling it to prove both termination and nontermination within a unified framework. We implemented our approach in the GOLEM verification framework and evaluated it on benchmarks from the Termination Competition (TermComp). Empirical results demonstrate that combining termination and nontermination is beneficial and yields performance comparable to state-of-the-art tools.
SMT solvers make automated verification convenient. At the same time, solvers suffer from instability, whereby seemingly inconsequential changes to the input may cause a previously quickly produced proof to fail or time out. This paper addresses a common cause of outcome instability (i.e., unsat/unknown fluctuations) i...
Can Cebeci, Nikolaj S. Bjørner, George Candea et al.· 0 citations
A proof checker called Nörgler is introduced that builds upon and extends the established approach pioneered by GDV and supports checking propositional, (untyped and typed) first-order, and higher-order refutations represented in TSTP.
Melanie Taprogge, H. Sariyanto, Alexander Steen· 1 citation
A QuickCheck testing method based on generating and shrinking random execution traces based on checking if the first and last terms of a generated trace share the same deterministic normal form that efficiently finds counterexamples and enables fast, robust shrinking.
Koen Claessen· Proc. ACM Program. Lang.· 0 citations
The top-down solver TD is a generic fixpoint algorithm that can be used to compute partial post-solutions of equation systems for abstract interpretation. We consider two extensions of the TD to deal with infinite strictly ascending chains. For the TD extended with warrowing, we formally prove that it always returns pa...
Sarah Tilscher, Alexandra Graß, Helmut Seidl et al.· Journal of automated reasoni...· 0 citations
Given the safety-critical nature of many embedded systems, their safety assurance is essential. Because such systems are typically stochastic, probabilistic model checking is a particularly important technique. However, there is a well-known scalability issue due to state-space explosion, especially when verifying comp...
T. Matsumoto, Kazuki Watanabe, Masaki Waga· 0 citations
This work proposes VPID, a multi-agent framework for generating complex Verilog that achieves monotonic functional improvement and introduces an experience-guided refinement strategy that distills historical waveform mismatches into constraints, guiding the targeted debugging for the unverified ports.
Hong-Guang Wang, Jiaming Guo, Rui Zhang et al.· Proceedings of the Thirty-Fi...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
