Benchmark

non-incremental/QF_NRA/20240407-pPDA-Chiari-Pontiggia-Winkler/past/and_or_PRAY.smt2

Publications:
  [1] Tobias Winkler, Joost-Pieter Katoen:
On Certificates, Expected Runtimes, and Termination in Probabilistic Pushdown Automata. LICS 2023: 1-13
  [2] Tomás Brázdil, Stefan Kiefer, Antonín Kucera, Ivana Hutarová Vareková:
Runtime analysis of probabilistic programs with unbounded recursion. J. Comput. Syst. Sci. 81(1): 288-310 (2015)

This benchmark encodes positive almost sure termination (PAST; termination in finite expected time) of the probabilistic recursive program given below. The program is taken from [2].
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.

bool and() {
  prob {
    1//2: return flip(1//2);
    1//2: {
      if(!or()) return false;
      else return or();
    }
  }
}

bool or() {
  prob {
    1//2: return flip(1//2);
    1//2: {
      if(and()) return true;
      else return and();
    }
  }
}

and(); # entry point

Benchmark
Size	34026
Compressed Size	4970
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	unknown
Inferred Status	None
Size	34018
Compressed Size	4983
Max. Term Depth	4
Asserts	516
Declared Functions	0
Declared Constants	258
Declared Sorts	0
Defined Functions	0
Defined Recursive Functions	0
Defined Sorts	0
Constants	0
Declared Datatypes	0

Symbols

/

110

+

258

*

245

>=

516

Evaluations

Evaluation	Rating	Solver	Variant	Result	Wallclock	CPU Time
SMT-COMP 2024	1.00 (0/5)	cvc5	cvc5	unknown ❌	1201.71200	1200.87068
		SMTInterpol	SMTInterpol	unknown ❌	0.78415	1.64996
		SMT-RAT	SMT-RAT	unknown ❌	1201.71108	1200.90888
		Yices2	Yices2	unknown ❌	1201.22042	1201.09364
		Z3alpha	Z3-alpha	unknown ❌	1201.72035	1201.11708
SMT-COMP 2025	1.00 (0/6)	cvc5	cvc5	unknown ❌	1201.77592	1200.97779
		SMTInterpol	SMTInterpol	unknown ❌	0.71824	1.41602
		SMT-RAT	SMT-RAT	unknown ❌	1201.27310	1200.93756
		Yices2	Yices2	unknown ❌	1201.25974	1201.03226
		Z3alpha	Z3-alpha	unknown ❌	1201.00593	4802.13839
		Z3	Z3-alpha-base	unknown ❌	1201.37013	1201.11054
			z3siri-base	unknown ❌	1201.28112	1200.95902