1149.31/291.49 WORST_CASE(Omega(n^1), O(n^1)) 1149.31/291.51 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1149.31/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1149.31/291.51 1149.31/291.51 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1149.31/291.51 1149.31/291.51 (0) CpxTRS 1149.31/291.51 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 12 ms] 1149.31/291.51 (2) CpxTRS 1149.31/291.51 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 1149.31/291.51 (4) CpxTRS 1149.31/291.51 (5) CpxTrsMatchBoundsTAProof [FINISHED, 24 ms] 1149.31/291.51 (6) BOUNDS(1, n^1) 1149.31/291.51 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1149.31/291.51 (8) TRS for Loop Detection 1149.31/291.51 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1149.31/291.51 (10) BEST 1149.31/291.51 (11) proven lower bound 1149.31/291.51 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1149.31/291.51 (13) BOUNDS(n^1, INF) 1149.31/291.51 (14) TRS for Loop Detection 1149.31/291.51 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (0) 1149.31/291.51 Obligation: 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 active(f(x)) -> mark(f(f(x))) 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(active(x)) -> active(f(x)) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 1149.31/291.51 The following defined symbols can occur below the 0th argument of f: chk, f, mat 1149.31/291.51 The following defined symbols can occur below the 0th argument of tp: chk, f, mat 1149.31/291.51 The following defined symbols can occur below the 0th argument of chk: chk, f, mat 1149.31/291.51 The following defined symbols can occur below the 0th argument of mat: chk, f, mat 1149.31/291.51 The following defined symbols can occur below the 1th argument of mat: chk, f, mat 1149.31/291.51 1149.31/291.51 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 1149.31/291.51 active(f(x)) -> mark(f(f(x))) 1149.31/291.51 f(active(x)) -> active(f(x)) 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (2) 1149.31/291.51 Obligation: 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 1149.31/291.51 transformed relative TRS to TRS 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (4) 1149.31/291.51 Obligation: 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (5) CpxTrsMatchBoundsTAProof (FINISHED) 1149.31/291.51 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 1149.31/291.51 1149.31/291.51 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 1149.31/291.51 final states : [1, 2, 3, 4] 1149.31/291.51 transitions: 1149.31/291.51 no0(0) -> 0 1149.31/291.51 X0() -> 0 1149.31/291.51 y0() -> 0 1149.31/291.51 c0() -> 0 1149.31/291.51 active0(0) -> 0 1149.31/291.51 mark0(0) -> 0 1149.31/291.51 chk0(0) -> 1 1149.31/291.51 mat0(0, 0) -> 2 1149.31/291.51 f0(0) -> 3 1149.31/291.51 tp0(0) -> 4 1149.31/291.51 c1() -> 5 1149.31/291.51 active1(5) -> 1 1149.31/291.51 f1(0) -> 6 1149.31/291.51 no1(6) -> 3 1149.31/291.51 f1(0) -> 7 1149.31/291.51 mark1(7) -> 3 1149.31/291.51 X1() -> 13 1149.31/291.51 f1(13) -> 12 1149.31/291.51 f1(12) -> 11 1149.31/291.51 f1(11) -> 11 1149.31/291.51 f1(11) -> 10 1149.31/291.51 mat1(10, 0) -> 9 1149.31/291.51 chk1(9) -> 8 1149.31/291.51 tp1(8) -> 4 1149.31/291.51 c1() -> 14 1149.31/291.51 no1(14) -> 9 1149.31/291.51 no1(6) -> 6 1149.31/291.51 no1(6) -> 7 1149.31/291.51 mark1(7) -> 6 1149.31/291.51 mark1(7) -> 7 1149.31/291.51 c2() -> 15 1149.31/291.51 active2(15) -> 8 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (6) 1149.31/291.51 BOUNDS(1, n^1) 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1149.31/291.51 Transformed a relative TRS into a decreasing-loop problem. 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (8) 1149.31/291.51 Obligation: 1149.31/291.51 Analyzing the following TRS for decreasing loops: 1149.31/291.51 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 active(f(x)) -> mark(f(f(x))) 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(active(x)) -> active(f(x)) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (9) DecreasingLoopProof (LOWER BOUND(ID)) 1149.31/291.51 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1149.31/291.51 1149.31/291.51 The rewrite sequence 1149.31/291.51 1149.31/291.51 f(no(x)) ->^+ no(f(x)) 1149.31/291.51 1149.31/291.51 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1149.31/291.51 1149.31/291.51 The pumping substitution is [x / no(x)]. 1149.31/291.51 1149.31/291.51 The result substitution is [ ]. 1149.31/291.51 1149.31/291.51 1149.31/291.51 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (10) 1149.31/291.51 Complex Obligation (BEST) 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (11) 1149.31/291.51 Obligation: 1149.31/291.51 Proved the lower bound n^1 for the following obligation: 1149.31/291.51 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 active(f(x)) -> mark(f(f(x))) 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(active(x)) -> active(f(x)) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (12) LowerBoundPropagationProof (FINISHED) 1149.31/291.51 Propagated lower bound. 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (13) 1149.31/291.51 BOUNDS(n^1, INF) 1149.31/291.51 1149.31/291.51 ---------------------------------------- 1149.31/291.51 1149.31/291.51 (14) 1149.31/291.51 Obligation: 1149.31/291.51 Analyzing the following TRS for decreasing loops: 1149.31/291.51 1149.31/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1149.31/291.51 1149.31/291.51 1149.31/291.51 The TRS R consists of the following rules: 1149.31/291.51 1149.31/291.51 active(f(x)) -> mark(f(f(x))) 1149.31/291.51 chk(no(f(x))) -> f(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 mat(f(x), f(y)) -> f(mat(x, y)) 1149.31/291.51 chk(no(c)) -> active(c) 1149.31/291.51 mat(f(x), c) -> no(c) 1149.31/291.51 f(active(x)) -> active(f(x)) 1149.31/291.51 f(no(x)) -> no(f(x)) 1149.31/291.51 f(mark(x)) -> mark(f(x)) 1149.31/291.51 tp(mark(x)) -> tp(chk(mat(f(f(f(f(f(f(f(f(f(f(X)))))))))), x))) 1149.31/291.51 1149.31/291.51 S is empty. 1149.31/291.51 Rewrite Strategy: FULL 1149.64/291.69 EOF