R
↳Dependency Pair Analysis
MINUS(s(x), s(y)) -> MINUS(x, y)
QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))
QUOT(s(x), s(y)) -> MINUS(x, y)
APP(add(n, x), y) -> APP(x, y)
REVERSE(add(n, x)) -> APP(reverse(x), add(n, nil))
REVERSE(add(n, x)) -> REVERSE(x)
SHUFFLE(add(n, x)) -> SHUFFLE(reverse(x))
SHUFFLE(add(n, x)) -> REVERSE(x)
CONCAT(cons(u, v), y) -> CONCAT(v, y)
LESSLEAVES(cons(u, v), cons(w, z)) -> LESSLEAVES(concat(u, v), concat(w, z))
LESSLEAVES(cons(u, v), cons(w, z)) -> CONCAT(u, v)
LESSLEAVES(cons(u, v), cons(w, z)) -> CONCAT(w, z)
R
↳DPs
→DP Problem 1
↳Argument Filtering and Ordering
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
MINUS(s(x), s(y)) -> MINUS(x, y)
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
MINUS(s(x), s(y)) -> MINUS(x, y)
trivial
MINUS(x1, x2) -> MINUS(x1, x2)
s(x1) -> s(x1)
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 8
↳Dependency Graph
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳Argument Filtering and Ordering
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
APP(add(n, x), y) -> APP(x, y)
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
APP(add(n, x), y) -> APP(x, y)
trivial
APP(x1, x2) -> APP(x1, x2)
add(x1, x2) -> add(x1, x2)
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 9
↳Dependency Graph
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳Argument Filtering and Ordering
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
CONCAT(cons(u, v), y) -> CONCAT(v, y)
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
CONCAT(cons(u, v), y) -> CONCAT(v, y)
trivial
CONCAT(x1, x2) -> CONCAT(x1, x2)
cons(x1, x2) -> cons(x1, x2)
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 10
↳Dependency Graph
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳Argument Filtering and Ordering
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
trivial
QUOT(x1, x2) -> QUOT(x1, x2)
s(x1) -> s(x1)
minus(x1, x2) -> x1
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 11
↳Dependency Graph
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳Argument Filtering and Ordering
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
REVERSE(add(n, x)) -> REVERSE(x)
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
REVERSE(add(n, x)) -> REVERSE(x)
trivial
REVERSE(x1) -> REVERSE(x1)
add(x1, x2) -> add(x1, x2)
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 12
↳Dependency Graph
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Narrowing Transformation
→DP Problem 7
↳Nar
LESSLEAVES(cons(u, v), cons(w, z)) -> LESSLEAVES(concat(u, v), concat(w, z))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
four new Dependency Pairs are created:
LESSLEAVES(cons(u, v), cons(w, z)) -> LESSLEAVES(concat(u, v), concat(w, z))
LESSLEAVES(cons(leaf, v'), cons(w, z)) -> LESSLEAVES(v', concat(w, z))
LESSLEAVES(cons(cons(u'', v''), v0), cons(w, z)) -> LESSLEAVES(cons(u'', concat(v'', v0)), concat(w, z))
LESSLEAVES(cons(u, v), cons(leaf, z')) -> LESSLEAVES(concat(u, v), z')
LESSLEAVES(cons(u, v), cons(cons(u'', v''), z')) -> LESSLEAVES(concat(u, v), cons(u'', concat(v'', z')))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 13
↳Argument Filtering and Ordering
→DP Problem 7
↳Nar
LESSLEAVES(cons(u, v), cons(cons(u'', v''), z')) -> LESSLEAVES(concat(u, v), cons(u'', concat(v'', z')))
LESSLEAVES(cons(u, v), cons(leaf, z')) -> LESSLEAVES(concat(u, v), z')
LESSLEAVES(cons(cons(u'', v''), v0), cons(w, z)) -> LESSLEAVES(cons(u'', concat(v'', v0)), concat(w, z))
LESSLEAVES(cons(leaf, v'), cons(w, z)) -> LESSLEAVES(v', concat(w, z))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
LESSLEAVES(cons(u, v), cons(cons(u'', v''), z')) -> LESSLEAVES(concat(u, v), cons(u'', concat(v'', z')))
LESSLEAVES(cons(u, v), cons(leaf, z')) -> LESSLEAVES(concat(u, v), z')
LESSLEAVES(cons(cons(u'', v''), v0), cons(w, z)) -> LESSLEAVES(cons(u'', concat(v'', v0)), concat(w, z))
LESSLEAVES(cons(leaf, v'), cons(w, z)) -> LESSLEAVES(v', concat(w, z))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
{concat, cons}
LESSLEAVES(x1, x2) -> LESSLEAVES(x1, x2)
cons(x1, x2) -> cons(x1, x2)
concat(x1, x2) -> concat(x1, x2)
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 13
↳AFS
...
→DP Problem 14
↳Dependency Graph
→DP Problem 7
↳Nar
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Narrowing Transformation
SHUFFLE(add(n, x)) -> SHUFFLE(reverse(x))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))
two new Dependency Pairs are created:
SHUFFLE(add(n, x)) -> SHUFFLE(reverse(x))
SHUFFLE(add(n, nil)) -> SHUFFLE(nil)
SHUFFLE(add(n, add(n'', x''))) -> SHUFFLE(app(reverse(x''), add(n'', nil)))
R
↳DPs
→DP Problem 1
↳AFS
→DP Problem 2
↳AFS
→DP Problem 3
↳AFS
→DP Problem 4
↳AFS
→DP Problem 5
↳AFS
→DP Problem 6
↳Nar
→DP Problem 7
↳Nar
→DP Problem 15
↳Remaining Obligation(s)
SHUFFLE(add(n, add(n'', x''))) -> SHUFFLE(app(reverse(x''), add(n'', nil)))
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
quot(0, s(y)) -> 0
quot(s(x), s(y)) -> s(quot(minus(x, y), s(y)))
app(nil, y) -> y
app(add(n, x), y) -> add(n, app(x, y))
reverse(nil) -> nil
reverse(add(n, x)) -> app(reverse(x), add(n, nil))
shuffle(nil) -> nil
shuffle(add(n, x)) -> add(n, shuffle(reverse(x)))
concat(leaf, y) -> y
concat(cons(u, v), y) -> cons(u, concat(v, y))
lessleaves(x, leaf) -> false
lessleaves(leaf, cons(w, z)) -> true
lessleaves(cons(u, v), cons(w, z)) -> lessleaves(concat(u, v), concat(w, z))