/export/starexec/sandbox2/solver/bin/starexec_run_c /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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, 664 ms] (4) LLVM Symbolic Execution Graph (5) SEGraph to IRS [EQUIVALENT, 140 ms] (6) IntTRS (7) IRS2T2 [EQUIVALENT, 0 ms] (8) T2IntSys (9) T2 [EQUIVALENT, 1074 ms] (10) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox2/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox2/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: false visibilityType: DEFAULT callingConvention: ccc *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 %M = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %x %3 = call i32 @__VERIFIER_nondet_int() store %3, %M %4 = load %M %5 = icmp sgt %4 0 br %5, %6, %21 6: br %7 7: %8 = load %x %9 = load %M %10 = icmp ne %8 %9 br %10, %11, %20 11: %12 = load %x %13 = load %M %14 = icmp sgt %12 %13 br %14, %15, %16 15: store 0, %x br %19 16: %17 = load %x %18 = add %17 1 store %18, %x br %19 19: br %7 20: br %21 21: ret 0 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) SEGraph to IRS (EQUIVALENT) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 77 rulesP rules: f_90 -> f_91(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 f_91(v1, v2, 3, 1, 4) -> f_92(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 f_92(v1, v3, v2, v4, 3, 1, 4) -> f_93(v1, v3, v5, v2, v4, v6, 3, 1, 4) :|: 1 <= v5 && v6 = 3 + v5 && 4 <= v6 f_93(v1, v3, v5, v2, v4, v6, 3, 1, 4) -> f_94(v1, v3, v5, v2, v4, v6, 0, 3, 1, 4) :|: TRUE f_94(v1, v3, v5, v2, v4, v6, 0, 3, 1, 4) -> f_95(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) :|: TRUE f_95(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) -> f_96(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) :|: TRUE f_96(v1, v3, v5, v7, v2, v4, v6, 0, 3, 1, 4) -> f_97(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: TRUE f_97(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_98(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: TRUE f_98(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_99(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: 0 = 0 f_99(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_100(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: 0 < v9 f_99(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_101(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) :|: v9 <= 0 f_100(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_102(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_101(v1, v3, v5, v7, v9, v2, v4, v6, 0, 3, 1, 4) -> f_103(v1, v3, v5, v7, v9, 0, v2, v4, v6, 3, 1, 4) :|: 0 = 0 f_102(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_104(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: TRUE f_103(v1, v3, v5, v7, v9, 0, v2, v4, v6, 3, 1, 4) -> f_105(v1, v3, v5, v7, v9, 0, v2, v4, v6, 3, 1, 4) :|: TRUE f_104(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_106(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: TRUE f_106(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_107(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_107(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_108(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_108(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_109(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: v7 != v9 f_108(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_110(v1, v3, v5, v9, 1, v2, v4, v6, 0, 3, 4) :|: v7 = v9 f_109(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_111(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_110(v1, v3, v5, v9, 1, v2, v4, v6, 0, 3, 4) -> f_112(v1, v3, v5, v9, 1, 0, v2, v4, v6, 3, 4) :|: 0 = 0 f_111(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_113(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: TRUE f_112(v1, v3, v5, v9, 1, 0, v2, v4, v6, 3, 4) -> f_114(v1, v3, v5, v9, 1, 0, v2, v4, v6, 3, 4) :|: TRUE f_113(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_115(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_114(v1, v3, v5, v9, 1, 0, v2, v4, v6, 3, 4) -> f_116(v1, v3, v5, v9, 1, 0, v2, v4, v6, 3, 4) :|: TRUE f_115(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_117(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: 0 = 0 f_117(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_118(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: v9 < v7 && 2 <= v7 f_117(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_119(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) :|: v7 <= v9 f_118(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_120(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: 0 = 0 f_119(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4) -> f_121(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) :|: 0 = 0 f_120(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_122(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: TRUE f_121(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) -> f_123(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) :|: TRUE f_122(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_124(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: TRUE f_123(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) -> f_125(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) :|: 0 = 0 f_124(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_126(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: TRUE f_125(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4) -> f_127(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) :|: v11 = 1 + v7 f_126(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_128(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) :|: TRUE f_127(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) -> f_129(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) :|: TRUE f_128(v1, v3, v5, v7, v9, 1, v2, v4, v6, 0, 3, 4, 2) -> f_130(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_129(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) -> f_131(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) :|: TRUE f_130(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_132(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_131(v1, v3, v5, v7, v9, 1, 0, v11, v2, v4, v6, 3, 4) -> f_177(v1, v3, v5, v7, v9, 1, v7, 0, v11, v2, v4, v6, 3, 4) :|: TRUE f_132(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_134(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_134(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_136(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: TRUE f_136(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_138(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_138(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_141(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_141(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_144(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_144(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_147(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: TRUE f_147(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_150(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_150(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_152(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: 0 = 0 f_152(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_154(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: TRUE f_154(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_156(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: TRUE f_156(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_158(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) :|: TRUE f_158(v1, v3, v5, v7, v9, 1, 0, v2, v4, v6, 3, 4, 2) -> f_159(v1, v3, v5, v7, v9, 1, 0, 0, 1, v2, v4, v6, 3, 4) :|: TRUE f_159(v39, v40, v41, v42, v43, 1, v45, 0, v47, v48, v49, v50, 3, 4) -> f_179(v39, v40, v41, v42, v43, 1, v45, 0, v47, v48, v49, v50, 3, 4) :|: TRUE f_177(v72, v73, v74, v75, v76, 1, v78, 0, v80, v81, v82, v83, 3, 4) -> f_197(v72, v73, v74, v75, v76, 1, v78, 0, v80, v81, v82, v83, 3, 4) :|: TRUE f_179(v103, v104, v105, v106, v107, 1, v109, 0, v111, v112, v113, v114, 3, 4) -> f_180(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_180(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_181(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_181(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_182(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: v111 != v107 f_181(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_183(v103, v104, v105, v106, v107, 1, v109, 0, v112, v113, v114, 3, 4) :|: v111 = v107 && 0 <= v109 f_182(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_184(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_183(v103, v104, v105, v106, v107, 1, v109, 0, v112, v113, v114, 3, 4) -> f_185(v103, v104, v105, v106, v107, 1, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_184(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_186(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) :|: TRUE f_185(v103, v104, v105, v106, v107, 1, 0, v109, v112, v113, v114, 3, 4) -> f_187(v103, v104, v105, v106, v107, 1, 0, v109, v112, v113, v114, 3, 4) :|: TRUE f_186(v103, v104, v105, v106, v107, 1, v111, v109, 0, v112, v113, v114, 3, 4) -> f_188(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_187(v103, v104, v105, v106, v107, 1, 0, v109, v112, v113, v114, 3, 4) -> f_189(v103, v104, v105, v106, v107, 1, 0, v109, v112, v113, v114, 3, 4) :|: TRUE f_188(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_190(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_190(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_191(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: 0 = 0 f_191(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_192(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) :|: TRUE f_192(v103, v104, v105, v106, v107, 1, v111, 0, v109, v112, v113, v114, 3, 4) -> f_193(v103, v104, v105, v106, v107, 1, v111, 0, v112, v113, v114, 3, 4) :|: 0 = 0 f_193(v103, v104, v105, v106, v107, 1, v111, 0, v112, v113, v114, 3, 4) -> f_194(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: v124 = 1 + v111 f_194(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_195(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: TRUE f_195(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_196(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: TRUE f_196(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) -> f_197(v103, v104, v105, v106, v107, 1, v111, 0, v124, v112, v113, v114, 3, 4) :|: TRUE f_197(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) -> f_198(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) :|: TRUE f_198(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) -> f_179(v138, v139, v140, v141, v142, 1, v144, 0, v146, v147, v148, v149, 3, 4) :|: TRUE Combined rules. Obtained 9 rulesP rules: f_90 -> f_116(v1:0, v3:0, v5:0, v7:0, 1, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v7:0 > 0 f_90 -> f_105(v1:0, v3:0, v5:0, v7:0, v9:0, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 1, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v9:0 < 1 f_90 -> f_181(v1:0, v3:0, v5:0, v7:0, v9:0, 1, 1 + v7:0, v7:0, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 4) :|: v9:0 > v7:0 && v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v9:0 > 0 f_90 -> f_181(v1:0, v3:0, v5:0, v7:0, v9:0, 1, v11:0, v7:0, 0, v2:0, v4:0, v6:0, 3, 4) :|: FALSE f_90 -> f_181(v1:0, v3:0, v5:0, v7:0, v9:0, 1, 1, 0, 0, v2:0, v4:0, v6:0, 3, 4) :|: FALSE f_90 -> f_181(v1:0, v3:0, v5:0, v7:0, v9:0, 1, 1, 0, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > 0 && v9:0 > 0 && v9:0 < v7:0 && v7:0 > 1 f_181(v103:0, v104:0, v105:0, v106:0, v107:0, 1, v111:0, v109:0, 0, v112:0, v113:0, v114:0, 3, 4) -> f_181(v103:0, v104:0, v105:0, v106:0, v107:0, 1, 1 + v111:0, v111:0, 0, v112:0, v113:0, v114:0, 3, 4) :|: v111:0 < v107:0 f_181(v103:0, v104:0, v105:0, v106:0, v107:0, 1, v111:0, v109:0, 0, v112:0, v113:0, v114:0, 3, 4) -> f_181(v103:0, v104:0, v105:0, v106:0, v107:0, 1, 1 + v111:0, v111:0, 0, v112:0, v113:0, v114:0, 3, 4) :|: v111:0 > v107:0 f_181(v103:0, v104:0, v105:0, v106:0, v107:0, 1, v107:0, v109:0, 0, v112:0, v113:0, v114:0, 3, 4) -> f_189(v103:0, v104:0, v105:0, v106:0, v107:0, 1, 0, v109:0, v112:0, v113:0, v114:0, 3, 4) :|: v109:0 > -1 Filtered unneeded arguments: f_181(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_181(x4, x5, x7, x8) Removed division, modulo operations, cleaned up constraints. Obtained 9 rules.P rules: f_90 -> f_116(v1:0, v3:0, v5:0, v7:0, 1, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 4) :|: v1:0 > 0 && v3:0 > 0 && v7:0 > 0 && v5:0 > 0 f_90 -> f_105(v1:0, v3:0, v5:0, v7:0, v9:0, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 1, 4) :|: v1:0 > 0 && v3:0 > 0 && v9:0 < 1 && v5:0 > 0 f_90 -> f_181(v7:0, v9:0, 1 + v7:0, v7:0) :|: v9:0 > v7:0 && v9:0 > 0 f_90 -> f_181(v7:0, v9:0, v11:0, v7:0) :|: FALSE f_90 -> f_181(v7:0, v9:0, 1, 0) :|: FALSE f_90 -> f_181(v7:0, v9:0, 1, 0) :|: v9:0 < v7:0 && v7:0 > 1 && v9:0 > 0 f_181(v106:0, v107:0, v111:0, v109:0) -> f_181(v106:0, v107:0, 1 + v111:0, v111:0) :|: v111:0 < v107:0 f_181(v106:0, v107:0, v111:0, v109:0) -> f_181(v106:0, v107:0, 1 + v111:0, v111:0) :|: v111:0 > v107:0 f_181(v106:0, v107:0, v107:01, v109:0) -> f_189(v103:0, v104:0, v105:0, v106:0, v107:0, 1, 0, v109:0, v112:0, v113:0, v114:0, 3, 4) :|: v109:0 > -1 && v107:0 = v107:01 ---------------------------------------- (6) Obligation: Rules: f_90 -> f_116(v1:0, v3:0, v5:0, v7:0, 1, 0, 3 + v1:0, 3 + v3:0, 3 + v5:0, 3, 4) :|: v1:0 > 0 && v3:0 > 0 && v7:0 > 0 && v5:0 > 0 f_90 -> f_105(x, x1, x2, x3, x4, 0, 3 + x, 3 + x1, 3 + x2, 3, 1, 4) :|: x > 0 && x1 > 0 && x4 < 1 && x2 > 0 f_90 -> f_181(x5, x6, 1 + x5, x5) :|: x6 > x5 && x6 > 0 f_90 -> f_181(x7, x8, x9, x7) :|: FALSE f_90 -> f_181(x10, x11, 1, 0) :|: FALSE f_90 -> f_181(x12, x13, 1, 0) :|: x13 < x12 && x12 > 1 && x13 > 0 f_181(v106:0, v107:0, v111:0, v109:0) -> f_181(v106:0, v107:0, 1 + v111:0, v111:0) :|: v111:0 < v107:0 f_181(x14, x15, x16, x17) -> f_181(x14, x15, 1 + x16, x16) :|: x16 > x15 f_181(x18, x19, x20, x21) -> f_189(x22, x23, x24, x18, x19, 1, 0, x21, x25, x26, x27, 3, 4) :|: x21 > -1 && x19 = x20 Start term: f_90 ---------------------------------------- (7) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_90_13,1) (f_116_13,2) (f_105_13,3) (f_181_13,4) (f_189_13,5) ---------------------------------------- (8) Obligation: START: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); assume(oldX13 > 0 && oldX14 > 0 && oldX16 > 0 && oldX15 > 0); x0 := oldX13; x1 := oldX14; x2 := oldX15; x3 := oldX16; x4 := 1; x5 := 0; x6 := 3 + oldX13; x7 := 3 + oldX14; x8 := 3 + oldX15; x9 := 3; x10 := 4; x11 := oldX17; x12 := oldX18; TO: 2; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); assume(oldX13 > 0 && oldX14 > 0 && oldX17 < 1 && oldX15 > 0); x0 := oldX13; x1 := oldX14; x2 := oldX15; x3 := oldX16; x4 := oldX17; x5 := 0; x6 := 3 + oldX13; x7 := 3 + oldX14; x8 := 3 + oldX15; x9 := 3; x10 := 1; x11 := 4; x12 := oldX18; TO: 3; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); oldX22 := nondet(); oldX23 := nondet(); assume(oldX14 > oldX13 && oldX14 > 0); x0 := oldX13; x1 := oldX14; x2 := 1 + oldX13; x3 := oldX13; x4 := oldX15; x5 := oldX16; x6 := oldX17; x7 := oldX18; x8 := oldX19; x9 := oldX20; x10 := oldX21; x11 := oldX22; x12 := oldX23; TO: 4; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); oldX22 := nondet(); oldX23 := nondet(); oldX24 := nondet(); assume(0 = 1); x0 := oldX13; x1 := oldX14; x2 := oldX15; x3 := oldX13; x4 := oldX16; x5 := oldX17; x6 := oldX18; x7 := oldX19; x8 := oldX20; x9 := oldX21; x10 := oldX22; x11 := oldX23; x12 := oldX24; TO: 4; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); oldX22 := nondet(); oldX23 := nondet(); assume(0 = 1); x0 := oldX13; x1 := oldX14; x2 := 1; x3 := 0; x4 := oldX15; x5 := oldX16; x6 := oldX17; x7 := oldX18; x8 := oldX19; x9 := oldX20; x10 := oldX21; x11 := oldX22; x12 := oldX23; TO: 4; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); oldX22 := nondet(); oldX23 := nondet(); assume(oldX14 < oldX13 && oldX13 > 1 && oldX14 > 0); x0 := oldX13; x1 := oldX14; x2 := 1; x3 := 0; x4 := oldX15; x5 := oldX16; x6 := oldX17; x7 := oldX18; x8 := oldX19; x9 := oldX20; x10 := oldX21; x11 := oldX22; x12 := oldX23; TO: 4; FROM: 4; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); assume(oldX2 < oldX1); x0 := oldX0; x1 := oldX1; x2 := 1 + oldX2; x3 := oldX2; x4 := oldX13; x5 := oldX14; x6 := oldX15; x7 := oldX16; x8 := oldX17; x9 := oldX18; x10 := oldX19; x11 := oldX20; x12 := oldX21; TO: 4; FROM: 4; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); oldX19 := nondet(); oldX20 := nondet(); oldX21 := nondet(); assume(oldX2 > oldX1); x0 := oldX0; x1 := oldX1; x2 := 1 + oldX2; x3 := oldX2; x4 := oldX13; x5 := oldX14; x6 := oldX15; x7 := oldX16; x8 := oldX17; x9 := oldX18; x10 := oldX19; x11 := oldX20; x12 := oldX21; TO: 4; FROM: 4; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := x3; oldX4 := x4; oldX5 := x5; oldX6 := x6; oldX7 := x7; oldX8 := x8; oldX9 := x9; oldX10 := x10; oldX11 := x11; oldX12 := x12; oldX13 := nondet(); oldX14 := nondet(); oldX15 := nondet(); oldX16 := nondet(); oldX17 := nondet(); oldX18 := nondet(); assume(oldX3 > -1 && oldX1 = oldX2); x0 := oldX13; x1 := oldX14; x2 := oldX15; x3 := oldX0; x4 := oldX1; x5 := 1; x6 := 0; x7 := oldX3; x8 := oldX16; x9 := oldX17; x10 := oldX18; x11 := 3; x12 := 4; TO: 5; ---------------------------------------- (9) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 14 using the following rank functions: - Rank function 1: RF for loc. 8: 1+2*x1-2*x2 RF for loc. 9: 2*x1-2*x2 Bound for (chained) transitions 14: 2 Used the following cutpoint-specific lexicographic rank functions: * For cutpoint 8, used the following rank functions/bounds (in descending priority order): - RF -x2+x1, bound 1 ---------------------------------------- (10) YES