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

0 QTRS
↳1 Overlay + Local Confluence (⇔)
↳2 QTRS
↳3 DependencyPairsProof (⇔)
↳4 QDP
↳5 DependencyGraphProof (⇔)
↳6 AND
  ↳7 QDP
    ↳8 QDPOrderProof (⇔)
    ↳9 QDP
    ↳10 PisEmptyProof (⇔)
    ↳11 TRUE
  ↳12 QDP
    ↳13 QDPOrderProof (⇔)
    ↳14 QDP
    ↳15 PisEmptyProof (⇔)
    ↳16 TRUE
  ↳17 QDP
    ↳18 QDPOrderProof (⇔)
    ↳19 QDP
    ↳20 PisEmptyProof (⇔)
    ↳21 TRUE
  ↳22 QDP
    ↳23 QDPOrderProof (⇔)
    ↳24 QDP
    ↳25 DependencyGraphProof (⇔)
    ↳26 TRUE
  ↳27 QDP
    ↳28 QDPOrderProof (⇔)
    ↳29 QDP
    ↳30 PisEmptyProof (⇔)
    ↳31 TRUE
  ↳32 QDP
    ↳33 QDPOrderProof (⇔)
    ↳34 QDP
    ↳35 PisEmptyProof (⇔)
    ↳36 TRUE
  ↳37 QDP
    ↳38 QDPOrderProof (⇔)
    ↳39 QDP
    ↳40 PisEmptyProof (⇔)
    ↳41 TRUE
  ↳42 QDP
    ↳43 QDPOrderProof (⇔)
    ↳44 QDP
    ↳45 DependencyGraphProof (⇔)
    ↳46 TRUE

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

Q is empty.

(1) Overlay + Local Confluence (EQUIVALENT transformation)

The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.

(2) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

(3) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(4) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(minus, app'(s, x)), app'(s, y)) → APP'(app'(minus, x), y)
APP'(app'(minus, app'(s, x)), app'(s, y)) → APP'(minus, x)
APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))
APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(quot, app'(app'(minus, x), y))
APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(app'(minus, x), y)
APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(minus, x)
APP'(app'(le, app'(s, x)), app'(s, y)) → APP'(app'(le, x), y)
APP'(app'(le, app'(s, x)), app'(s, y)) → APP'(le, x)
APP'(app'(app, app'(app'(add, n), x)), y) → APP'(app'(add, n), app'(app'(app, x), y))
APP'(app'(app, app'(app'(add, n), x)), y) → APP'(app'(app, x), y)
APP'(app'(app, app'(app'(add, n), x)), y) → APP'(app, x)
APP'(app'(low, n), app'(app'(add, m), x)) → APP'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(low, n), app'(app'(add, m), x)) → APP'(app'(if_low, app'(app'(le, m), n)), n)
APP'(app'(low, n), app'(app'(add, m), x)) → APP'(if_low, app'(app'(le, m), n))
APP'(app'(low, n), app'(app'(add, m), x)) → APP'(app'(le, m), n)
APP'(app'(low, n), app'(app'(add, m), x)) → APP'(le, m)
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → APP'(app'(add, m), app'(app'(low, n), x))
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → APP'(low, n)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → APP'(low, n)
APP'(app'(high, n), app'(app'(add, m), x)) → APP'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(high, n), app'(app'(add, m), x)) → APP'(app'(if_high, app'(app'(le, m), n)), n)
APP'(app'(high, n), app'(app'(add, m), x)) → APP'(if_high, app'(app'(le, m), n))
APP'(app'(high, n), app'(app'(add, m), x)) → APP'(app'(le, m), n)
APP'(app'(high, n), app'(app'(add, m), x)) → APP'(le, m)
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → APP'(high, n)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → APP'(app'(add, m), app'(app'(high, n), x))
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → APP'(high, n)
APP'(quicksort, app'(app'(add, n), x)) → APP'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
APP'(quicksort, app'(app'(add, n), x)) → APP'(app, app'(quicksort, app'(app'(low, n), x)))
APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(low, n), x))
APP'(quicksort, app'(app'(add, n), x)) → APP'(app'(low, n), x)
APP'(quicksort, app'(app'(add, n), x)) → APP'(low, n)
APP'(quicksort, app'(app'(add, n), x)) → APP'(app'(add, n), app'(quicksort, app'(app'(high, n), x)))
APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) → APP'(app'(high, n), x)
APP'(quicksort, app'(app'(add, n), x)) → APP'(high, n)
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(app'(add, app'(f, x)), app'(app'(map, f), xs))
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(add, app'(f, x))
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(f, x)
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(app'(map, f), xs)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(app'(filter2, app'(f, x)), f), x)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(filter2, app'(f, x)), f)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(filter2, app'(f, x))
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(f, x)
APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(app'(add, x), app'(app'(filter, f), xs))
APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(add, x)
APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(app'(filter, f), xs)
APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(filter, f)
APP'(app'(app'(app'(filter2, false), f), x), xs) → APP'(app'(filter, f), xs)
APP'(app'(app'(app'(filter2, false), f), x), xs) → APP'(filter, f)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 8 SCCs with 38 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(app, app'(app'(add, n), x)), y) → APP'(app'(app, x), y)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(8) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

app1(add(n, x), y) → app1(x, y)

The a-transformed usable rules are
none


The following pairs can be oriented strictly and are deleted.


APP'(app'(app, app'(app'(add, n), x)), y) → APP'(app'(app, x), y)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
app1(x1, x2)  =  app1(x1, x2)
add(x1, x2)  =  add(x2)

Lexicographic Path Order [LPO].
Precedence:
trivial


The following usable rules [FROCOS05] were oriented: none

(9) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(10) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(11) TRUE

(12) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(le, app'(s, x)), app'(s, y)) → APP'(app'(le, x), y)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(13) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

le1(s(x), s(y)) → le1(x, y)

The a-transformed usable rules are
none


The following pairs can be oriented strictly and are deleted.


APP'(app'(le, app'(s, x)), app'(s, y)) → APP'(app'(le, x), y)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
le1(x1, x2)  =  x2
s(x1)  =  s(x1)

Lexicographic Path Order [LPO].
Precedence:
trivial


The following usable rules [FROCOS05] were oriented: none

(14) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(15) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(16) TRUE

(17) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(high, n), app'(app'(add, m), x)) → APP'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(18) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

high1(n, add(m, x)) → if_high1(le(m, n), n, add(m, x))
if_high1(true, n, add(m, x)) → high1(n, x)
if_high1(false, n, add(m, x)) → high1(n, x)

The a-transformed usable rules are

le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)


The following pairs can be oriented strictly and are deleted.


APP'(app'(high, n), app'(app'(add, m), x)) → APP'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)
APP'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → APP'(app'(high, n), x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
high1(x1, x2)  =  high1(x2)
add(x1, x2)  =  add(x1, x2)
if_high1(x1, x2, x3)  =  if_high1(x3)
le(x1, x2)  =  le(x1, x2)
true  =  true
false  =  false
0  =  0
s(x1)  =  s(x1)

Lexicographic Path Order [LPO].
Precedence:
add2 > [high11, false] > ifhigh11 > [le2, true]
0 > [le2, true]
s1 > [high11, false] > ifhigh11 > [le2, true]


The following usable rules [FROCOS05] were oriented:

app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)

(19) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(20) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(21) TRUE

(22) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(low, n), app'(app'(add, m), x)) → APP'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(23) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

low1(n, add(m, x)) → if_low1(le(m, n), n, add(m, x))
if_low1(true, n, add(m, x)) → low1(n, x)
if_low1(false, n, add(m, x)) → low1(n, x)

The a-transformed usable rules are

le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)


The following pairs can be oriented strictly and are deleted.


APP'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)
APP'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → APP'(app'(low, n), x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
low1(x1, x2)  =  low1(x1, x2)
add(x1, x2)  =  add(x2)
if_low1(x1, x2, x3)  =  if_low1(x2, x3)
le(x1, x2)  =  le
true  =  true
false  =  false
0  =  0
s(x1)  =  s(x1)

Lexicographic Path Order [LPO].
Precedence:
[low12, iflow12] > add1
[low12, iflow12] > [le, true, 0] > [false, s1]


The following usable rules [FROCOS05] were oriented:

app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)

(24) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(low, n), app'(app'(add, m), x)) → APP'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(25) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.

(26) TRUE

(27) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(low, n), x))

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(28) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

quicksort1(add(n, x)) → quicksort1(high(n, x))
quicksort1(add(n, x)) → quicksort1(low(n, x))

The a-transformed usable rules are

low(n, nil) → nil
low(n, add(m, x)) → if_low(le(m, n), n, add(m, x))
if_low(false, n, add(m, x)) → low(n, x)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
if_low(true, n, add(m, x)) → add(m, low(n, x))
high(n, nil) → nil
high(n, add(m, x)) → if_high(le(m, n), n, add(m, x))
if_high(true, n, add(m, x)) → high(n, x)
if_high(false, n, add(m, x)) → add(m, high(n, x))


The following pairs can be oriented strictly and are deleted.


APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(high, n), x))
APP'(quicksort, app'(app'(add, n), x)) → APP'(quicksort, app'(app'(low, n), x))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
quicksort1(x1)  =  quicksort1(x1)
add(x1, x2)  =  add(x2)
high(x1, x2)  =  x2
low(x1, x2)  =  x2
nil  =  nil
if_low(x1, x2, x3)  =  x3
le(x1, x2)  =  le(x2)
false  =  false
0  =  0
true  =  true
s(x1)  =  x1
if_high(x1, x2, x3)  =  x3

Lexicographic Path Order [LPO].
Precedence:
[quicksort11, add1] > [le1, false, 0] > true > nil


The following usable rules [FROCOS05] were oriented:

app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))

(29) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(30) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(31) TRUE

(32) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(minus, app'(s, x)), app'(s, y)) → APP'(app'(minus, x), y)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(33) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

minus1(s(x), s(y)) → minus1(x, y)

The a-transformed usable rules are
none


The following pairs can be oriented strictly and are deleted.


APP'(app'(minus, app'(s, x)), app'(s, y)) → APP'(app'(minus, x), y)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
minus1(x1, x2)  =  x2
s(x1)  =  s(x1)

Lexicographic Path Order [LPO].
Precedence:
trivial


The following usable rules [FROCOS05] were oriented: none

(34) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(35) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(36) TRUE

(37) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(38) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

quot1(s(x), s(y)) → quot1(minus(x, y), s(y))

The a-transformed usable rules are

minus(x, 0) → x
minus(s(x), s(y)) → minus(x, y)


The following pairs can be oriented strictly and are deleted.


APP'(app'(quot, app'(s, x)), app'(s, y)) → APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
quot1(x1, x2)  =  quot1(x1)
s(x1)  =  s(x1)
minus(x1, x2)  =  x1
0  =  0

Lexicographic Path Order [LPO].
Precedence:
0 > [quot11, s1]


The following usable rules [FROCOS05] were oriented:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)

(39) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(40) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(41) TRUE

(42) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(app'(map, f), xs)
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(f, x)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(app'(filter, f), xs)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(f, x)
APP'(app'(app'(app'(filter2, false), f), x), xs) → APP'(app'(filter, f), xs)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(43) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(app'(map, f), xs)
APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(f, x)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(f, x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
APP'(x1, x2)  =  APP'(x2)
app'(x1, x2)  =  app'(x1, x2)
map  =  map
add  =  add
filter  =  filter
filter2  =  filter2
true  =  true
false  =  false
nil  =  nil
if_high  =  if_high
high  =  high
le  =  le
quicksort  =  quicksort
app  =  app
low  =  low
s  =  s
0  =  0
if_low  =  if_low
minus  =  minus
quot  =  quot

Lexicographic Path Order [LPO].
Precedence:
APP'1 > map > app'2
APP'1 > [filter, filter2, false] > app'2
true > low > le > [filter, filter2, false] > app'2
true > low > iflow > app'2
app > [add, nil, high] > map > app'2
app > [add, nil, high] > ifhigh > app'2
app > [add, nil, high] > quicksort > app'2
app > [add, nil, high] > low > le > [filter, filter2, false] > app'2
app > [add, nil, high] > low > iflow > app'2
0 > [filter, filter2, false] > app'2
minus > app'2
quot > s > app'2


The following usable rules [FROCOS05] were oriented: none

(44) Obligation:

Q DP problem:
The TRS P consists of the following rules:

APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(app'(filter, f), xs)
APP'(app'(app'(app'(filter2, false), f), x), xs) → APP'(app'(filter, f), xs)

The TRS R consists of the following rules:

app'(app'(minus, x), 0) → x
app'(app'(minus, app'(s, x)), app'(s, y)) → app'(app'(minus, x), y)
app'(app'(quot, 0), app'(s, y)) → 0
app'(app'(quot, app'(s, x)), app'(s, y)) → app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y)))
app'(app'(le, 0), y) → true
app'(app'(le, app'(s, x)), 0) → false
app'(app'(le, app'(s, x)), app'(s, y)) → app'(app'(le, x), y)
app'(app'(app, nil), y) → y
app'(app'(app, app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(app, x), y))
app'(app'(low, n), nil) → nil
app'(app'(low, n), app'(app'(add, m), x)) → app'(app'(app'(if_low, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_low, true), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(low, n), x))
app'(app'(app'(if_low, false), n), app'(app'(add, m), x)) → app'(app'(low, n), x)
app'(app'(high, n), nil) → nil
app'(app'(high, n), app'(app'(add, m), x)) → app'(app'(app'(if_high, app'(app'(le, m), n)), n), app'(app'(add, m), x))
app'(app'(app'(if_high, true), n), app'(app'(add, m), x)) → app'(app'(high, n), x)
app'(app'(app'(if_high, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(high, n), x))
app'(quicksort, nil) → nil
app'(quicksort, app'(app'(add, n), x)) → app'(app'(app, app'(quicksort, app'(app'(low, n), x))), app'(app'(add, n), app'(quicksort, app'(app'(high, n), x))))
app'(app'(map, f), nil) → nil
app'(app'(map, f), app'(app'(add, x), xs)) → app'(app'(add, app'(f, x)), app'(app'(map, f), xs))
app'(app'(filter, f), nil) → nil
app'(app'(filter, f), app'(app'(add, x), xs)) → app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
app'(app'(app'(app'(filter2, true), f), x), xs) → app'(app'(add, x), app'(app'(filter, f), xs))
app'(app'(app'(app'(filter2, false), f), x), xs) → app'(app'(filter, f), xs)

The set Q consists of the following terms:

app'(app'(minus, x0), 0)
app'(app'(minus, app'(s, x0)), app'(s, x1))
app'(app'(quot, 0), app'(s, x0))
app'(app'(quot, app'(s, x0)), app'(s, x1))
app'(app'(le, 0), x0)
app'(app'(le, app'(s, x0)), 0)
app'(app'(le, app'(s, x0)), app'(s, x1))
app'(app'(app, nil), x0)
app'(app'(app, app'(app'(add, x0), x1)), x2)
app'(app'(low, x0), nil)
app'(app'(low, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_low, false), x0), app'(app'(add, x1), x2))
app'(app'(high, x0), nil)
app'(app'(high, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_high, false), x0), app'(app'(add, x1), x2))
app'(quicksort, nil)
app'(quicksort, app'(app'(add, x0), x1))
app'(app'(map, x0), nil)
app'(app'(map, x0), app'(app'(add, x1), x2))
app'(app'(filter, x0), nil)
app'(app'(filter, x0), app'(app'(add, x1), x2))
app'(app'(app'(app'(filter2, true), x0), x1), x2)
app'(app'(app'(app'(filter2, false), x0), x1), x2)

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

(45) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.

(46) TRUE