5.78/2.24 WORST_CASE(NON_POLY, ?) 5.78/2.24 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.78/2.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.78/2.24 5.78/2.24 5.78/2.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.78/2.24 5.78/2.24 (0) CpxTRS 5.78/2.24 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 5.78/2.24 (2) TRS for Loop Detection 5.78/2.24 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 5.78/2.24 (4) BEST 5.78/2.24 (5) proven lower bound 5.78/2.24 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 5.78/2.24 (7) BOUNDS(n^1, INF) 5.78/2.24 (8) TRS for Loop Detection 5.78/2.24 (9) DecreasingLoopProof [FINISHED, 353 ms] 5.78/2.24 (10) BOUNDS(EXP, INF) 5.78/2.24 5.78/2.24 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (0) 5.78/2.24 Obligation: 5.78/2.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.78/2.24 5.78/2.24 5.78/2.24 The TRS R consists of the following rules: 5.78/2.24 5.78/2.24 and(true, y) -> y 5.78/2.24 and(false, y) -> false 5.78/2.24 eq(nil, nil) -> true 5.78/2.24 eq(cons(t, l), nil) -> false 5.78/2.24 eq(nil, cons(t, l)) -> false 5.78/2.24 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.78/2.24 eq(var(l), var(l')) -> eq(l, l') 5.78/2.24 eq(var(l), apply(t, s)) -> false 5.78/2.24 eq(var(l), lambda(x, t)) -> false 5.78/2.24 eq(apply(t, s), var(l)) -> false 5.78/2.24 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.78/2.24 eq(apply(t, s), lambda(x, t)) -> false 5.78/2.24 eq(lambda(x, t), var(l)) -> false 5.78/2.24 eq(lambda(x, t), apply(t, s)) -> false 5.78/2.24 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.78/2.24 if(true, var(k), var(l')) -> var(k) 5.78/2.24 if(false, var(k), var(l')) -> var(l') 5.78/2.24 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.78/2.24 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.78/2.24 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.78/2.24 5.78/2.24 S is empty. 5.78/2.24 Rewrite Strategy: FULL 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 5.78/2.24 Transformed a relative TRS into a decreasing-loop problem. 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (2) 5.78/2.24 Obligation: 5.78/2.24 Analyzing the following TRS for decreasing loops: 5.78/2.24 5.78/2.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.78/2.24 5.78/2.24 5.78/2.24 The TRS R consists of the following rules: 5.78/2.24 5.78/2.24 and(true, y) -> y 5.78/2.24 and(false, y) -> false 5.78/2.24 eq(nil, nil) -> true 5.78/2.24 eq(cons(t, l), nil) -> false 5.78/2.24 eq(nil, cons(t, l)) -> false 5.78/2.24 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.78/2.24 eq(var(l), var(l')) -> eq(l, l') 5.78/2.24 eq(var(l), apply(t, s)) -> false 5.78/2.24 eq(var(l), lambda(x, t)) -> false 5.78/2.24 eq(apply(t, s), var(l)) -> false 5.78/2.24 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.78/2.24 eq(apply(t, s), lambda(x, t)) -> false 5.78/2.24 eq(lambda(x, t), var(l)) -> false 5.78/2.24 eq(lambda(x, t), apply(t, s)) -> false 5.78/2.24 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.78/2.24 if(true, var(k), var(l')) -> var(k) 5.78/2.24 if(false, var(k), var(l')) -> var(l') 5.78/2.24 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.78/2.24 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.78/2.24 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.78/2.24 5.78/2.24 S is empty. 5.78/2.24 Rewrite Strategy: FULL 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (3) DecreasingLoopProof (LOWER BOUND(ID)) 5.78/2.24 The following loop(s) give(s) rise to the lower bound Omega(n^1): 5.78/2.24 5.78/2.24 The rewrite sequence 5.78/2.24 5.78/2.24 eq(lambda(x, t), lambda(x', t')) ->^+ and(eq(x, x'), eq(t, t')) 5.78/2.24 5.78/2.24 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 5.78/2.24 5.78/2.24 The pumping substitution is [x / lambda(x, t), x' / lambda(x', t')]. 5.78/2.24 5.78/2.24 The result substitution is [ ]. 5.78/2.24 5.78/2.24 5.78/2.24 5.78/2.24 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (4) 5.78/2.24 Complex Obligation (BEST) 5.78/2.24 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (5) 5.78/2.24 Obligation: 5.78/2.24 Proved the lower bound n^1 for the following obligation: 5.78/2.24 5.78/2.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.78/2.24 5.78/2.24 5.78/2.24 The TRS R consists of the following rules: 5.78/2.24 5.78/2.24 and(true, y) -> y 5.78/2.24 and(false, y) -> false 5.78/2.24 eq(nil, nil) -> true 5.78/2.24 eq(cons(t, l), nil) -> false 5.78/2.24 eq(nil, cons(t, l)) -> false 5.78/2.24 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.78/2.24 eq(var(l), var(l')) -> eq(l, l') 5.78/2.24 eq(var(l), apply(t, s)) -> false 5.78/2.24 eq(var(l), lambda(x, t)) -> false 5.78/2.24 eq(apply(t, s), var(l)) -> false 5.78/2.24 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.78/2.24 eq(apply(t, s), lambda(x, t)) -> false 5.78/2.24 eq(lambda(x, t), var(l)) -> false 5.78/2.24 eq(lambda(x, t), apply(t, s)) -> false 5.78/2.24 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.78/2.24 if(true, var(k), var(l')) -> var(k) 5.78/2.24 if(false, var(k), var(l')) -> var(l') 5.78/2.24 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.78/2.24 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.78/2.24 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.78/2.24 5.78/2.24 S is empty. 5.78/2.24 Rewrite Strategy: FULL 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (6) LowerBoundPropagationProof (FINISHED) 5.78/2.24 Propagated lower bound. 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (7) 5.78/2.24 BOUNDS(n^1, INF) 5.78/2.24 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (8) 5.78/2.24 Obligation: 5.78/2.24 Analyzing the following TRS for decreasing loops: 5.78/2.24 5.78/2.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF). 5.78/2.24 5.78/2.24 5.78/2.24 The TRS R consists of the following rules: 5.78/2.24 5.78/2.24 and(true, y) -> y 5.78/2.24 and(false, y) -> false 5.78/2.24 eq(nil, nil) -> true 5.78/2.24 eq(cons(t, l), nil) -> false 5.78/2.24 eq(nil, cons(t, l)) -> false 5.78/2.24 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.78/2.24 eq(var(l), var(l')) -> eq(l, l') 5.78/2.24 eq(var(l), apply(t, s)) -> false 5.78/2.24 eq(var(l), lambda(x, t)) -> false 5.78/2.24 eq(apply(t, s), var(l)) -> false 5.78/2.24 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.78/2.24 eq(apply(t, s), lambda(x, t)) -> false 5.78/2.24 eq(lambda(x, t), var(l)) -> false 5.78/2.24 eq(lambda(x, t), apply(t, s)) -> false 5.78/2.24 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.78/2.24 if(true, var(k), var(l')) -> var(k) 5.78/2.24 if(false, var(k), var(l')) -> var(l') 5.78/2.24 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.78/2.24 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.78/2.24 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.78/2.24 5.78/2.24 S is empty. 5.78/2.24 Rewrite Strategy: FULL 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (9) DecreasingLoopProof (FINISHED) 5.78/2.24 The following loop(s) give(s) rise to the lower bound EXP: 5.78/2.24 5.78/2.24 The rewrite sequence 5.78/2.24 5.78/2.24 ren(x, y, lambda(z, lambda(z3_0, t4_0))) ->^+ lambda(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), lambda(var(cons(x, cons(y, cons(lambda(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0))), nil)))), ren(x, y, ren(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), var(cons(x, cons(y, cons(lambda(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0))), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0)))))) 5.78/2.24 5.78/2.24 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0,0,1,1,0,1,2]. 5.78/2.24 5.78/2.24 The pumping substitution is [t4_0 / lambda(z, lambda(z3_0, t4_0))]. 5.78/2.24 5.78/2.24 The result substitution is [x / z3_0, y / var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil))))]. 5.78/2.24 5.78/2.24 5.78/2.24 5.78/2.24 The rewrite sequence 5.78/2.24 5.78/2.24 ren(x, y, lambda(z, lambda(z3_0, t4_0))) ->^+ lambda(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), lambda(var(cons(x, cons(y, cons(lambda(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0))), nil)))), ren(x, y, ren(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), var(cons(x, cons(y, cons(lambda(var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0))), nil)))), ren(z, var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), ren(z3_0, var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil)))), t4_0)))))) 5.78/2.24 5.78/2.24 gives rise to a decreasing loop by considering the right hand sides subterm at position [1,1,2,1,0,1,1,0,1,2]. 5.78/2.24 5.78/2.24 The pumping substitution is [t4_0 / lambda(z, lambda(z3_0, t4_0))]. 5.78/2.24 5.78/2.24 The result substitution is [x / z3_0, y / var(cons(z, cons(var(cons(x, cons(y, cons(lambda(z, lambda(z3_0, t4_0)), nil)))), cons(lambda(z3_0, t4_0), nil))))]. 5.78/2.24 5.78/2.24 5.78/2.24 5.78/2.24 5.78/2.24 ---------------------------------------- 5.78/2.24 5.78/2.24 (10) 5.78/2.24 BOUNDS(EXP, INF) 5.78/2.29 EOF