26.36/11.19 YES 26.36/11.21 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 26.36/11.21 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 26.36/11.21 26.36/11.21 26.36/11.21 Termination of the given C Problem could be proven: 26.36/11.21 26.36/11.21 (0) C Problem 26.36/11.21 (1) CToLLVMProof [EQUIVALENT, 154 ms] 26.36/11.21 (2) LLVM problem 26.36/11.21 (3) LLVMToTerminationGraphProof [EQUIVALENT, 5603 ms] 26.36/11.21 (4) LLVM Symbolic Execution Graph 26.36/11.21 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 26.36/11.21 (6) LLVM Symbolic Execution SCC 26.36/11.21 (7) SCC2IRS [SOUND, 191 ms] 26.36/11.21 (8) IntTRS 26.36/11.21 (9) IRS2T2 [EQUIVALENT, 0 ms] 26.36/11.21 (10) T2IntSys 26.36/11.21 (11) T2 [EQUIVALENT, 1126 ms] 26.36/11.21 (12) YES 26.36/11.21 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (0) 26.36/11.21 Obligation: 26.36/11.21 c file /export/starexec/sandbox/benchmark/theBenchmark.c 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (1) CToLLVMProof (EQUIVALENT) 26.36/11.21 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (2) 26.36/11.21 Obligation: 26.36/11.21 LLVM Problem 26.36/11.21 26.36/11.21 Aliases: 26.36/11.21 26.36/11.21 Data layout: 26.36/11.21 26.36/11.21 "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" 26.36/11.21 26.36/11.21 Machine: 26.36/11.21 26.36/11.21 "x86_64-pc-linux-gnu" 26.36/11.21 26.36/11.21 Type definitions: 26.36/11.21 26.36/11.21 Global variables: 26.36/11.21 26.36/11.21 Function declarations and definitions: 26.36/11.21 26.36/11.21 *BasicFunctionTypename: "__VERIFIER_error" returnParam: BasicVoidType parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 26.36/11.21 *BasicFunctionTypename: "fibo" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 26.36/11.21 0: 26.36/11.21 %1 = alloca i32, align 4 26.36/11.21 %2 = alloca i32, align 4 26.36/11.21 store %n, %2 26.36/11.21 %3 = load %2 26.36/11.21 %4 = icmp slt %3 1 26.36/11.21 br %4, %5, %6 26.36/11.21 5: 26.36/11.21 store 0, %1 26.36/11.21 br %18 26.36/11.21 6: 26.36/11.21 %7 = load %2 26.36/11.21 %8 = icmp eq %7 1 26.36/11.21 br %8, %9, %10 26.36/11.21 9: 26.36/11.21 store 1, %1 26.36/11.21 br %18 26.36/11.21 10: 26.36/11.21 %11 = load %2 26.36/11.21 %12 = sub %11 1 26.36/11.21 %13 = call i32 @fibo(i32 %12) 26.36/11.21 %14 = load %2 26.36/11.21 %15 = sub %14 2 26.36/11.21 %16 = call i32 @fibo(i32 %15) 26.36/11.21 %17 = add %13 %16 26.36/11.21 store %17, %1 26.36/11.21 br %18 26.36/11.21 18: 26.36/11.21 %19 = load %1 26.36/11.21 ret %19 26.36/11.21 26.36/11.21 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 26.36/11.21 0: 26.36/11.21 %1 = alloca i32, align 4 26.36/11.21 %x = alloca i32, align 4 26.36/11.21 %result = alloca i32, align 4 26.36/11.21 store 0, %1 26.36/11.21 store 5, %x 26.36/11.21 %2 = load %x 26.36/11.21 %3 = call i32 @fibo(i32 %2) 26.36/11.21 store %3, %result 26.36/11.21 %4 = load %result 26.36/11.21 %5 = icmp eq %4 5 26.36/11.21 br %5, %6, %8 26.36/11.21 6: 26.36/11.21 br %7 26.36/11.21 7: 26.36/11.21 Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() 26.36/11.21 br %8 26.36/11.21 8: 26.36/11.21 ret 0 26.36/11.21 26.36/11.21 26.36/11.21 Analyze Termination of all function calls matching the pattern: 26.36/11.21 main() 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (3) LLVMToTerminationGraphProof (EQUIVALENT) 26.36/11.21 Constructed symbolic execution graph for LLVM program and proved memory safety. 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (4) 26.36/11.21 Obligation: 26.36/11.21 SE Graph 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (5) SymbolicExecutionGraphToSCCProof (SOUND) 26.36/11.21 Splitted symbolic execution graph to 1 SCC. 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (6) 26.36/11.21 Obligation: 26.36/11.21 SCC 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (7) SCC2IRS (SOUND) 26.36/11.21 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 26.36/11.21 Generated rules. Obtained 48 rulesP rules: 26.36/11.21 f_200(v85, v94, v86, v87, v88, v89, v90, v91, v95, 0, 5, 3, 1, 4) -> f_201(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) :|: 1 <= v96 && v97 = 3 + v96 && 4 <= v97 26.36/11.21 f_201(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) -> f_202(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_202(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) -> f_203(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) :|: 0 = 0 26.36/11.21 f_203(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) -> f_205(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) :|: 1 <= v85 26.36/11.21 f_205(v85, v94, v96, v86, v87, v88, v89, v90, v91, v95, v97, 0, 5, 3, 1, 4) -> f_207(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) :|: 0 = 0 26.36/11.21 f_207(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) -> f_209(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_209(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) -> f_211(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) :|: 0 = 0 26.36/11.21 f_211(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 4) -> f_214(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) :|: v85 != 1 && 2 <= v85 && v85 <= 5 26.36/11.21 f_214(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) -> f_217(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) :|: 0 = 0 26.36/11.21 f_217(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) -> f_220(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) :|: TRUE 26.36/11.21 f_220(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) -> f_222(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) :|: 0 = 0 26.36/11.21 f_222(v85, v94, v96, 0, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 2, 1, 4) -> f_224(v85, v94, v96, 0, v109, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 1 + v109 = v85 && 1 <= v109 && v109 <= 4 26.36/11.21 f_224(v85, v94, v96, 0, v109, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_228(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_230(1, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, 2, 3, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_546(v109, v1105, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_576(v109, v1194, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_617(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_656(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_226(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_678(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_228(v109, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_199(v109, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_199(v85, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) -> f_200(v85, v94, v86, v87, v88, v89, v90, v91, v95, 0, 5, 3, 1, 4) :|: 1 <= v94 && v95 = 3 + v94 && 4 <= v95 26.36/11.21 f_230(1, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, 2, 3, 4) -> f_231(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) :|: 0 = 0 26.36/11.21 f_231(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) -> f_232(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) :|: 0 = 0 26.36/11.21 f_232(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) -> f_233(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) :|: 0 = 0 26.36/11.21 f_233(2, v94, v96, 0, 1, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 4) -> f_234(0, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 5, 2, 1, 3, 4) :|: 0 = 0 26.36/11.21 f_234(0, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 5, 2, 1, 3, 4) -> f_235(0, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 5, 2, 3, 1, 4) :|: TRUE 26.36/11.21 f_235(0, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 5, 2, 3, 1, 4) -> f_199(0, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_546(v109, v1105, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_553(v85, v94, v96, 0, v109, v1105, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_553(v85, v94, v96, 0, v109, v1105, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_556(v85, v94, v96, 0, v109, v1105, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_556(v85, v94, v96, 0, v109, v1105, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_559(v85, v94, v96, 0, v109, v1105, v1120, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 2 + v1120 = v85 && 0 <= v1120 && v1120 <= 3 26.36/11.21 f_559(v85, v94, v96, 0, v109, v1105, v1120, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_563(v1120, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1105, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_563(v1120, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1105, 3, 1, 2, 4) -> f_567(v1120, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) :|: TRUE 26.36/11.21 f_567(v1120, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) -> f_199(v1120, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_576(v109, v1194, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_583(v85, v94, v96, 0, v109, v1194, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_583(v85, v94, v96, 0, v109, v1194, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_589(v85, v94, v96, 0, v109, v1194, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_589(v85, v94, v96, 0, v109, v1194, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_595(v85, v94, v96, 0, v109, v1194, v1214, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 2 + v1214 = v85 && 0 <= v1214 && v1214 <= 3 26.36/11.21 f_595(v85, v94, v96, 0, v109, v1194, v1214, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_602(v1214, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1194, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_602(v1214, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1194, 3, 1, 2, 4) -> f_609(v1214, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) :|: TRUE 26.36/11.21 f_609(v1214, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) -> f_199(v1214, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_617(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_624(v85, v94, v96, 0, v109, v1329, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_624(v85, v94, v96, 0, v109, v1329, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_631(v85, v94, v96, 0, v109, v1329, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_631(v85, v94, v96, 0, v109, v1329, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_638(v85, v94, v96, 0, v109, v1329, v1387, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) :|: 2 + v1387 = v85 && 0 <= v1387 && v1387 <= 3 26.36/11.21 f_638(v85, v94, v96, 0, v109, v1329, v1387, v86, v87, v88, v89, v90, v91, v95, v97, 5, 3, 1, 2, 4) -> f_646(v1387, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1329, 3, 1, 2, 4) :|: 0 = 0 26.36/11.21 f_646(v1387, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, v109, v1329, 3, 1, 2, 4) -> f_654(v1387, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) :|: TRUE 26.36/11.21 f_654(v1387, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 2, 1, 4) -> f_199(v1387, v86, v87, v88, v89, v90, v91, 0, 5, 3, 1, 4) :|: TRUE 26.36/11.21 f_656(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_617(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 f_678(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) -> f_656(v109, v1329, v86, v87, v88, v89, v90, v91, v94, v95, v96, v97, 0, 5, v85, 3, 1, 2, 4) :|: TRUE 26.36/11.21 Combined rules. Obtained 3 rulesP rules: 26.36/11.21 f_200(1 + v109:0, v94:0, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, v95:0, 0, 5, 3, 1, 4) -> f_200(v109:0, v94:1, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, 3 + v94:1, 0, 5, 3, 1, 4) :|: v109:0 > 0 && v96:0 > 0 && v109:0 < 5 && v94:1 > 0 26.36/11.21 f_200(2 + v1120:0, v94:0, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, v95:0, 0, 5, 3, 1, 4) -> f_200(v1120:0, v94:1, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, 3 + v94:1, 0, 5, 3, 1, 4) :|: v1120:0 > -1 && v96:0 > 0 && v1120:0 < 4 && v109:0 > 0 && 2 + v1120:0 = 1 + v109:0 && v109:0 < 5 && v94:1 > 0 26.36/11.21 f_200(1 + v109:0, v94:0, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, v95:0, 0, 5, 3, 1, 4) -> f_200(0, v94:1, v86:0, v87:0, v88:0, v89:0, v90:0, v91:0, 3 + v94:1, 0, 5, 3, 1, 4) :|: v109:0 > 0 && v96:0 > 0 && v109:0 < 5 && v94:1 > 0 26.36/11.21 Filtered unneeded arguments: 26.36/11.21 f_200(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_200(x1) 26.36/11.21 Removed division, modulo operations, cleaned up constraints. Obtained 3 rules.P rules: 26.36/11.21 f_200(sum~cons_1~v109:0) -> f_200(v109:0) :|: v109:0 > 0 && v109:0 < 5 && sum~cons_1~v109:0 = 1 + v109:0 26.36/11.21 f_200(sum~cons_2~v1120:0) -> f_200(v1120:0) :|: v1120:0 > -1 && v1120:0 < 4 && sum~cons_2~v1120:0 = 2 + v1120:0 26.36/11.21 f_200(sum~cons_1~v109:0) -> f_200(0) :|: v109:0 > 0 && v109:0 < 5 && sum~cons_1~v109:0 = 1 + v109:0 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (8) 26.36/11.21 Obligation: 26.36/11.21 Rules: 26.36/11.21 f_200(sum~cons_1~v109:0) -> f_200(v109:0) :|: v109:0 > 0 && v109:0 < 5 && sum~cons_1~v109:0 = 1 + v109:0 26.36/11.21 f_200(sum~cons_2~v1120:0) -> f_200(v1120:0) :|: v1120:0 > -1 && v1120:0 < 4 && sum~cons_2~v1120:0 = 2 + v1120:0 26.36/11.21 f_200(x) -> f_200(0) :|: x1 > 0 && x1 < 5 && x = 1 + x1 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (9) IRS2T2 (EQUIVALENT) 26.36/11.21 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 26.36/11.21 26.36/11.21 (f_200_1,1) 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (10) 26.36/11.21 Obligation: 26.36/11.21 START: 0; 26.36/11.21 26.36/11.21 FROM: 0; 26.36/11.21 TO: 1; 26.36/11.21 26.36/11.21 FROM: 1; 26.36/11.21 oldX0 := x0; 26.36/11.21 oldX1 := oldX0 - 1; 26.36/11.21 assume(oldX1 > 0 && oldX1 < 5 && oldX0 = 1 + oldX1); 26.36/11.21 x0 := oldX0 - 1; 26.36/11.21 TO: 1; 26.36/11.21 26.36/11.21 FROM: 1; 26.36/11.21 oldX0 := x0; 26.36/11.21 oldX1 := oldX0 - 2; 26.36/11.21 assume(oldX1 > -1 && oldX1 < 4 && oldX0 = 2 + oldX1); 26.36/11.21 x0 := oldX0 - 2; 26.36/11.21 TO: 1; 26.36/11.21 26.36/11.21 FROM: 1; 26.36/11.21 oldX0 := x0; 26.36/11.21 oldX1 := oldX0 - 1; 26.36/11.21 assume(oldX1 > 0 && oldX1 < 5 && oldX0 = 1 + oldX1); 26.36/11.21 x0 := 0; 26.36/11.21 TO: 1; 26.36/11.21 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (11) T2 (EQUIVALENT) 26.36/11.21 Initially, performed program simplifications using lexicographic rank functions: 26.36/11.21 * Removed transitions 1, 4, 5, 6 using the following rank functions: 26.36/11.21 - Rank function 1: 26.36/11.21 RF for loc. 5: 1+2*x0 26.36/11.21 RF for loc. 6: 2*x0 26.36/11.21 Bound for (chained) transitions 4: 4 26.36/11.21 Bound for (chained) transitions 6: 4 26.36/11.21 - Rank function 2: 26.36/11.21 RF for loc. 5: 1+x0 26.36/11.21 RF for loc. 6: x0 26.36/11.21 Bound for (chained) transitions 5: 2 26.36/11.21 - Rank function 3: 26.36/11.21 RF for loc. 5: 0 26.36/11.21 RF for loc. 6: -1 26.36/11.21 Bound for (chained) transitions 1: 0 26.36/11.21 26.36/11.21 ---------------------------------------- 26.36/11.21 26.36/11.21 (12) 26.36/11.21 YES 26.44/11.51 EOF