13.14/4.61 YES 13.36/4.63 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 13.36/4.63 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.36/4.63 13.36/4.63 13.36/4.63 Termination w.r.t. Q of the given QTRS could be proven: 13.36/4.63 13.36/4.63 (0) QTRS 13.36/4.63 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 13.36/4.63 (2) QDP 13.36/4.63 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 13.36/4.63 (4) AND 13.36/4.63 (5) QDP 13.36/4.63 (6) UsableRulesProof [EQUIVALENT, 0 ms] 13.36/4.63 (7) QDP 13.36/4.63 (8) QReductionProof [EQUIVALENT, 1 ms] 13.36/4.63 (9) QDP 13.36/4.63 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.36/4.63 (11) YES 13.36/4.63 (12) QDP 13.36/4.63 (13) UsableRulesProof [EQUIVALENT, 0 ms] 13.36/4.63 (14) QDP 13.36/4.63 (15) QReductionProof [EQUIVALENT, 1 ms] 13.36/4.63 (16) QDP 13.36/4.63 (17) MRRProof [EQUIVALENT, 0 ms] 13.36/4.63 (18) QDP 13.36/4.63 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 13.36/4.63 (20) TRUE 13.36/4.63 (21) QDP 13.36/4.63 (22) UsableRulesProof [EQUIVALENT, 0 ms] 13.36/4.63 (23) QDP 13.36/4.63 (24) QReductionProof [EQUIVALENT, 1 ms] 13.36/4.63 (25) QDP 13.36/4.63 (26) MRRProof [EQUIVALENT, 0 ms] 13.36/4.63 (27) QDP 13.36/4.63 (28) QDPOrderProof [EQUIVALENT, 13 ms] 13.36/4.63 (29) QDP 13.36/4.63 (30) DependencyGraphProof [EQUIVALENT, 0 ms] 13.36/4.63 (31) TRUE 13.36/4.63 (32) QDP 13.36/4.63 (33) UsableRulesProof [EQUIVALENT, 0 ms] 13.36/4.63 (34) QDP 13.36/4.63 (35) QReductionProof [EQUIVALENT, 0 ms] 13.36/4.63 (36) QDP 13.36/4.63 (37) QDPOrderProof [EQUIVALENT, 61 ms] 13.36/4.63 (38) QDP 13.36/4.63 (39) DependencyGraphProof [EQUIVALENT, 0 ms] 13.36/4.63 (40) TRUE 13.36/4.63 13.36/4.63 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (0) 13.36/4.63 Obligation: 13.36/4.63 Q restricted rewrite system: 13.36/4.63 The TRS R consists of the following rules: 13.36/4.63 13.36/4.63 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.63 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.63 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.63 breadth#2(nil, @queue') -> nil 13.36/4.63 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.63 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.63 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.63 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.63 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.63 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.63 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.63 children#2(nil, @b) -> nil 13.36/4.63 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.63 children#3(nil, @b, @x, @xs) -> nil 13.36/4.63 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.63 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.63 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.63 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.63 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.63 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.63 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.63 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.63 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.63 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.63 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.63 empty(@x) -> tuple#2(nil, nil) 13.36/4.63 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.63 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.63 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.63 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.63 enqueues#1(nil, @queue) -> @queue 13.36/4.63 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.63 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.63 startBreadth#1(nil) -> nil 13.36/4.63 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.63 13.36/4.63 The set Q consists of the following terms: 13.36/4.63 13.36/4.63 breadth(x0, x1) 13.36/4.63 breadth#1(tuple#2(x0, x1)) 13.36/4.63 breadth#2(::(x0, x1), x2) 13.36/4.63 breadth#2(nil, x0) 13.36/4.63 breadth#3(tuple#2(x0, x1), x2) 13.36/4.63 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.63 breadth#5(tuple#2(x0, x1)) 13.36/4.63 children(x0, x1, x2, x3) 13.36/4.63 children#1(::(x0, x1), x2, x3) 13.36/4.63 children#1(nil, x0, x1) 13.36/4.63 children#2(::(x0, x1), x2) 13.36/4.63 children#2(nil, x0) 13.36/4.63 children#3(::(x0, x1), x2, x3, x4) 13.36/4.63 children#3(nil, x0, x1, x2) 13.36/4.63 copyover(x0, x1) 13.36/4.63 copyover#1(tuple#2(x0, x1)) 13.36/4.63 copyover#2(::(x0, x1), x2) 13.36/4.63 copyover#2(nil, x0) 13.36/4.63 dequeue(x0, x1) 13.36/4.63 dequeue#1(tuple#2(x0, x1)) 13.36/4.63 dequeue#2(::(x0, x1), x2) 13.36/4.63 dequeue#2(nil, x0) 13.36/4.63 dequeue#3(::(x0, x1)) 13.36/4.63 dequeue#3(nil) 13.36/4.63 dequeue#4(tuple#2(x0, x1)) 13.36/4.63 empty(x0) 13.36/4.63 enqueue(x0, x1) 13.36/4.63 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.63 enqueues(x0, x1) 13.36/4.63 enqueues#1(::(x0, x1), x2) 13.36/4.63 enqueues#1(nil, x0) 13.36/4.63 startBreadth(x0) 13.36/4.63 startBreadth#1(::(x0, x1)) 13.36/4.63 startBreadth#1(nil) 13.36/4.63 startBreadth#2(tuple#2(x0, x1)) 13.36/4.63 13.36/4.63 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (1) DependencyPairsProof (EQUIVALENT) 13.36/4.63 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (2) 13.36/4.63 Obligation: 13.36/4.63 Q DP problem: 13.36/4.63 The TRS P consists of the following rules: 13.36/4.63 13.36/4.63 BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.63 BREADTH(@breadth@1, @breadth@2) -> DEQUEUE(@breadth@1, @breadth@2) 13.36/4.63 BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue') 13.36/4.63 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue') 13.36/4.63 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#4(@z) 13.36/4.63 BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue')) 13.36/4.63 BREADTH#3(tuple#2(@x, @ys), @queue') -> ENQUEUES(@ys, @queue') 13.36/4.63 BREADTH#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> CHILDREN(@children@3, @children@4, @children@5, @children@6) 13.36/4.63 BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8) 13.36/4.63 CHILDREN(@a, @b, @l1, @l2) -> CHILDREN#1(@l1, @b, @l2) 13.36/4.63 CHILDREN#1(::(@x, @xs), @b, @l2) -> CHILDREN#3(@l2, @b, @x, @xs) 13.36/4.63 CHILDREN#1(nil, @b, @l2) -> CHILDREN#2(@l2, @b) 13.36/4.63 COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.63 COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq) 13.36/4.63 COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq)) 13.36/4.63 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.63 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.63 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.63 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.63 DEQUEUE#3(::(@x, @xs)) -> COPYOVER(::(@x, @xs), nil) 13.36/4.63 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.63 ENQUEUE(@x, @queue) -> ENQUEUE#1(@queue, @x) 13.36/4.63 ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue) 13.36/4.63 ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue)) 13.36/4.63 ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUE(@x, @queue) 13.36/4.63 STARTBREADTH(@xs) -> STARTBREADTH#1(@xs) 13.36/4.63 STARTBREADTH#1(::(@x, @xs)) -> STARTBREADTH#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.63 STARTBREADTH#1(::(@x, @xs)) -> ENQUEUE(tuple#4(@x, @x, @xs, @xs), empty(#unit)) 13.36/4.63 STARTBREADTH#1(::(@x, @xs)) -> EMPTY(#unit) 13.36/4.63 STARTBREADTH#2(tuple#2(@breadth@1, @breadth@2)) -> BREADTH(@breadth@1, @breadth@2) 13.36/4.63 13.36/4.63 The TRS R consists of the following rules: 13.36/4.63 13.36/4.63 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.63 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.63 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.63 breadth#2(nil, @queue') -> nil 13.36/4.63 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.63 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.63 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.63 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.63 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.63 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.63 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.63 children#2(nil, @b) -> nil 13.36/4.63 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.63 children#3(nil, @b, @x, @xs) -> nil 13.36/4.63 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.63 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.63 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.63 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.63 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.63 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.63 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.63 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.63 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.63 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.63 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.63 empty(@x) -> tuple#2(nil, nil) 13.36/4.63 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.63 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.63 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.63 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.63 enqueues#1(nil, @queue) -> @queue 13.36/4.63 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.63 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.63 startBreadth#1(nil) -> nil 13.36/4.63 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.63 13.36/4.63 The set Q consists of the following terms: 13.36/4.63 13.36/4.63 breadth(x0, x1) 13.36/4.63 breadth#1(tuple#2(x0, x1)) 13.36/4.63 breadth#2(::(x0, x1), x2) 13.36/4.63 breadth#2(nil, x0) 13.36/4.63 breadth#3(tuple#2(x0, x1), x2) 13.36/4.63 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.63 breadth#5(tuple#2(x0, x1)) 13.36/4.63 children(x0, x1, x2, x3) 13.36/4.63 children#1(::(x0, x1), x2, x3) 13.36/4.63 children#1(nil, x0, x1) 13.36/4.63 children#2(::(x0, x1), x2) 13.36/4.63 children#2(nil, x0) 13.36/4.63 children#3(::(x0, x1), x2, x3, x4) 13.36/4.63 children#3(nil, x0, x1, x2) 13.36/4.63 copyover(x0, x1) 13.36/4.63 copyover#1(tuple#2(x0, x1)) 13.36/4.63 copyover#2(::(x0, x1), x2) 13.36/4.63 copyover#2(nil, x0) 13.36/4.63 dequeue(x0, x1) 13.36/4.63 dequeue#1(tuple#2(x0, x1)) 13.36/4.63 dequeue#2(::(x0, x1), x2) 13.36/4.63 dequeue#2(nil, x0) 13.36/4.63 dequeue#3(::(x0, x1)) 13.36/4.63 dequeue#3(nil) 13.36/4.63 dequeue#4(tuple#2(x0, x1)) 13.36/4.63 empty(x0) 13.36/4.63 enqueue(x0, x1) 13.36/4.63 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.63 enqueues(x0, x1) 13.36/4.63 enqueues#1(::(x0, x1), x2) 13.36/4.63 enqueues#1(nil, x0) 13.36/4.63 startBreadth(x0) 13.36/4.63 startBreadth#1(::(x0, x1)) 13.36/4.63 startBreadth#1(nil) 13.36/4.63 startBreadth#2(tuple#2(x0, x1)) 13.36/4.63 13.36/4.63 We have to consider all minimal (P,Q,R)-chains. 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (3) DependencyGraphProof (EQUIVALENT) 13.36/4.63 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 15 less nodes. 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (4) 13.36/4.63 Complex Obligation (AND) 13.36/4.63 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (5) 13.36/4.63 Obligation: 13.36/4.63 Q DP problem: 13.36/4.63 The TRS P consists of the following rules: 13.36/4.63 13.36/4.63 ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue)) 13.36/4.63 ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue) 13.36/4.63 13.36/4.63 The TRS R consists of the following rules: 13.36/4.63 13.36/4.63 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.63 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.63 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.63 breadth#2(nil, @queue') -> nil 13.36/4.63 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.63 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.63 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.63 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.63 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.63 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.63 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.63 children#2(nil, @b) -> nil 13.36/4.63 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.63 children#3(nil, @b, @x, @xs) -> nil 13.36/4.63 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.63 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.63 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.63 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.63 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.63 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.63 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.63 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.63 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.63 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.63 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.63 empty(@x) -> tuple#2(nil, nil) 13.36/4.63 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.63 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.63 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.63 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.63 enqueues#1(nil, @queue) -> @queue 13.36/4.63 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.63 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.63 startBreadth#1(nil) -> nil 13.36/4.63 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.63 13.36/4.63 The set Q consists of the following terms: 13.36/4.63 13.36/4.63 breadth(x0, x1) 13.36/4.63 breadth#1(tuple#2(x0, x1)) 13.36/4.63 breadth#2(::(x0, x1), x2) 13.36/4.63 breadth#2(nil, x0) 13.36/4.63 breadth#3(tuple#2(x0, x1), x2) 13.36/4.63 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.63 breadth#5(tuple#2(x0, x1)) 13.36/4.63 children(x0, x1, x2, x3) 13.36/4.63 children#1(::(x0, x1), x2, x3) 13.36/4.63 children#1(nil, x0, x1) 13.36/4.63 children#2(::(x0, x1), x2) 13.36/4.63 children#2(nil, x0) 13.36/4.63 children#3(::(x0, x1), x2, x3, x4) 13.36/4.63 children#3(nil, x0, x1, x2) 13.36/4.63 copyover(x0, x1) 13.36/4.63 copyover#1(tuple#2(x0, x1)) 13.36/4.63 copyover#2(::(x0, x1), x2) 13.36/4.63 copyover#2(nil, x0) 13.36/4.63 dequeue(x0, x1) 13.36/4.63 dequeue#1(tuple#2(x0, x1)) 13.36/4.63 dequeue#2(::(x0, x1), x2) 13.36/4.63 dequeue#2(nil, x0) 13.36/4.63 dequeue#3(::(x0, x1)) 13.36/4.63 dequeue#3(nil) 13.36/4.63 dequeue#4(tuple#2(x0, x1)) 13.36/4.63 empty(x0) 13.36/4.63 enqueue(x0, x1) 13.36/4.63 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.63 enqueues(x0, x1) 13.36/4.63 enqueues#1(::(x0, x1), x2) 13.36/4.63 enqueues#1(nil, x0) 13.36/4.63 startBreadth(x0) 13.36/4.63 startBreadth#1(::(x0, x1)) 13.36/4.63 startBreadth#1(nil) 13.36/4.63 startBreadth#2(tuple#2(x0, x1)) 13.36/4.63 13.36/4.63 We have to consider all minimal (P,Q,R)-chains. 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (6) UsableRulesProof (EQUIVALENT) 13.36/4.63 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 13.36/4.63 ---------------------------------------- 13.36/4.63 13.36/4.63 (7) 13.36/4.63 Obligation: 13.36/4.63 Q DP problem: 13.36/4.63 The TRS P consists of the following rules: 13.36/4.63 13.36/4.63 ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue)) 13.36/4.63 ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue) 13.36/4.63 13.36/4.63 The TRS R consists of the following rules: 13.36/4.63 13.36/4.63 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.63 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.63 13.36/4.63 The set Q consists of the following terms: 13.36/4.63 13.36/4.63 breadth(x0, x1) 13.36/4.63 breadth#1(tuple#2(x0, x1)) 13.36/4.63 breadth#2(::(x0, x1), x2) 13.36/4.63 breadth#2(nil, x0) 13.36/4.63 breadth#3(tuple#2(x0, x1), x2) 13.36/4.63 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.63 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (8) QReductionProof (EQUIVALENT) 13.36/4.64 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (9) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue)) 13.36/4.64 ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (10) QDPSizeChangeProof (EQUIVALENT) 13.36/4.64 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 13.36/4.64 13.36/4.64 From the DPs we obtained the following set of size-change graphs: 13.36/4.64 *ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue) 13.36/4.64 The graph contains the following edges 1 >= 1, 2 >= 2 13.36/4.64 13.36/4.64 13.36/4.64 *ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue)) 13.36/4.64 The graph contains the following edges 1 > 1 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (11) 13.36/4.64 YES 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (12) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq) 13.36/4.64 COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq)) 13.36/4.64 COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.64 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.64 breadth#2(nil, @queue') -> nil 13.36/4.64 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 empty(@x) -> tuple#2(nil, nil) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.64 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.64 startBreadth#1(nil) -> nil 13.36/4.64 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (13) UsableRulesProof (EQUIVALENT) 13.36/4.64 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (14) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq) 13.36/4.64 COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq)) 13.36/4.64 COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 13.36/4.64 R is empty. 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (15) QReductionProof (EQUIVALENT) 13.36/4.64 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (16) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq) 13.36/4.64 COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq)) 13.36/4.64 COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 13.36/4.64 R is empty. 13.36/4.64 Q is empty. 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (17) MRRProof (EQUIVALENT) 13.36/4.64 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 13.36/4.64 13.36/4.64 Strictly oriented dependency pairs: 13.36/4.64 13.36/4.64 COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq)) 13.36/4.64 COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 13.36/4.64 13.36/4.64 Used ordering: Polynomial interpretation [POLO]: 13.36/4.64 13.36/4.64 POL(::(x_1, x_2)) = 2 + 2*x_1 + x_2 13.36/4.64 POL(COPYOVER(x_1, x_2)) = 1 + 2*x_1 + x_2 13.36/4.64 POL(COPYOVER#1(x_1)) = x_1 13.36/4.64 POL(COPYOVER#2(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 POL(tuple#2(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (18) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq) 13.36/4.64 13.36/4.64 R is empty. 13.36/4.64 Q is empty. 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (19) DependencyGraphProof (EQUIVALENT) 13.36/4.64 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (20) 13.36/4.64 TRUE 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (21) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.64 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.64 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.64 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.64 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.64 breadth#2(nil, @queue') -> nil 13.36/4.64 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 empty(@x) -> tuple#2(nil, nil) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.64 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.64 startBreadth#1(nil) -> nil 13.36/4.64 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (22) UsableRulesProof (EQUIVALENT) 13.36/4.64 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (23) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.64 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.64 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.64 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (24) QReductionProof (EQUIVALENT) 13.36/4.64 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (25) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.64 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.64 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.64 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (26) MRRProof (EQUIVALENT) 13.36/4.64 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 13.36/4.64 13.36/4.64 13.36/4.64 Strictly oriented rules of the TRS R: 13.36/4.64 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 13.36/4.64 Used ordering: Polynomial interpretation [POLO]: 13.36/4.64 13.36/4.64 POL(::(x_1, x_2)) = 2 + 2*x_1 + x_2 13.36/4.64 POL(DEQUEUE(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 POL(DEQUEUE#1(x_1)) = x_1 13.36/4.64 POL(DEQUEUE#2(x_1, x_2)) = x_1 + 2*x_2 13.36/4.64 POL(DEQUEUE#3(x_1)) = 2*x_1 13.36/4.64 POL(DEQUEUE#4(x_1)) = x_1 13.36/4.64 POL(copyover(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 POL(copyover#1(x_1)) = x_1 13.36/4.64 POL(copyover#2(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 POL(nil) = 0 13.36/4.64 POL(tuple#2(x_1, x_2)) = 2*x_1 + x_2 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (27) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.64 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.64 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.64 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (28) QDPOrderProof (EQUIVALENT) 13.36/4.64 We use the reduction pair processor [LPAR04,JAR06]. 13.36/4.64 13.36/4.64 13.36/4.64 The following pairs can be oriented strictly and are deleted. 13.36/4.64 13.36/4.64 DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil)) 13.36/4.64 DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq) 13.36/4.64 The remaining pairs can at least be oriented weakly. 13.36/4.64 Used ordering: Combined order from the following AFS and order. 13.36/4.64 DEQUEUE#3(x1) = DEQUEUE#3(x1) 13.36/4.64 13.36/4.64 ::(x1, x2) = ::(x1, x2) 13.36/4.64 13.36/4.64 DEQUEUE#4(x1) = DEQUEUE#4(x1) 13.36/4.64 13.36/4.64 copyover(x1, x2) = x2 13.36/4.64 13.36/4.64 nil = nil 13.36/4.64 13.36/4.64 tuple#2(x1, x2) = x1 13.36/4.64 13.36/4.64 DEQUEUE(x1, x2) = DEQUEUE(x1) 13.36/4.64 13.36/4.64 DEQUEUE#1(x1) = DEQUEUE#1(x1) 13.36/4.64 13.36/4.64 DEQUEUE#2(x1, x2) = DEQUEUE#2(x2) 13.36/4.64 13.36/4.64 copyover#1(x1) = copyover#1 13.36/4.64 13.36/4.64 copyover#2(x1, x2) = copyover#2 13.36/4.64 13.36/4.64 13.36/4.64 Recursive path order with status [RPO]. 13.36/4.64 Quasi-Precedence: [::_2, DEQUEUE#4_1, DEQUEUE_1, DEQUEUE#1_1] > [DEQUEUE#3_1, DEQUEUE#2_1] > [nil, copyover#1, copyover#2] 13.36/4.64 13.36/4.64 Status: DEQUEUE#3_1: [1] 13.36/4.64 ::_2: [2,1] 13.36/4.64 DEQUEUE#4_1: [1] 13.36/4.64 nil: multiset status 13.36/4.64 DEQUEUE_1: [1] 13.36/4.64 DEQUEUE#1_1: [1] 13.36/4.64 DEQUEUE#2_1: [1] 13.36/4.64 copyover#1: multiset status 13.36/4.64 copyover#2: multiset status 13.36/4.64 13.36/4.64 13.36/4.64 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 13.36/4.64 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (29) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4) 13.36/4.64 DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (30) DependencyGraphProof (EQUIVALENT) 13.36/4.64 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (31) 13.36/4.64 TRUE 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (32) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue') 13.36/4.64 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue') 13.36/4.64 BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue')) 13.36/4.64 BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8) 13.36/4.64 BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue') 13.36/4.64 breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue') 13.36/4.64 breadth#2(nil, @queue') -> nil 13.36/4.64 breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue'))) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 empty(@x) -> tuple#2(nil, nil) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 startBreadth(@xs) -> startBreadth#1(@xs) 13.36/4.64 startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit))) 13.36/4.64 startBreadth#1(nil) -> nil 13.36/4.64 startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2) 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (33) UsableRulesProof (EQUIVALENT) 13.36/4.64 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (34) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue') 13.36/4.64 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue') 13.36/4.64 BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue')) 13.36/4.64 BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8) 13.36/4.64 BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (35) QReductionProof (EQUIVALENT) 13.36/4.64 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.36/4.64 13.36/4.64 breadth(x0, x1) 13.36/4.64 breadth#1(tuple#2(x0, x1)) 13.36/4.64 breadth#2(::(x0, x1), x2) 13.36/4.64 breadth#2(nil, x0) 13.36/4.64 breadth#3(tuple#2(x0, x1), x2) 13.36/4.64 breadth#5(tuple#2(x0, x1)) 13.36/4.64 empty(x0) 13.36/4.64 startBreadth(x0) 13.36/4.64 startBreadth#1(::(x0, x1)) 13.36/4.64 startBreadth#1(nil) 13.36/4.64 startBreadth#2(tuple#2(x0, x1)) 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (36) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue') 13.36/4.64 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue') 13.36/4.64 BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue')) 13.36/4.64 BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8) 13.36/4.64 BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (37) QDPOrderProof (EQUIVALENT) 13.36/4.64 We use the reduction pair processor [LPAR04,JAR06]. 13.36/4.64 13.36/4.64 13.36/4.64 The following pairs can be oriented strictly and are deleted. 13.36/4.64 13.36/4.64 BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue') 13.36/4.64 The remaining pairs can at least be oriented weakly. 13.36/4.64 Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(BREADTH#1(x_1)) = [[0]] + [[1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(tuple#2(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(BREADTH#2(x_1, x_2)) = [[0]] + [[1, 0]] * x_1 + [[1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(::(x_1, x_2)) = [[1], [1]] + [[0, 1], [0, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(BREADTH#3(x_1, x_2)) = [[0]] + [[0, 1]] * x_1 + [[1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(breadth#4(x_1)) = [[1], [0]] + [[1, 0], [0, 1]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(BREADTH#5(x_1)) = [[0]] + [[1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(enqueues(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(BREADTH(x_1, x_2)) = [[0]] + [[1, 0]] * x_1 + [[1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(dequeue(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(tuple#4(x_1, x_2, x_3, x_4)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[0, 1], [0, 1]] * x_3 + [[1, 0], [1, 0]] * x_4 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(children(x_1, x_2, x_3, x_4)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[0, 1], [0, 1]] * x_3 + [[1, 0], [1, 0]] * x_4 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(enqueues#1(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(enqueue(x_1, x_2)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(dequeue#2(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(nil) = [[0], [0]] 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(dequeue#3(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(dequeue#4(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(copyover(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(dequeue#1(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(copyover#2(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(copyover#1(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(enqueue#1(x_1, x_2)) = [[1], [0]] + [[1, 0], [0, 1]] * x_1 + [[0, 1], [0, 0]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(children#1(x_1, x_2, x_3)) = [[0], [1]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(children#3(x_1, x_2, x_3, x_4)) = [[1], [1]] + [[1, 0], [1, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 0], [0, 0]] * x_3 + [[1, 1], [1, 1]] * x_4 13.36/4.64 >>> 13.36/4.64 13.36/4.64 <<< 13.36/4.64 POL(children#2(x_1, x_2)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [1, 1]] * x_2 13.36/4.64 >>> 13.36/4.64 13.36/4.64 13.36/4.64 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 13.36/4.64 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 13.36/4.64 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (38) 13.36/4.64 Obligation: 13.36/4.64 Q DP problem: 13.36/4.64 The TRS P consists of the following rules: 13.36/4.64 13.36/4.64 BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue') 13.36/4.64 BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue')) 13.36/4.64 BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8) 13.36/4.64 BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2)) 13.36/4.64 13.36/4.64 The TRS R consists of the following rules: 13.36/4.64 13.36/4.64 dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq) 13.36/4.64 dequeue#2(nil, @inq) -> dequeue#3(@inq) 13.36/4.64 dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil)) 13.36/4.64 dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4) 13.36/4.64 dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2)) 13.36/4.64 dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil)) 13.36/4.64 dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil) 13.36/4.64 copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq) 13.36/4.64 copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq)) 13.36/4.64 copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2)) 13.36/4.64 copyover#2(nil, @outq) -> tuple#2(nil, @outq) 13.36/4.64 enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue)) 13.36/4.64 enqueues(@l, @queue) -> enqueues#1(@l, @queue) 13.36/4.64 enqueue(@x, @queue) -> enqueue#1(@queue, @x) 13.36/4.64 enqueues#1(nil, @queue) -> @queue 13.36/4.64 enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq) 13.36/4.64 breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6) 13.36/4.64 children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2)) 13.36/4.64 children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs) 13.36/4.64 children#1(nil, @b, @l2) -> children#2(@l2, @b) 13.36/4.64 children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil) 13.36/4.64 children#2(nil, @b) -> nil 13.36/4.64 children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil)) 13.36/4.64 children#3(nil, @b, @x, @xs) -> nil 13.36/4.64 13.36/4.64 The set Q consists of the following terms: 13.36/4.64 13.36/4.64 breadth#4(tuple#4(x0, x1, x2, x3)) 13.36/4.64 children(x0, x1, x2, x3) 13.36/4.64 children#1(::(x0, x1), x2, x3) 13.36/4.64 children#1(nil, x0, x1) 13.36/4.64 children#2(::(x0, x1), x2) 13.36/4.64 children#2(nil, x0) 13.36/4.64 children#3(::(x0, x1), x2, x3, x4) 13.36/4.64 children#3(nil, x0, x1, x2) 13.36/4.64 copyover(x0, x1) 13.36/4.64 copyover#1(tuple#2(x0, x1)) 13.36/4.64 copyover#2(::(x0, x1), x2) 13.36/4.64 copyover#2(nil, x0) 13.36/4.64 dequeue(x0, x1) 13.36/4.64 dequeue#1(tuple#2(x0, x1)) 13.36/4.64 dequeue#2(::(x0, x1), x2) 13.36/4.64 dequeue#2(nil, x0) 13.36/4.64 dequeue#3(::(x0, x1)) 13.36/4.64 dequeue#3(nil) 13.36/4.64 dequeue#4(tuple#2(x0, x1)) 13.36/4.64 enqueue(x0, x1) 13.36/4.64 enqueue#1(tuple#2(x0, x1), x2) 13.36/4.64 enqueues(x0, x1) 13.36/4.64 enqueues#1(::(x0, x1), x2) 13.36/4.64 enqueues#1(nil, x0) 13.36/4.64 13.36/4.64 We have to consider all minimal (P,Q,R)-chains. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (39) DependencyGraphProof (EQUIVALENT) 13.36/4.64 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. 13.36/4.64 ---------------------------------------- 13.36/4.64 13.36/4.64 (40) 13.36/4.64 TRUE 13.44/4.68 EOF