/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 177 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 12.1 s] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] (6) LLVM Symbolic Execution Lasso (7) Lasso2IRS [SOUND, 164 ms] (8) IntTRS (9) IRS2T2 [EQUIVALENT, 0 ms] (10) T2IntSys (11) T2 [EQUIVALENT, 1061 ms] (12) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "Ack" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (m i32, n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %2 = alloca i32, align 4 %3 = alloca i32, align 4 store %m, %2 store %n, %3 %4 = load %2 %5 = icmp eq %4 0 br %5, %6, %9 6: %7 = load %3 %8 = add %7 1 store %8, %1 br %24 9: %10 = load %3 %11 = icmp eq %10 0 br %11, %12, %16 12: %13 = load %2 %14 = sub %13 1 %15 = call i32 @Ack(i32 %14, i32 1) store %15, %1 br %24 16: %17 = load %2 %18 = sub %17 1 %19 = load %2 %20 = load %3 %21 = sub %20 1 %22 = call i32 @Ack(i32 %19, i32 %21) %23 = call i32 @Ack(i32 %18, i32 %22) store %23, %1 br %24 24: %25 = load %1 ret %25 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %y = alloca i32, align 4 %r = alloca i32, align 4 store 0, %1 %2 = call i32 (...)* @__VERIFIER_nondet_int() store %2, %x %3 = call i32 (...)* @__VERIFIER_nondet_int() store %3, %y %4 = load %x %5 = icmp slt %4 0 br %5, %9, %6 6: %7 = load %y %8 = icmp slt %7 0 br %8, %9, %10 9: store 0, %1 br %15 10: %11 = load %x %12 = load %y %13 = call i32 @Ack(i32 %11, i32 %12) store %13, %r %14 = load %r store %14, %1 br %15 15: %16 = load %1 ret %16 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) Converted SEGraph to 1 independent lasso. ---------------------------------------- (6) Obligation: Lasso ---------------------------------------- (7) Lasso2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 109 rulesP rules: f_288(v93, v94, v108, v95, v96, v97, v98, v99, v100, v101, v102, v109, 0, v104, v105, 3, 1, 4) -> f_290(v93, v94, v108, v115, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, 0, v104, v105, 3, 1, 4) :|: 1 <= v115 && v116 = 3 + v115 && 4 <= v116 f_290(v93, v94, v108, v115, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, 0, v104, v105, 3, 1, 4) -> f_291(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) :|: 1 <= v117 && v118 = 3 + v117 && 4 <= v118 f_291(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) -> f_292(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) :|: TRUE f_292(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) -> f_293(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) :|: TRUE f_293(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) -> f_294(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) :|: 0 = 0 f_294(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) -> f_296(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) :|: v93 != 0 && 1 <= v104 f_296(v93, v94, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, 0, v104, v105, 3, 1, 4) -> f_298(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_298(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_300(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: TRUE f_300(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_302(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_302(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_304(v93, 0, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: v94 = 0 f_302(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_305(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: v94 != 0 f_304(v93, 0, v108, v115, v117, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_307(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) :|: 0 = 0 f_307(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) -> f_310(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) :|: TRUE f_310(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) -> f_313(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) :|: 0 = 0 f_313(v93, 0, v108, v115, v117, 1, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) -> f_316(v93, 0, v108, v115, v117, 1, v141, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) :|: 1 + v141 = v93 && 0 <= v141 f_316(v93, 0, v108, v115, v117, 1, v141, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4) -> f_319(v141, 1, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 3, 4) :|: 0 = 0 f_319(v141, 1, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 3, 4) -> f_322(v141, 1, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 3, 4) :|: TRUE f_322(v141, 1, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 3, 4) -> f_285(v141, 1, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_285(v93, v94, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) -> f_288(v93, v94, v108, v95, v96, v97, v98, v99, v100, v101, v102, v109, 0, v104, v105, 3, 1, 4) :|: 1 <= v108 && v109 = 3 + v108 && 4 <= v109 f_305(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_308(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_308(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_311(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: TRUE f_311(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_314(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_314(v93, v94, v108, v115, v117, 0, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_317(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 1 + v142 = v93 && 0 <= v142 f_317(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_320(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_320(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_323(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_323(v93, v94, v108, v115, v117, 0, v142, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_325(v93, v94, v108, v115, v117, 0, v142, v157, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 1 + v157 = v94 && 0 <= v157 f_325(v93, v94, v108, v115, v117, 0, v142, v157, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: 0 = 0 f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_331(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_474(v93, 0, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_520(v93, 0, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_564(v93, 0, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_619(v93, 0, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_678(v93, 0, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_689(v93, v157, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_735(v93, 0, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_788(v93, 0, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_796(v93, v157, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_844(v93, 0, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_853(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_891(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_918(v93, 0, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_928(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_328(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_958(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_331(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, 3, 1, 4) -> f_285(v93, v157, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_474(v93, 0, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_479(v93, 1, v108, v115, v117, 0, v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_479(v93, 1, v108, v115, v117, 0, v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_481(v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_481(v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_483(v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_483(v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v1084, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_520(v93, 0, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_529(v93, 1, v108, v115, v117, 0, v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_529(v93, 1, v108, v115, v117, 0, v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_535(v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_535(v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_541(v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_541(v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v1355, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_564(v93, 0, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_576(v93, 1, v108, v115, v117, 0, v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_576(v93, 1, v108, v115, v117, 0, v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_584(v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_584(v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_596(v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_596(v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v1655, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_619(v93, 0, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_635(v93, 1, v108, v115, v117, 0, v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_635(v93, 1, v108, v115, v117, 0, v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_647(v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_647(v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_664(v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_664(v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v1960, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_678(v93, 0, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_619(v93, 0, v1960, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_689(v93, v157, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_697(v93, v94, v108, v115, v117, 0, v142, v157, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_697(v93, v94, v108, v115, v117, 0, v142, v157, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_705(v142, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) :|: 0 = 0 f_705(v142, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) -> f_713(v142, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) :|: TRUE f_713(v142, v2360, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) -> f_285(v142, v2360, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_735(v93, 0, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_751(v93, 1, v108, v115, v117, 0, v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_751(v93, 1, v108, v115, v117, 0, v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_763(v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_763(v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_774(v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_774(v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v2624, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_788(v93, 0, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_735(v93, 0, v2624, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_796(v93, v157, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_813(v93, v94, v108, v115, v117, 0, v142, v157, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_813(v93, v94, v108, v115, v117, 0, v142, v157, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_823(v142, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) :|: 0 = 0 f_823(v142, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) -> f_833(v142, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) :|: TRUE f_833(v142, v3017, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) -> f_285(v142, v3017, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_844(v93, 0, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_863(v93, 1, v108, v115, v117, 0, v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) :|: 0 = 0 f_863(v93, 1, v108, v115, v117, 0, v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 4, 2) -> f_877(v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: 0 = 0 f_877(v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_900(v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) :|: TRUE f_900(v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, 1, 3, 4, 2) -> f_285(v142, v3405, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_853(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_869(v93, v94, v108, v115, v117, 0, v142, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) :|: 0 = 0 f_869(v93, v94, v108, v115, v117, 0, v142, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v109, v116, v118, v104, v105, 3, 1, 4) -> f_882(v142, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) :|: 0 = 0 f_882(v142, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, v157, 3, 1, 4) -> f_905(v142, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) :|: TRUE f_905(v142, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v93, v94, 3, 1, 4) -> f_285(v142, v3508, v95, v96, v97, v98, v99, v100, v101, v102, 0, v104, v105, 3, 1, 4) :|: TRUE f_891(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_853(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_918(v93, 0, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) -> f_844(v93, 0, v3405, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, v104, v105, 1, v142, 3, 4, 2) :|: TRUE f_928(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_891(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_958(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) -> f_928(v93, v157, v3508, v95, v96, v97, v98, v99, v100, v101, v102, v108, v109, v115, v116, v117, v118, 0, v104, v105, v94, v142, 3, 1, 4) :|: TRUE f_175 -> f_176(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 f_176(v1, v2, 3, 1, 4) -> f_177(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 f_177(v1, v3, v2, v4, 3, 1, 4) -> f_178(v1, v3, v5, v2, v4, v6, 3, 1, 4) :|: 1 <= v5 && v6 = 3 + v5 && 4 <= v6 f_178(v1, v3, v5, v2, v4, v6, 3, 1, 4) -> f_179(v1, v3, v5, v7, v2, v4, v6, v8, 3, 1, 4) :|: 1 <= v7 && v8 = 3 + v7 && 4 <= v8 f_179(v1, v3, v5, v7, v2, v4, v6, v8, 3, 1, 4) -> f_180(v1, v3, v5, v7, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_180(v1, v3, v5, v7, v2, v4, v6, v8, 0, 3, 1, 4) -> f_181(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_181(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) -> f_182(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_182(v1, v3, v5, v7, v9, v2, v4, v6, v8, 0, 3, 1, 4) -> f_183(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_183(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_184(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: TRUE f_184(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_185(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: 0 = 0 f_185(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_187(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) :|: 0 <= v9 f_187(v1, v3, v5, v7, v9, v11, v2, v4, v6, v8, 0, 3, 1, 4) -> f_189(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 = 0 f_189(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_191(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: TRUE f_191(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_193(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 = 0 f_193(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_196(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 <= v11 f_196(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_199(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 = 0 f_199(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_201(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: TRUE f_201(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_203(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 = 0 f_203(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_205(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) :|: 0 = 0 f_205(v1, v3, v5, v7, v9, v11, 0, v2, v4, v6, v8, 3, 1, 4) -> f_207(v9, v11, v1, v2, v3, v4, v5, v6, v7, v8, 0, 3, 1, 4) :|: 0 = 0 f_207(v9, v11, v1, v2, v3, v4, v5, v6, v7, v8, 0, 3, 1, 4) -> f_208(v9, v11, v1, v2, v3, v4, v5, v6, v7, v8, 0, 3, 1, 4) :|: TRUE f_208(v9, v11, v1, v2, v3, v4, v5, v6, v7, v8, 0, 3, 1, 4) -> f_245(v9, v11, v1, v2, v3, v4, v5, v6, v7, v8, 0, v9, v11, 3, 1, 4) :|: TRUE f_245(v42, v43, v44, v45, v46, v47, v48, v49, v50, v51, 0, v53, v54, 3, 1, 4) -> f_285(v42, v43, v44, v45, v46, v47, v48, v49, v50, v51, 0, v53, v54, 3, 1, 4) :|: TRUE Combined rules. Obtained 4 rulesP rules: f_288(1 + v141:0, 0, v108:0, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, v109:0, 0, v104:0, v105:0, 3, 1, 4) -> f_288(v141:0, 1, v108:1, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, 3 + v108:1, 0, v104:0, v105:0, 3, 1, 4) :|: v117:0 > 0 && v115:0 > 0 && v104:0 > 0 && v141:0 > -1 && v108:1 > 0 f_288(1 + v142:0, 1 + v157:0, v108:0, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, v109:0, 0, v104:0, v105:0, 3, 1, 4) -> f_288(v142:0, v1960:0, v108:1, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, 3 + v108:1, 0, v104:0, v105:0, 3, 1, 4) :|: v117:0 > 0 && v115:0 > 0 && v104:0 > 0 && v142:0 > -1 && v157:0 > -1 && v108:1 > 0 f_175 -> f_288(v9:0, v11:0, v108:0, v1:0, 3 + v1:0, v3:0, 3 + v3:0, v5:0, 3 + v5:0, v7:0, 3 + v7:0, 3 + v108:0, 0, v9:0, v11:0, 3, 1, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v7:0 > 0 && v9:0 > -1 && v11:0 > -1 && v108:0 > 0 f_288(1 + v142:0, 1 + v157:0, v108:0, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, v109:0, 0, v104:0, v105:0, 3, 1, 4) -> f_288(1 + v142:0, v157:0, v108:1, v95:0, v96:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, 3 + v108:1, 0, v104:0, v105:0, 3, 1, 4) :|: v117:0 > 0 && v115:0 > 0 && v104:0 > 0 && v142:0 > -1 && v157:0 > -1 && v108:1 > 0 Filtered unneeded arguments: f_288(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_288(x1, x2, x14) Removed division, modulo operations, cleaned up constraints. Obtained 4 rules.P rules: f_288(sum~cons_1~v141:0, cons_0, v104:0) -> f_288(v141:0, 1, v104:0) :|: v104:0 > 0 && v141:0 > -1 && sum~cons_1~v141:0 = 1 + v141:0 && cons_0 = 0 f_288(sum~cons_1~v142:0, sum~cons_1~v157:0, v104:0) -> f_288(v142:0, v1960:0, v104:0) :|: v142:0 > -1 && v157:0 > -1 && v104:0 > 0 && sum~cons_1~v142:0 = 1 + v142:0 && sum~cons_1~v157:0 = 1 + v157:0 f_175 -> f_288(v9:0, v11:0, v9:0) :|: v9:0 > -1 && v11:0 > -1 f_288(sum~cons_1~v142:0, sum~cons_1~v157:0, v104:0) -> f_288(1 + v142:0, v157:0, v104:0) :|: v142:0 > -1 && v157:0 > -1 && v104:0 > 0 && sum~cons_1~v142:0 = 1 + v142:0 && sum~cons_1~v157:0 = 1 + v157:0 ---------------------------------------- (8) Obligation: Rules: f_288(sum~cons_1~v141:0, cons_0, v104:0) -> f_288(v141:0, 1, v104:0) :|: v104:0 > 0 && v141:0 > -1 && sum~cons_1~v141:0 = 1 + v141:0 && cons_0 = 0 f_288(x, x1, x2) -> f_288(x3, x4, x2) :|: x3 > -1 && x5 > -1 && x2 > 0 && x = 1 + x3 && x1 = 1 + x5 f_175 -> f_288(v9:0, v11:0, v9:0) :|: v9:0 > -1 && v11:0 > -1 f_288(x6, x7, x8) -> f_288(1 + x9, x10, x8) :|: x9 > -1 && x10 > -1 && x8 > 0 && x6 = 1 + x9 && x7 = 1 + x10 Start term: f_175 ---------------------------------------- (9) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_288_3,1) (f_175_3,2) ---------------------------------------- (10) Obligation: START: 2; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX0 - 1; assume(oldX2 > 0 && oldX3 > -1 && oldX0 = 1 + oldX3 && oldX1 = 0); x0 := oldX0 - 1; x1 := 1; x2 := oldX2; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX0 - 1; oldX5 := oldX1 - 1; oldX4 := nondet(); assume(oldX3 > -1 && oldX5 > -1 && oldX2 > 0 && oldX0 = 1 + oldX3 && oldX1 = 1 + oldX5); x0 := oldX0 - 1; x1 := oldX4; x2 := oldX2; TO: 1; FROM: 2; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := nondet(); oldX4 := nondet(); assume(oldX3 > -1 && oldX4 > -1); x0 := oldX3; x1 := oldX4; x2 := oldX3; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX0 - 1; oldX4 := oldX1 - 1; assume(oldX3 > -1 && oldX4 > -1 && oldX2 > 0 && oldX0 = 1 + oldX3 && oldX1 = 1 + oldX4); x0 := 1 + oldX3; x1 := oldX1 - 1; x2 := oldX2; TO: 1; ---------------------------------------- (11) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 4, 5, 6 using the following rank functions: - Rank function 1: RF for loc. 5: x0 RF for loc. 6: x0 Bound for (chained) transitions 4: 1 Bound for (chained) transitions 5: 1 - Rank function 2: RF for loc. 5: 2*x1 RF for loc. 6: -1+2*x1 Bound for (chained) transitions 6: 1 - Rank function 3: RF for loc. 5: 0 RF for loc. 6: -1 Bound for (chained) transitions 1: 0 ---------------------------------------- (12) YES