Benchmark

non-incremental/QF_NRA/20240407-pPDA-Chiari-Pontiggia-Winkler/past/geom_offspring_0.499_PRAY.smt2

Publications:
  [1] Tobias Winkler, Joost-Pieter Katoen:
On Certificates, Expected Runtimes, and Termination in Probabilistic Pushdown Automata. LICS 2023: 1-13

This benchmark encodes positive almost sure termination (PAST; termination in finite expected time) of the probabilistic recursive program given below. The program model a process P that spawns a random number of copies of itself; the number of copies is geometrically distributed.
The program was automatically translated to a probabilistic pushdown automaton (pPDA) using the PRAY tool. The SMT formula results from applying Theorem 8 from [1]. The SMT formula is SAT iff the program is PAST.

void P() {
    while flip(499//1000) {
        P();
    }
}

P(); # entry point

Benchmark
Size	4987
Compressed Size	1189
License	Creative Commons Attribution 4.0 International (CC-BY-4.0)
Category	industrial
First Occurrence	2024-07-22
Generated By	Tobias Winkler
Generated On	2024-04-07 00:00:00
Generator	PRAY - Probabilistic Recursion Analyzer (https://doi.org/10.5281/zenodo.7506305)
Dolmen OK	1
strict Dolmen OK	1
check-sat calls	1

Query 1

Status	sat
Inferred Status	sat
Size	4979
Compressed Size	1187
Max. Term Depth	4
Asserts	58
Declared Functions	0
Declared Constants	29
Declared Sorts	0
Defined Functions	0
Defined Recursive Functions	0
Defined Sorts	0
Constants	0
Declared Datatypes	0

Symbols

/

24

+

29

*

36

>=

58

Evaluations

Evaluation	Rating	Solver	Variant	Result	Wallclock	CPU Time
SMT-COMP 2024	0.20 (4/5)	cvc5	cvc5	sat ✅	0.29215	0.19249
		SMTInterpol	SMTInterpol	unknown ❌	0.46284	0.53315
		SMT-RAT	SMT-RAT	sat ✅	0.63714	0.53746
		Yices2	Yices2	sat ✅	0.22675	0.12693
		Z3alpha	Z3-alpha	sat ✅	0.26866	0.16907
SMT-COMP 2025	0.17 (5/6)	cvc5	cvc5	sat ✅	0.33937	0.20978
		SMTInterpol	SMTInterpol	unknown ❌	0.49170	0.54857
		SMT-RAT	SMT-RAT	sat ✅	0.32755	0.20401
		Yices2	Yices2	sat ✅	0.27698	0.15601
		Z3alpha	Z3-alpha	sat ✅	0.61686	0.51189
		Z3	Z3-alpha-base	sat ✅	0.27790	0.15754
			z3siri-base	sat ✅	0.26863	0.15007