YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 8 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QReductionProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QReductionProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) MRRProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) DependencyGraphProof [EQUIVALENT, 0 ms]
        (20) TRUE
    (21) QDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QReductionProof [EQUIVALENT, 0 ms]
        (25) QDP
        (26) MRRProof [EQUIVALENT, 13 ms]
        (27) QDP
        (28) QDPOrderProof [EQUIVALENT, 17 ms]
        (29) QDP
        (30) DependencyGraphProof [EQUIVALENT, 0 ms]
        (31) TRUE
    (32) QDP
        (33) UsableRulesProof [EQUIVALENT, 0 ms]
        (34) QDP
        (35) QReductionProof [EQUIVALENT, 0 ms]
        (36) QDP
        (37) QDPOrderProof [EQUIVALENT, 77 ms]
        (38) QDP
        (39) DependencyGraphProof [EQUIVALENT, 0 ms]
        (40) TRUE


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))


----------------------------------------

(1) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(2)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2))
   BREADTH(@breadth@1, @breadth@2) -> DEQUEUE(@breadth@1, @breadth@2)
   BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue')
   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue')
   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#4(@z)
   BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue'))
   BREADTH#3(tuple#2(@x, @ys), @queue') -> ENQUEUES(@ys, @queue')
   BREADTH#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> CHILDREN(@children@3, @children@4, @children@5, @children@6)
   BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8)
   CHILDREN(@a, @b, @l1, @l2) -> CHILDREN#1(@l1, @b, @l2)
   CHILDREN#1(::(@x, @xs), @b, @l2) -> CHILDREN#3(@l2, @b, @x, @xs)
   CHILDREN#1(nil, @b, @l2) -> CHILDREN#2(@l2, @b)
   COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2))
   COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq)
   COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq))
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)
   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE#3(::(@x, @xs)) -> COPYOVER(::(@x, @xs), nil)
   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   ENQUEUE(@x, @queue) -> ENQUEUE#1(@queue, @x)
   ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue)
   ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue))
   ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUE(@x, @queue)
   STARTBREADTH(@xs) -> STARTBREADTH#1(@xs)
   STARTBREADTH#1(::(@x, @xs)) -> STARTBREADTH#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   STARTBREADTH#1(::(@x, @xs)) -> ENQUEUE(tuple#4(@x, @x, @xs, @xs), empty(#unit))
   STARTBREADTH#1(::(@x, @xs)) -> EMPTY(#unit)
   STARTBREADTH#2(tuple#2(@breadth@1, @breadth@2)) -> BREADTH(@breadth@1, @breadth@2)

The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(3) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 15 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue))
   ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue)

The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(6) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue))
   ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue)

The TRS R consists of the following rules:

   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(8) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))


----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue))
   ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue)

The TRS R consists of the following rules:

   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)

The set Q consists of the following terms:

   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(10) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*ENQUEUES(@l, @queue) -> ENQUEUES#1(@l, @queue)
The graph contains the following edges 1 >= 1, 2 >= 2


*ENQUEUES#1(::(@x, @xs), @queue) -> ENQUEUES(@xs, enqueue(@x, @queue))
The graph contains the following edges 1 > 1


----------------------------------------

(11)
YES

----------------------------------------

(12)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq)
   COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq))
   COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2))

The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(13) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq)
   COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq))
   COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2))

R is empty.
The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))


----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq)
   COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq))
   COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(17) MRRProof (EQUIVALENT)
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.

Strictly oriented dependency pairs:

   COPYOVER#2(::(@x, @xs), @outq) -> COPYOVER(@xs, ::(@x, @outq))
   COPYOVER(@copyover@1, @copyover@2) -> COPYOVER#1(tuple#2(@copyover@1, @copyover@2))


Used ordering: Polynomial interpretation [POLO]:

   POL(::(x_1, x_2)) = 2 + 2*x_1 + x_2
   POL(COPYOVER(x_1, x_2)) = 1 + 2*x_1 + x_2
   POL(COPYOVER#1(x_1)) = x_1
   POL(COPYOVER#2(x_1, x_2)) = 2*x_1 + x_2
   POL(tuple#2(x_1, x_2)) = 2*x_1 + x_2


----------------------------------------

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COPYOVER#1(tuple#2(@inq, @outq)) -> COPYOVER#2(@inq, @outq)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(19) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(20)
TRUE

----------------------------------------

(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)

The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(22) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)

The TRS R consists of the following rules:

   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(24) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))


----------------------------------------

(25)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)

The TRS R consists of the following rules:

   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)

The set Q consists of the following terms:

   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(26) MRRProof (EQUIVALENT)
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.


Strictly oriented rules of the TRS R:

   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))

Used ordering: Polynomial interpretation [POLO]:

   POL(::(x_1, x_2)) = 2 + 2*x_1 + x_2
   POL(DEQUEUE(x_1, x_2)) = 2*x_1 + x_2
   POL(DEQUEUE#1(x_1)) = x_1
   POL(DEQUEUE#2(x_1, x_2)) = x_1 + 2*x_2
   POL(DEQUEUE#3(x_1)) = 2*x_1
   POL(DEQUEUE#4(x_1)) = x_1
   POL(copyover(x_1, x_2)) = 2*x_1 + x_2
   POL(copyover#1(x_1)) = x_1
   POL(copyover#2(x_1, x_2)) = 2*x_1 + x_2
   POL(nil) = 0
   POL(tuple#2(x_1, x_2)) = 2*x_1 + x_2


----------------------------------------

(27)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)

The TRS R consists of the following rules:

   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)

The set Q consists of the following terms:

   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(28) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   DEQUEUE#3(::(@x, @xs)) -> DEQUEUE#4(copyover(::(@x, @xs), nil))
   DEQUEUE(@dequeue@1, @dequeue@2) -> DEQUEUE#1(tuple#2(@dequeue@1, @dequeue@2))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( DEQUEUE#4_1(x_1) ) = 2x_1 + 1
POL( copyover_2(x_1, x_2) ) = 1
POL( copyover#1_1(x_1) ) = 1
POL( tuple#2_2(x_1, x_2) ) = x_1
POL( copyover#2_2(x_1, x_2) ) = 1
POL( nil ) = 0
POL( DEQUEUE#3_1(x_1) ) = 2x_1
POL( ::_2(x_1, x_2) ) = 2
POL( DEQUEUE_2(x_1, x_2) ) = 2x_1 + 1
POL( DEQUEUE#1_1(x_1) ) = 2x_1
POL( DEQUEUE#2_2(x_1, x_2) ) = 2x_2

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)


----------------------------------------

(29)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DEQUEUE#4(tuple#2(@dequeue@3, @dequeue@4)) -> DEQUEUE(@dequeue@3, @dequeue@4)
   DEQUEUE#1(tuple#2(@inq, @outq)) -> DEQUEUE#2(@outq, @inq)
   DEQUEUE#2(nil, @inq) -> DEQUEUE#3(@inq)

The TRS R consists of the following rules:

   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)

The set Q consists of the following terms:

   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(30) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes.
----------------------------------------

(31)
TRUE

----------------------------------------

(32)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue')
   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue')
   BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue'))
   BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8)
   BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2))

The TRS R consists of the following rules:

   breadth(@breadth@1, @breadth@2) -> breadth#1(dequeue(@breadth@1, @breadth@2))
   breadth#1(tuple#2(@queue', @elem)) -> breadth#2(@elem, @queue')
   breadth#2(::(@z, @_@9), @queue') -> breadth#3(breadth#4(@z), @queue')
   breadth#2(nil, @queue') -> nil
   breadth#3(tuple#2(@x, @ys), @queue') -> ::(@x, breadth#5(enqueues(@ys, @queue')))
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   breadth#5(tuple#2(@breadth@7, @breadth@8)) -> breadth(@breadth@7, @breadth@8)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   empty(@x) -> tuple#2(nil, nil)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues#1(nil, @queue) -> @queue
   startBreadth(@xs) -> startBreadth#1(@xs)
   startBreadth#1(::(@x, @xs)) -> startBreadth#2(enqueue(tuple#4(@x, @x, @xs, @xs), empty(#unit)))
   startBreadth#1(nil) -> nil
   startBreadth#2(tuple#2(@breadth@1, @breadth@2)) -> breadth(@breadth@1, @breadth@2)

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(33) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(34)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue')
   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue')
   BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue'))
   BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8)
   BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2))

The TRS R consists of the following rules:

   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueues#1(nil, @queue) -> @queue
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil

The set Q consists of the following terms:

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#4(tuple#4(x0, x1, x2, x3))
   breadth#5(tuple#2(x0, x1))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   empty(x0)
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(35) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   breadth(x0, x1)
   breadth#1(tuple#2(x0, x1))
   breadth#2(::(x0, x1), x2)
   breadth#2(nil, x0)
   breadth#3(tuple#2(x0, x1), x2)
   breadth#5(tuple#2(x0, x1))
   empty(x0)
   startBreadth(x0)
   startBreadth#1(::(x0, x1))
   startBreadth#1(nil)
   startBreadth#2(tuple#2(x0, x1))


----------------------------------------

(36)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue')
   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue')
   BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue'))
   BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8)
   BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2))

The TRS R consists of the following rules:

   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueues#1(nil, @queue) -> @queue
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil

The set Q consists of the following terms:

   breadth#4(tuple#4(x0, x1, x2, x3))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(37) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   BREADTH#2(::(@z, @_@9), @queue') -> BREADTH#3(breadth#4(@z), @queue')
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(BREADTH#1(x_1)) =  	[[0]] 	 +  	[[1, 0]] 	* 	x_1
>>>

   <<<
 POL(tuple#2(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 0]] 	* 	x_2
>>>

   <<<
 POL(BREADTH#2(x_1, x_2)) =  	[[0]] 	 +  	[[1, 0]] 	* 	x_1 	 +  	[[1, 0]] 	* 	x_2
>>>

   <<<
 POL(::(x_1, x_2)) =  	[[1], [1]] 	 +  	[[0, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 1]] 	* 	x_2
>>>

   <<<
 POL(BREADTH#3(x_1, x_2)) =  	[[0]] 	 +  	[[0, 1]] 	* 	x_1 	 +  	[[1, 0]] 	* 	x_2
>>>

   <<<
 POL(breadth#4(x_1)) =  	[[1], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(BREADTH#5(x_1)) =  	[[0]] 	 +  	[[1, 0]] 	* 	x_1
>>>

   <<<
 POL(enqueues(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 1]] 	* 	x_2
>>>

   <<<
 POL(BREADTH(x_1, x_2)) =  	[[0]] 	 +  	[[1, 0]] 	* 	x_1 	 +  	[[1, 0]] 	* 	x_2
>>>

   <<<
 POL(dequeue(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 0]] 	* 	x_2
>>>

   <<<
 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
>>>

   <<<
 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
>>>

   <<<
 POL(enqueues#1(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 1]] 	* 	x_2
>>>

   <<<
 POL(enqueue(x_1, x_2)) =  	[[1], [0]] 	 +  	[[0, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 1]] 	* 	x_2
>>>

   <<<
 POL(dequeue#2(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 0]] 	* 	x_2
>>>

   <<<
 POL(nil) =  	[[0], [0]]
>>>

   <<<
 POL(dequeue#3(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1
>>>

   <<<
 POL(dequeue#4(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1
>>>

   <<<
 POL(copyover(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 0]] 	* 	x_2
>>>

   <<<
 POL(dequeue#1(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1
>>>

   <<<
 POL(copyover#2(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1 	 +  	[[1, 0], [1, 0]] 	* 	x_2
>>>

   <<<
 POL(copyover#1(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [1, 0]] 	* 	x_1
>>>

   <<<
 POL(enqueue#1(x_1, x_2)) =  	[[1], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1 	 +  	[[0, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 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
>>>

   <<<
 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
>>>

   <<<
 POL(children#2(x_1, x_2)) =  	[[0], [1]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[0, 0], [1, 1]] 	* 	x_2
>>>


The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   enqueues#1(nil, @queue) -> @queue
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil


----------------------------------------

(38)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   BREADTH#1(tuple#2(@queue', @elem)) -> BREADTH#2(@elem, @queue')
   BREADTH#3(tuple#2(@x, @ys), @queue') -> BREADTH#5(enqueues(@ys, @queue'))
   BREADTH#5(tuple#2(@breadth@7, @breadth@8)) -> BREADTH(@breadth@7, @breadth@8)
   BREADTH(@breadth@1, @breadth@2) -> BREADTH#1(dequeue(@breadth@1, @breadth@2))

The TRS R consists of the following rules:

   dequeue#1(tuple#2(@inq, @outq)) -> dequeue#2(@outq, @inq)
   dequeue#2(nil, @inq) -> dequeue#3(@inq)
   dequeue#3(::(@x, @xs)) -> dequeue#4(copyover(::(@x, @xs), nil))
   dequeue#4(tuple#2(@dequeue@3, @dequeue@4)) -> dequeue(@dequeue@3, @dequeue@4)
   dequeue(@dequeue@1, @dequeue@2) -> dequeue#1(tuple#2(@dequeue@1, @dequeue@2))
   dequeue#2(::(@y, @ys), @inq) -> tuple#2(tuple#2(@inq, @ys), ::(@y, nil))
   dequeue#3(nil) -> tuple#2(tuple#2(nil, nil), nil)
   copyover#1(tuple#2(@inq, @outq)) -> copyover#2(@inq, @outq)
   copyover#2(::(@x, @xs), @outq) -> copyover(@xs, ::(@x, @outq))
   copyover(@copyover@1, @copyover@2) -> copyover#1(tuple#2(@copyover@1, @copyover@2))
   copyover#2(nil, @outq) -> tuple#2(nil, @outq)
   enqueues#1(::(@x, @xs), @queue) -> enqueues(@xs, enqueue(@x, @queue))
   enqueues(@l, @queue) -> enqueues#1(@l, @queue)
   enqueue(@x, @queue) -> enqueue#1(@queue, @x)
   enqueues#1(nil, @queue) -> @queue
   enqueue#1(tuple#2(@inq, @outq), @x) -> tuple#2(::(@x, @inq), @outq)
   breadth#4(tuple#4(@children@3, @children@4, @children@5, @children@6)) -> children(@children@3, @children@4, @children@5, @children@6)
   children(@a, @b, @l1, @l2) -> tuple#2(tuple#2(@a, @b), children#1(@l1, @b, @l2))
   children#1(::(@x, @xs), @b, @l2) -> children#3(@l2, @b, @x, @xs)
   children#1(nil, @b, @l2) -> children#2(@l2, @b)
   children#2(::(@y, @ys), @b) -> ::(tuple#4(@y, @b, nil, @ys), nil)
   children#2(nil, @b) -> nil
   children#3(::(@y, @ys), @b, @x, @xs) -> ::(tuple#4(@x, @b, nil, @xs), ::(tuple#4(@x, @y, @xs, @ys), nil))
   children#3(nil, @b, @x, @xs) -> nil

The set Q consists of the following terms:

   breadth#4(tuple#4(x0, x1, x2, x3))
   children(x0, x1, x2, x3)
   children#1(::(x0, x1), x2, x3)
   children#1(nil, x0, x1)
   children#2(::(x0, x1), x2)
   children#2(nil, x0)
   children#3(::(x0, x1), x2, x3, x4)
   children#3(nil, x0, x1, x2)
   copyover(x0, x1)
   copyover#1(tuple#2(x0, x1))
   copyover#2(::(x0, x1), x2)
   copyover#2(nil, x0)
   dequeue(x0, x1)
   dequeue#1(tuple#2(x0, x1))
   dequeue#2(::(x0, x1), x2)
   dequeue#2(nil, x0)
   dequeue#3(::(x0, x1))
   dequeue#3(nil)
   dequeue#4(tuple#2(x0, x1))
   enqueue(x0, x1)
   enqueue#1(tuple#2(x0, x1), x2)
   enqueues(x0, x1)
   enqueues#1(::(x0, x1), x2)
   enqueues#1(nil, x0)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(39) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes.
----------------------------------------

(40)
TRUE