1135.90/297.70 WORST_CASE(Omega(n^1), ?) 1135.90/297.71 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1135.90/297.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1135.90/297.71 1135.90/297.71 1135.90/297.71 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1135.90/297.71 1135.90/297.71 (0) CpxTRS 1135.90/297.71 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1135.90/297.71 (2) TRS for Loop Detection 1135.90/297.71 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1135.90/297.71 (4) BEST 1135.90/297.71 (5) proven lower bound 1135.90/297.71 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1135.90/297.71 (7) BOUNDS(n^1, INF) 1135.90/297.71 (8) TRS for Loop Detection 1135.90/297.71 1135.90/297.71 1135.90/297.71 ---------------------------------------- 1135.90/297.71 1135.90/297.71 (0) 1135.90/297.71 Obligation: 1135.90/297.71 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1135.90/297.71 1135.90/297.71 1135.90/297.71 The TRS R consists of the following rules: 1135.90/297.71 1135.90/297.71 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 1135.90/297.71 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 1135.90/297.71 a__from(X) -> cons(mark(X), from(s(X))) 1135.90/297.71 mark(2nd(X)) -> a__2nd(mark(X)) 1135.90/297.71 mark(from(X)) -> a__from(mark(X)) 1135.90/297.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1135.90/297.71 mark(s(X)) -> s(mark(X)) 1135.90/297.71 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 1135.90/297.71 a__2nd(X) -> 2nd(X) 1135.90/297.71 a__from(X) -> from(X) 1135.90/297.71 1135.90/297.71 S is empty. 1135.90/297.71 Rewrite Strategy: INNERMOST 1135.90/297.71 ---------------------------------------- 1135.90/297.71 1135.90/297.71 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1135.90/297.71 Transformed a relative TRS into a decreasing-loop problem. 1135.90/297.71 ---------------------------------------- 1135.90/297.71 1135.90/297.71 (2) 1135.90/297.71 Obligation: 1135.90/297.71 Analyzing the following TRS for decreasing loops: 1135.90/297.71 1135.90/297.71 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1135.90/297.71 1135.90/297.71 1135.90/297.71 The TRS R consists of the following rules: 1135.90/297.71 1135.90/297.71 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 1135.90/297.71 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 1135.90/297.71 a__from(X) -> cons(mark(X), from(s(X))) 1135.90/297.71 mark(2nd(X)) -> a__2nd(mark(X)) 1135.90/297.71 mark(from(X)) -> a__from(mark(X)) 1135.90/297.71 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1135.90/297.71 mark(s(X)) -> s(mark(X)) 1135.90/297.71 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 1135.90/297.71 a__2nd(X) -> 2nd(X) 1135.90/297.71 a__from(X) -> from(X) 1135.90/297.71 1135.90/297.71 S is empty. 1135.90/297.71 Rewrite Strategy: INNERMOST 1135.90/297.71 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1135.90/297.72 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1135.90/297.72 1135.90/297.72 The rewrite sequence 1135.90/297.72 1135.90/297.72 mark(from(X)) ->^+ a__from(mark(X)) 1135.90/297.72 1135.90/297.72 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1135.90/297.72 1135.90/297.72 The pumping substitution is [X / from(X)]. 1135.90/297.72 1135.90/297.72 The result substitution is [ ]. 1135.90/297.72 1135.90/297.72 1135.90/297.72 1135.90/297.72 1135.90/297.72 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (4) 1135.90/297.72 Complex Obligation (BEST) 1135.90/297.72 1135.90/297.72 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (5) 1135.90/297.72 Obligation: 1135.90/297.72 Proved the lower bound n^1 for the following obligation: 1135.90/297.72 1135.90/297.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1135.90/297.72 1135.90/297.72 1135.90/297.72 The TRS R consists of the following rules: 1135.90/297.72 1135.90/297.72 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 1135.90/297.72 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 1135.90/297.72 a__from(X) -> cons(mark(X), from(s(X))) 1135.90/297.72 mark(2nd(X)) -> a__2nd(mark(X)) 1135.90/297.72 mark(from(X)) -> a__from(mark(X)) 1135.90/297.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1135.90/297.72 mark(s(X)) -> s(mark(X)) 1135.90/297.72 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 1135.90/297.72 a__2nd(X) -> 2nd(X) 1135.90/297.72 a__from(X) -> from(X) 1135.90/297.72 1135.90/297.72 S is empty. 1135.90/297.72 Rewrite Strategy: INNERMOST 1135.90/297.72 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (6) LowerBoundPropagationProof (FINISHED) 1135.90/297.72 Propagated lower bound. 1135.90/297.72 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (7) 1135.90/297.72 BOUNDS(n^1, INF) 1135.90/297.72 1135.90/297.72 ---------------------------------------- 1135.90/297.72 1135.90/297.72 (8) 1135.90/297.72 Obligation: 1135.90/297.72 Analyzing the following TRS for decreasing loops: 1135.90/297.72 1135.90/297.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1135.90/297.72 1135.90/297.72 1135.90/297.72 The TRS R consists of the following rules: 1135.90/297.72 1135.90/297.72 a__2nd(cons1(X, cons(Y, Z))) -> mark(Y) 1135.90/297.72 a__2nd(cons(X, X1)) -> a__2nd(cons1(mark(X), mark(X1))) 1135.90/297.72 a__from(X) -> cons(mark(X), from(s(X))) 1135.90/297.72 mark(2nd(X)) -> a__2nd(mark(X)) 1135.90/297.72 mark(from(X)) -> a__from(mark(X)) 1135.90/297.72 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1135.90/297.72 mark(s(X)) -> s(mark(X)) 1135.90/297.72 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) 1135.90/297.72 a__2nd(X) -> 2nd(X) 1135.90/297.72 a__from(X) -> from(X) 1135.90/297.72 1135.90/297.72 S is empty. 1135.90/297.72 Rewrite Strategy: INNERMOST 1136.07/297.77 EOF