1094.63/291.57 WORST_CASE(Omega(n^1), ?) 1112.82/296.17 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1112.82/296.17 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1112.82/296.17 1112.82/296.17 1112.82/296.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1112.82/296.17 1112.82/296.17 (0) CpxTRS 1112.82/296.17 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1112.82/296.17 (2) TRS for Loop Detection 1112.82/296.17 (3) DecreasingLoopProof [LOWER BOUND(ID), 86 ms] 1112.82/296.17 (4) BEST 1112.82/296.17 (5) proven lower bound 1112.82/296.17 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1112.82/296.17 (7) BOUNDS(n^1, INF) 1112.82/296.17 (8) TRS for Loop Detection 1112.82/296.17 1112.82/296.17 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (0) 1112.82/296.17 Obligation: 1112.82/296.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1112.82/296.17 1112.82/296.17 1112.82/296.17 The TRS R consists of the following rules: 1112.82/296.17 1112.82/296.17 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 1112.82/296.17 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 1112.82/296.17 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 1112.82/296.17 breadth#2(nil, @queue') -> nil 1112.82/296.17 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 1112.82/296.17 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 1112.82/296.17 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 1112.82/296.17 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 1112.82/296.17 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 1112.82/296.17 children#1(nil, @b, @l2) -> children#2(@l2, @b) 1112.82/296.17 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 1112.82/296.17 children#2(nil, @b) -> nil 1112.82/296.17 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 1112.82/296.17 children#3(nil, @b, @x, @xs) -> nil 1112.82/296.17 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 1112.82/296.17 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 1112.82/296.17 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 1112.82/296.17 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 1112.82/296.17 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 1112.82/296.17 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 1112.82/296.17 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 1112.82/296.17 dequeue#2(nil, @inq) -> dequeue#3(@inq) 1112.82/296.17 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 1112.82/296.17 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 1112.82/296.17 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 1112.82/296.17 empty(@x) -> tuple#2(nil, nil) 1112.82/296.17 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 1112.82/296.17 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 1112.82/296.17 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 1112.82/296.17 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 1112.82/296.17 enqueues#1(nil, @queue) -> @queue 1112.82/296.17 startBreadth(@xs) -> startBreadth#1(@xs) 1112.82/296.17 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 1112.82/296.17 startBreadth#1(nil) -> nil 1112.82/296.17 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 1112.82/296.17 1112.82/296.17 S is empty. 1112.82/296.17 Rewrite Strategy: INNERMOST 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1112.82/296.17 Transformed a relative TRS into a decreasing-loop problem. 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (2) 1112.82/296.17 Obligation: 1112.82/296.17 Analyzing the following TRS for decreasing loops: 1112.82/296.17 1112.82/296.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1112.82/296.17 1112.82/296.17 1112.82/296.17 The TRS R consists of the following rules: 1112.82/296.17 1112.82/296.17 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 1112.82/296.17 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 1112.82/296.17 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 1112.82/296.17 breadth#2(nil, @queue') -> nil 1112.82/296.17 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 1112.82/296.17 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 1112.82/296.17 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 1112.82/296.17 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 1112.82/296.17 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 1112.82/296.17 children#1(nil, @b, @l2) -> children#2(@l2, @b) 1112.82/296.17 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 1112.82/296.17 children#2(nil, @b) -> nil 1112.82/296.17 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 1112.82/296.17 children#3(nil, @b, @x, @xs) -> nil 1112.82/296.17 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 1112.82/296.17 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 1112.82/296.17 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 1112.82/296.17 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 1112.82/296.17 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 1112.82/296.17 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 1112.82/296.17 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 1112.82/296.17 dequeue#2(nil, @inq) -> dequeue#3(@inq) 1112.82/296.17 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 1112.82/296.17 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 1112.82/296.17 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 1112.82/296.17 empty(@x) -> tuple#2(nil, nil) 1112.82/296.17 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 1112.82/296.17 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 1112.82/296.17 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 1112.82/296.17 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 1112.82/296.17 enqueues#1(nil, @queue) -> @queue 1112.82/296.17 startBreadth(@xs) -> startBreadth#1(@xs) 1112.82/296.17 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 1112.82/296.17 startBreadth#1(nil) -> nil 1112.82/296.17 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 1112.82/296.17 1112.82/296.17 S is empty. 1112.82/296.17 Rewrite Strategy: INNERMOST 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1112.82/296.17 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1112.82/296.17 1112.82/296.17 The rewrite sequence 1112.82/296.17 1112.82/296.17 enqueues(::(@x1_0, @xs2_0), @queue) ->^+ enqueues(@xs2_0, enqueue(@x1_0, @queue)) 1112.82/296.17 1112.82/296.17 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1112.82/296.17 1112.82/296.17 The pumping substitution is [@xs2_0 / ::(@x1_0, @xs2_0)]. 1112.82/296.17 1112.82/296.17 The result substitution is [@queue / enqueue(@x1_0, @queue)]. 1112.82/296.17 1112.82/296.17 1112.82/296.17 1112.82/296.17 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (4) 1112.82/296.17 Complex Obligation (BEST) 1112.82/296.17 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (5) 1112.82/296.17 Obligation: 1112.82/296.17 Proved the lower bound n^1 for the following obligation: 1112.82/296.17 1112.82/296.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1112.82/296.17 1112.82/296.17 1112.82/296.17 The TRS R consists of the following rules: 1112.82/296.17 1112.82/296.17 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 1112.82/296.17 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 1112.82/296.17 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 1112.82/296.17 breadth#2(nil, @queue') -> nil 1112.82/296.17 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 1112.82/296.17 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 1112.82/296.17 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 1112.82/296.17 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 1112.82/296.17 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 1112.82/296.17 children#1(nil, @b, @l2) -> children#2(@l2, @b) 1112.82/296.17 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 1112.82/296.17 children#2(nil, @b) -> nil 1112.82/296.17 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 1112.82/296.17 children#3(nil, @b, @x, @xs) -> nil 1112.82/296.17 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 1112.82/296.17 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 1112.82/296.17 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 1112.82/296.17 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 1112.82/296.17 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 1112.82/296.17 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 1112.82/296.17 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 1112.82/296.17 dequeue#2(nil, @inq) -> dequeue#3(@inq) 1112.82/296.17 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 1112.82/296.17 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 1112.82/296.17 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 1112.82/296.17 empty(@x) -> tuple#2(nil, nil) 1112.82/296.17 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 1112.82/296.17 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 1112.82/296.17 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 1112.82/296.17 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 1112.82/296.17 enqueues#1(nil, @queue) -> @queue 1112.82/296.17 startBreadth(@xs) -> startBreadth#1(@xs) 1112.82/296.17 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 1112.82/296.17 startBreadth#1(nil) -> nil 1112.82/296.17 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 1112.82/296.17 1112.82/296.17 S is empty. 1112.82/296.17 Rewrite Strategy: INNERMOST 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (6) LowerBoundPropagationProof (FINISHED) 1112.82/296.17 Propagated lower bound. 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (7) 1112.82/296.17 BOUNDS(n^1, INF) 1112.82/296.17 1112.82/296.17 ---------------------------------------- 1112.82/296.17 1112.82/296.17 (8) 1112.82/296.17 Obligation: 1112.82/296.17 Analyzing the following TRS for decreasing loops: 1112.82/296.17 1112.82/296.17 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1112.82/296.17 1112.82/296.17 1112.82/296.17 The TRS R consists of the following rules: 1112.82/296.17 1112.82/296.17 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 1112.82/296.17 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 1112.82/296.17 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 1112.82/296.17 breadth#2(nil, @queue') -> nil 1112.82/296.17 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 1112.82/296.17 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 1112.82/296.17 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 1112.82/296.17 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 1112.82/296.17 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 1112.82/296.17 children#1(nil, @b, @l2) -> children#2(@l2, @b) 1112.82/296.17 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 1112.82/296.17 children#2(nil, @b) -> nil 1112.82/296.17 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 1112.82/296.17 children#3(nil, @b, @x, @xs) -> nil 1112.82/296.17 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 1112.82/296.17 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 1112.82/296.17 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 1112.82/296.17 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 1112.82/296.17 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 1112.82/296.17 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 1112.82/296.17 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 1112.82/296.17 dequeue#2(nil, @inq) -> dequeue#3(@inq) 1112.82/296.17 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 1112.82/296.17 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 1112.82/296.17 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 1112.82/296.17 empty(@x) -> tuple#2(nil, nil) 1112.82/296.17 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 1112.82/296.17 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 1112.82/296.17 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 1112.82/296.17 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 1112.82/296.17 enqueues#1(nil, @queue) -> @queue 1112.82/296.17 startBreadth(@xs) -> startBreadth#1(@xs) 1112.82/296.17 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 1112.82/296.17 startBreadth#1(nil) -> nil 1112.82/296.17 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 1112.82/296.17 1112.82/296.17 S is empty. 1112.82/296.17 Rewrite Strategy: INNERMOST 1113.22/296.23 EOF