4.05/1.85 WORST_CASE(Omega(n^1), O(n^1)) 4.05/1.86 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.05/1.86 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.05/1.86 4.05/1.86 4.05/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.05/1.86 4.05/1.86 (0) CpxTRS 4.05/1.86 (1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 4.05/1.86 (2) CpxTRS 4.05/1.86 (3) CpxTrsMatchBoundsTAProof [FINISHED, 89 ms] 4.05/1.86 (4) BOUNDS(1, n^1) 4.05/1.86 (5) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 4.05/1.86 (6) TRS for Loop Detection 4.05/1.86 (7) DecreasingLoopProof [LOWER BOUND(ID), 31 ms] 4.05/1.86 (8) BEST 4.05/1.86 (9) proven lower bound 4.05/1.86 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 4.05/1.86 (11) BOUNDS(n^1, INF) 4.05/1.86 (12) TRS for Loop Detection 4.05/1.86 4.05/1.86 4.05/1.86 ---------------------------------------- 4.05/1.86 4.05/1.86 (0) 4.05/1.86 Obligation: 4.05/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.05/1.86 4.05/1.86 4.05/1.86 The TRS R consists of the following rules: 4.05/1.86 4.05/1.86 group3(@l) -> group3#1(@l) 4.05/1.86 group3#1(::(@x, @xs)) -> group3#2(@xs, @x) 4.05/1.86 group3#1(nil) -> nil 4.05/1.86 group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y) 4.05/1.86 group3#2(nil, @x) -> nil 4.05/1.86 group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs)) 4.05/1.86 group3#3(nil, @x, @y) -> nil 4.05/1.86 zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3) 4.05/1.86 zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs) 4.05/1.86 zip3#1(nil, @l2, @l3) -> nil 4.05/1.86 zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys) 4.05/1.86 zip3#2(nil, @l3, @x, @xs) -> nil 4.05/1.86 zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs)) 4.05/1.86 zip3#3(nil, @x, @xs, @y, @ys) -> nil 4.05/1.86 4.05/1.86 S is empty. 4.05/1.86 Rewrite Strategy: INNERMOST 4.05/1.86 ---------------------------------------- 4.05/1.86 4.05/1.86 (1) RelTrsToTrsProof (UPPER BOUND(ID)) 4.05/1.86 transformed relative TRS to TRS 4.05/1.86 ---------------------------------------- 4.05/1.86 4.05/1.86 (2) 4.05/1.86 Obligation: 4.05/1.86 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 4.05/1.86 4.05/1.86 4.05/1.86 The TRS R consists of the following rules: 4.05/1.86 4.05/1.86 group3(@l) -> group3#1(@l) 4.05/1.86 group3#1(::(@x, @xs)) -> group3#2(@xs, @x) 4.05/1.86 group3#1(nil) -> nil 4.05/1.86 group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y) 4.05/1.86 group3#2(nil, @x) -> nil 4.05/1.86 group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs)) 4.05/1.86 group3#3(nil, @x, @y) -> nil 4.05/1.86 zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3) 4.05/1.86 zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs) 4.05/1.86 zip3#1(nil, @l2, @l3) -> nil 4.05/1.86 zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys) 4.05/1.86 zip3#2(nil, @l3, @x, @xs) -> nil 4.05/1.86 zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs)) 4.05/1.86 zip3#3(nil, @x, @xs, @y, @ys) -> nil 4.05/1.86 4.05/1.86 S is empty. 4.05/1.86 Rewrite Strategy: INNERMOST 4.05/1.86 ---------------------------------------- 4.05/1.86 4.05/1.86 (3) CpxTrsMatchBoundsTAProof (FINISHED) 4.05/1.86 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. 4.05/1.86 4.05/1.86 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 4.05/1.86 final states : [1, 2, 3, 4, 5, 6, 7, 8] 4.05/1.86 transitions: 4.05/1.86 ::0(0, 0) -> 0 4.05/1.87 nil0() -> 0 4.05/1.87 tuple#30(0, 0, 0) -> 0 4.05/1.87 group30(0) -> 1 4.05/1.87 group3#10(0) -> 2 4.05/1.87 group3#20(0, 0) -> 3 4.05/1.87 group3#30(0, 0, 0) -> 4 4.05/1.87 zip30(0, 0, 0) -> 5 4.05/1.87 zip3#10(0, 0, 0) -> 6 4.05/1.87 zip3#20(0, 0, 0, 0) -> 7 4.05/1.87 zip3#30(0, 0, 0, 0, 0) -> 8 4.05/1.87 group3#11(0) -> 1 4.05/1.87 group3#21(0, 0) -> 2 4.05/1.87 nil1() -> 2 4.05/1.87 group3#31(0, 0, 0) -> 3 4.05/1.87 nil1() -> 3 4.05/1.87 tuple#31(0, 0, 0) -> 9 4.05/1.87 group31(0) -> 10 4.05/1.87 ::1(9, 10) -> 4 4.05/1.87 nil1() -> 4 4.05/1.87 zip3#11(0, 0, 0) -> 5 4.05/1.87 zip3#21(0, 0, 0, 0) -> 6 4.05/1.87 nil1() -> 6 4.05/1.87 zip3#31(0, 0, 0, 0, 0) -> 7 4.05/1.87 nil1() -> 7 4.05/1.87 zip31(0, 0, 0) -> 11 4.05/1.87 ::1(9, 11) -> 8 4.05/1.87 nil1() -> 8 4.05/1.87 group3#12(0) -> 10 4.05/1.87 group3#21(0, 0) -> 1 4.05/1.87 nil1() -> 1 4.05/1.87 group3#31(0, 0, 0) -> 2 4.05/1.87 ::1(9, 10) -> 3 4.05/1.87 zip3#12(0, 0, 0) -> 11 4.05/1.87 zip3#21(0, 0, 0, 0) -> 5 4.05/1.87 nil1() -> 5 4.05/1.87 zip3#31(0, 0, 0, 0, 0) -> 6 4.05/1.87 ::1(9, 11) -> 7 4.05/1.87 group3#31(0, 0, 0) -> 1 4.05/1.87 ::1(9, 10) -> 2 4.05/1.87 zip3#31(0, 0, 0, 0, 0) -> 5 4.05/1.87 ::1(9, 11) -> 6 4.05/1.87 group3#21(0, 0) -> 10 4.05/1.87 nil1() -> 10 4.05/1.87 zip3#21(0, 0, 0, 0) -> 11 4.05/1.87 nil1() -> 11 4.05/1.87 group3#31(0, 0, 0) -> 10 4.05/1.87 ::1(9, 10) -> 1 4.05/1.87 zip3#31(0, 0, 0, 0, 0) -> 11 4.05/1.87 ::1(9, 11) -> 5 4.05/1.87 ::1(9, 10) -> 10 4.05/1.87 ::1(9, 11) -> 11 4.05/1.87 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (4) 4.05/1.87 BOUNDS(1, n^1) 4.05/1.87 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (5) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 4.05/1.87 Transformed a relative TRS into a decreasing-loop problem. 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (6) 4.05/1.87 Obligation: 4.05/1.87 Analyzing the following TRS for decreasing loops: 4.05/1.87 4.05/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.05/1.87 4.05/1.87 4.05/1.87 The TRS R consists of the following rules: 4.05/1.87 4.05/1.87 group3(@l) -> group3#1(@l) 4.05/1.87 group3#1(::(@x, @xs)) -> group3#2(@xs, @x) 4.05/1.87 group3#1(nil) -> nil 4.05/1.87 group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y) 4.05/1.87 group3#2(nil, @x) -> nil 4.05/1.87 group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs)) 4.05/1.87 group3#3(nil, @x, @y) -> nil 4.05/1.87 zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3) 4.05/1.87 zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs) 4.05/1.87 zip3#1(nil, @l2, @l3) -> nil 4.05/1.87 zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys) 4.05/1.87 zip3#2(nil, @l3, @x, @xs) -> nil 4.05/1.87 zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs)) 4.05/1.87 zip3#3(nil, @x, @xs, @y, @ys) -> nil 4.05/1.87 4.05/1.87 S is empty. 4.05/1.87 Rewrite Strategy: INNERMOST 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (7) DecreasingLoopProof (LOWER BOUND(ID)) 4.05/1.87 The following loop(s) give(s) rise to the lower bound Omega(n^1): 4.05/1.87 4.05/1.87 The rewrite sequence 4.05/1.87 4.05/1.87 group3#2(::(@y, ::(@z1_0, ::(@x1_1, @xs2_1))), @x) ->^+ ::(tuple#3(@x, @y, @z1_0), group3#2(@xs2_1, @x1_1)) 4.05/1.87 4.05/1.87 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 4.05/1.87 4.05/1.87 The pumping substitution is [@xs2_1 / ::(@y, ::(@z1_0, ::(@x1_1, @xs2_1)))]. 4.05/1.87 4.05/1.87 The result substitution is [@x / @x1_1]. 4.05/1.87 4.05/1.87 4.05/1.87 4.05/1.87 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (8) 4.05/1.87 Complex Obligation (BEST) 4.05/1.87 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (9) 4.05/1.87 Obligation: 4.05/1.87 Proved the lower bound n^1 for the following obligation: 4.05/1.87 4.05/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.05/1.87 4.05/1.87 4.05/1.87 The TRS R consists of the following rules: 4.05/1.87 4.05/1.87 group3(@l) -> group3#1(@l) 4.05/1.87 group3#1(::(@x, @xs)) -> group3#2(@xs, @x) 4.05/1.87 group3#1(nil) -> nil 4.05/1.87 group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y) 4.05/1.87 group3#2(nil, @x) -> nil 4.05/1.87 group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs)) 4.05/1.87 group3#3(nil, @x, @y) -> nil 4.05/1.87 zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3) 4.05/1.87 zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs) 4.05/1.87 zip3#1(nil, @l2, @l3) -> nil 4.05/1.87 zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys) 4.05/1.87 zip3#2(nil, @l3, @x, @xs) -> nil 4.05/1.87 zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs)) 4.05/1.87 zip3#3(nil, @x, @xs, @y, @ys) -> nil 4.05/1.87 4.05/1.87 S is empty. 4.05/1.87 Rewrite Strategy: INNERMOST 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (10) LowerBoundPropagationProof (FINISHED) 4.05/1.87 Propagated lower bound. 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (11) 4.05/1.87 BOUNDS(n^1, INF) 4.05/1.87 4.05/1.87 ---------------------------------------- 4.05/1.87 4.05/1.87 (12) 4.05/1.87 Obligation: 4.05/1.87 Analyzing the following TRS for decreasing loops: 4.05/1.87 4.05/1.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 4.05/1.87 4.05/1.87 4.05/1.87 The TRS R consists of the following rules: 4.05/1.87 4.05/1.87 group3(@l) -> group3#1(@l) 4.05/1.87 group3#1(::(@x, @xs)) -> group3#2(@xs, @x) 4.05/1.87 group3#1(nil) -> nil 4.05/1.87 group3#2(::(@y, @ys), @x) -> group3#3(@ys, @x, @y) 4.05/1.87 group3#2(nil, @x) -> nil 4.05/1.87 group3#3(::(@z, @zs), @x, @y) -> ::(tuple#3(@x, @y, @z), group3(@zs)) 4.05/1.87 group3#3(nil, @x, @y) -> nil 4.05/1.87 zip3(@l1, @l2, @l3) -> zip3#1(@l1, @l2, @l3) 4.05/1.87 zip3#1(::(@x, @xs), @l2, @l3) -> zip3#2(@l2, @l3, @x, @xs) 4.05/1.87 zip3#1(nil, @l2, @l3) -> nil 4.05/1.87 zip3#2(::(@y, @ys), @l3, @x, @xs) -> zip3#3(@l3, @x, @xs, @y, @ys) 4.05/1.87 zip3#2(nil, @l3, @x, @xs) -> nil 4.05/1.87 zip3#3(::(@z, @zs), @x, @xs, @y, @ys) -> ::(tuple#3(@x, @y, @z), zip3(@xs, @ys, @zs)) 4.05/1.87 zip3#3(nil, @x, @xs, @y, @ys) -> nil 4.05/1.87 4.05/1.87 S is empty. 4.05/1.87 Rewrite Strategy: INNERMOST 4.24/1.97 EOF