(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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'(eq, app'(s, x)), app'(s, y)) → APP'(app'(eq, x), y)
APP'(app'(eq, app'(s, x)), app'(s, y)) → APP'(eq, 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'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
APP'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(if_min, app'(app'(le, n), m))
APP'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(app'(le, n), m)
APP'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(le, n)
APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, n), x))
APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → APP'(app'(add, n), x)
APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, m), x))
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(app'(if_rm, app'(app'(eq, n), m)), n)
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(if_rm, app'(app'(eq, n), m))
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(app'(eq, n), m)
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(eq, n)
APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → APP'(rm, n)
APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → APP'(app'(add, m), app'(app'(rm, n), x))
APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → APP'(rm, n)
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x))
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x))))
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(app'(eq, n), app'(min, app'(app'(add, n), x)))
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(eq, n)
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(min, app'(app'(add, n), x))
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(minsort, app'(app'(app, app'(app'(rm, n), x)), y))
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(app, app'(app'(rm, n), x)), y)
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app, app'(app'(rm, n), x))
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(rm, n), x)
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(rm, n)
APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → APP'(app'(minsort, x), app'(app'(add, n), y))
APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → APP'(minsort, x)
APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → APP'(app'(add, n), y)
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'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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 7 SCCs with 37 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'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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) UsableRulesProof (EQUIVALENT transformation)
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.
(9) 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)
R is empty.
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(11) Obligation:
Q DP problem:
The TRS P consists of the following rules:
app1(add(n, x), y) → app1(x, y)
R is empty.
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(12) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(13) Obligation:
Q DP problem:
The TRS P consists of the following rules:
app1(add(n, x), y) → app1(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(14) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- app1(add(n, x), y) → app1(x, y)
The graph contains the following edges 1 > 1, 2 >= 2
(15) YES
(16) 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'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(17) UsableRulesProof (EQUIVALENT transformation)
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.
(18) 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)
R is empty.
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(19) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(20) Obligation:
Q DP problem:
The TRS P consists of the following rules:
le1(s(x), s(y)) → le1(x, y)
R is empty.
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(21) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(22) Obligation:
Q DP problem:
The TRS P consists of the following rules:
le1(s(x), s(y)) → le1(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(23) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- le1(s(x), s(y)) → le1(x, y)
The graph contains the following edges 1 > 1, 2 > 2
(24) YES
(25) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, n), x))
APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, m), x))
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(26) UsableRulesProof (EQUIVALENT transformation)
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.
(27) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(min, app'(app'(add, n), app'(app'(add, m), x))) → APP'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
APP'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, n), x))
APP'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → APP'(min, app'(app'(add, m), x))
The TRS R consists of the following rules:
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)
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(29) Obligation:
Q DP problem:
The TRS P consists of the following rules:
min1(add(n, add(m, x))) → if_min1(le(n, m), add(n, add(m, x)))
if_min1(true, add(n, add(m, x))) → min1(add(n, x))
if_min1(false, add(n, add(m, x))) → min1(add(m, x))
The TRS R consists of the following rules:
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(30) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(31) Obligation:
Q DP problem:
The TRS P consists of the following rules:
min1(add(n, add(m, x))) → if_min1(le(n, m), add(n, add(m, x)))
if_min1(true, add(n, add(m, x))) → min1(add(n, x))
if_min1(false, add(n, add(m, x))) → min1(add(m, x))
The TRS R consists of the following rules:
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
(32) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04,JAR06].
The following pairs can be oriented strictly and are deleted.
min1(add(n, add(m, x))) → if_min1(le(n, m), add(n, add(m, x)))
if_min1(true, add(n, add(m, x))) → min1(add(n, x))
if_min1(false, add(n, add(m, x))) → min1(add(m, x))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:
POL( if_min1(x1, x2) ) = max{0, 2x1 + x2 - 2} |
POL( min1(x1) ) = max{0, 2x1 - 1} |
POL( add(x1, x2) ) = 2x2 + 2 |
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
(33) Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
(34) PisEmptyProof (EQUIVALENT transformation)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
(35) YES
(36) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(eq, app'(s, x)), app'(s, y)) → APP'(app'(eq, x), y)
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(37) UsableRulesProof (EQUIVALENT transformation)
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.
(38) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(eq, app'(s, x)), app'(s, y)) → APP'(app'(eq, x), y)
R is empty.
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(39) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(40) Obligation:
Q DP problem:
The TRS P consists of the following rules:
eq1(s(x), s(y)) → eq1(x, y)
R is empty.
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(41) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(42) Obligation:
Q DP problem:
The TRS P consists of the following rules:
eq1(s(x), s(y)) → eq1(x, y)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(43) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- eq1(s(x), s(y)) → eq1(x, y)
The graph contains the following edges 1 > 1, 2 > 2
(44) YES
(45) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(46) UsableRulesProof (EQUIVALENT transformation)
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.
(47) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(rm, n), app'(app'(add, m), x)) → APP'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
APP'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
APP'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → APP'(app'(rm, n), x)
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), y)
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(48) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(49) Obligation:
Q DP problem:
The TRS P consists of the following rules:
rm1(n, add(m, x)) → if_rm1(eq(n, m), n, add(m, x))
if_rm1(true, n, add(m, x)) → rm1(n, x)
if_rm1(false, n, add(m, x)) → rm1(n, x)
The TRS R consists of the following rules:
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(50) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(51) Obligation:
Q DP problem:
The TRS P consists of the following rules:
rm1(n, add(m, x)) → if_rm1(eq(n, m), n, add(m, x))
if_rm1(true, n, add(m, x)) → rm1(n, x)
if_rm1(false, n, add(m, x)) → rm1(n, x)
The TRS R consists of the following rules:
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
We have to consider all minimal (P,Q,R)-chains.
(52) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- rm1(n, add(m, x)) → if_rm1(eq(n, m), n, add(m, x))
The graph contains the following edges 1 >= 2, 2 >= 3
- if_rm1(true, n, add(m, x)) → rm1(n, x)
The graph contains the following edges 2 >= 1, 3 > 2
- if_rm1(false, n, add(m, x)) → rm1(n, x)
The graph contains the following edges 2 >= 1, 3 > 2
(53) YES
(54) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → APP'(app'(minsort, x), app'(app'(add, n), y))
The TRS R consists of the following rules:
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(55) UsableRulesProof (EQUIVALENT transformation)
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.
(56) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APP'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → APP'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil)
APP'(app'(minsort, app'(app'(add, n), x)), y) → APP'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
APP'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → APP'(app'(minsort, x), app'(app'(add, n), y))
The TRS R consists of the following rules:
app'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
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'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
The set Q consists of the following terms:
app'(app'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(57) ATransformationProof (EQUIVALENT transformation)
We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem.
(58) Obligation:
Q DP problem:
The TRS P consists of the following rules:
if_minsort1(true, add(n, x), y) → minsort1(app(rm(n, x), y), nil)
minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The TRS R consists of the following rules:
min(add(n, nil)) → n
min(add(n, add(m, x))) → if_min(le(n, m), add(n, add(m, x)))
if_min(true, add(n, add(m, x))) → min(add(n, x))
if_min(false, add(n, add(m, x))) → min(add(m, x))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
rm(n, nil) → nil
rm(n, add(m, x)) → if_rm(eq(n, m), n, add(m, x))
if_rm(true, n, add(m, x)) → rm(n, x)
app(nil, y) → y
app(add(n, x), y) → add(n, app(x, y))
if_rm(false, n, add(m, x)) → add(m, rm(n, x))
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
We have to consider all minimal (P,Q,R)-chains.
(59) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
minsort(nil, nil)
minsort(add(x0, x1), x2)
if_minsort(true, add(x0, x1), x2)
if_minsort(false, add(x0, x1), x2)
map(x0, nil)
map(x0, add(x1, x2))
filter(x0, nil)
filter(x0, add(x1, x2))
filter2(true, x0, x1, x2)
filter2(false, x0, x1, x2)
(60) Obligation:
Q DP problem:
The TRS P consists of the following rules:
if_minsort1(true, add(n, x), y) → minsort1(app(rm(n, x), y), nil)
minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The TRS R consists of the following rules:
min(add(n, nil)) → n
min(add(n, add(m, x))) → if_min(le(n, m), add(n, add(m, x)))
if_min(true, add(n, add(m, x))) → min(add(n, x))
if_min(false, add(n, add(m, x))) → min(add(m, x))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
rm(n, nil) → nil
rm(n, add(m, x)) → if_rm(eq(n, m), n, add(m, x))
if_rm(true, n, add(m, x)) → rm(n, x)
app(nil, y) → y
app(add(n, x), y) → add(n, app(x, y))
if_rm(false, n, add(m, x)) → add(m, rm(n, x))
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
We have to consider all minimal (P,Q,R)-chains.
(61) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04,JAR06].
The following pairs can be oriented strictly and are deleted.
if_minsort1(true, add(n, x), y) → minsort1(app(rm(n, x), y), nil)
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:
POL( app(x1, x2) ) = x1 + x2 |
POL( minsort1(x1, x2) ) = x1 + x2 |
POL( add(x1, x2) ) = x2 + 1 |
POL( if_rm(x1, ..., x3) ) = max{0, x1 + x3 - 1} |
POL( if_minsort1(x1, ..., x3) ) = max{0, 2x1 + x2 + x3 - 2} |
POL( if_min(x1, x2) ) = max{0, x2 - 2} |
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
rm(n, nil) → nil
rm(n, add(m, x)) → if_rm(eq(n, m), n, add(m, x))
if_rm(true, n, add(m, x)) → rm(n, x)
app(nil, y) → y
app(add(n, x), y) → add(n, app(x, y))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
if_rm(false, n, add(m, x)) → add(m, rm(n, x))
(62) Obligation:
Q DP problem:
The TRS P consists of the following rules:
minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The TRS R consists of the following rules:
min(add(n, nil)) → n
min(add(n, add(m, x))) → if_min(le(n, m), add(n, add(m, x)))
if_min(true, add(n, add(m, x))) → min(add(n, x))
if_min(false, add(n, add(m, x))) → min(add(m, x))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
rm(n, nil) → nil
rm(n, add(m, x)) → if_rm(eq(n, m), n, add(m, x))
if_rm(true, n, add(m, x)) → rm(n, x)
app(nil, y) → y
app(add(n, x), y) → add(n, app(x, y))
if_rm(false, n, add(m, x)) → add(m, rm(n, x))
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
We have to consider all minimal (P,Q,R)-chains.
(63) UsableRulesProof (EQUIVALENT transformation)
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.
(64) Obligation:
Q DP problem:
The TRS P consists of the following rules:
minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The TRS R consists of the following rules:
min(add(n, nil)) → n
min(add(n, add(m, x))) → if_min(le(n, m), add(n, add(m, x)))
if_min(true, add(n, add(m, x))) → min(add(n, x))
if_min(false, add(n, add(m, x))) → min(add(m, x))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
app(nil, x0)
app(add(x0, x1), x2)
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
We have to consider all minimal (P,Q,R)-chains.
(65) QReductionProof (EQUIVALENT transformation)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
app(nil, x0)
app(add(x0, x1), x2)
rm(x0, nil)
rm(x0, add(x1, x2))
if_rm(true, x0, add(x1, x2))
if_rm(false, x0, add(x1, x2))
(66) Obligation:
Q DP problem:
The TRS P consists of the following rules:
minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The TRS R consists of the following rules:
min(add(n, nil)) → n
min(add(n, add(m, x))) → if_min(le(n, m), add(n, add(m, x)))
if_min(true, add(n, add(m, x))) → min(add(n, x))
if_min(false, add(n, add(m, x))) → min(add(m, x))
eq(0, 0) → true
eq(0, s(x)) → false
eq(s(x), 0) → false
eq(s(x), s(y)) → eq(x, y)
le(0, y) → true
le(s(x), 0) → false
le(s(x), s(y)) → le(x, y)
The set Q consists of the following terms:
eq(0, 0)
eq(0, s(x0))
eq(s(x0), 0)
eq(s(x0), s(x1))
le(0, x0)
le(s(x0), 0)
le(s(x0), s(x1))
min(add(x0, nil))
min(add(x0, add(x1, x2)))
if_min(true, add(x0, add(x1, x2)))
if_min(false, add(x0, add(x1, x2)))
We have to consider all minimal (P,Q,R)-chains.
(67) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- if_minsort1(false, add(n, x), y) → minsort1(x, add(n, y))
The graph contains the following edges 2 > 1
- minsort1(add(n, x), y) → if_minsort1(eq(n, min(add(n, x))), add(n, x), y)
The graph contains the following edges 1 >= 2, 2 >= 3
(68) YES
(69) 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'(eq, 0), 0) → true
app'(app'(eq, 0), app'(s, x)) → false
app'(app'(eq, app'(s, x)), 0) → false
app'(app'(eq, app'(s, x)), app'(s, y)) → app'(app'(eq, x), 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'(min, app'(app'(add, n), nil)) → n
app'(min, app'(app'(add, n), app'(app'(add, m), x))) → app'(app'(if_min, app'(app'(le, n), m)), app'(app'(add, n), app'(app'(add, m), x)))
app'(app'(if_min, true), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, n), x))
app'(app'(if_min, false), app'(app'(add, n), app'(app'(add, m), x))) → app'(min, app'(app'(add, m), x))
app'(app'(rm, n), nil) → nil
app'(app'(rm, n), app'(app'(add, m), x)) → app'(app'(app'(if_rm, app'(app'(eq, n), m)), n), app'(app'(add, m), x))
app'(app'(app'(if_rm, true), n), app'(app'(add, m), x)) → app'(app'(rm, n), x)
app'(app'(app'(if_rm, false), n), app'(app'(add, m), x)) → app'(app'(add, m), app'(app'(rm, n), x))
app'(app'(minsort, nil), nil) → nil
app'(app'(minsort, app'(app'(add, n), x)), y) → app'(app'(app'(if_minsort, app'(app'(eq, n), app'(min, app'(app'(add, n), x)))), app'(app'(add, n), x)), y)
app'(app'(app'(if_minsort, true), app'(app'(add, n), x)), y) → app'(app'(add, n), app'(app'(minsort, app'(app'(app, app'(app'(rm, n), x)), y)), nil))
app'(app'(app'(if_minsort, false), app'(app'(add, n), x)), y) → app'(app'(minsort, x), app'(app'(add, n), y))
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'(eq, 0), 0)
app'(app'(eq, 0), app'(s, x0))
app'(app'(eq, app'(s, x0)), 0)
app'(app'(eq, 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'(min, app'(app'(add, x0), nil))
app'(min, app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, true), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(if_min, false), app'(app'(add, x0), app'(app'(add, x1), x2)))
app'(app'(rm, x0), nil)
app'(app'(rm, x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, true), x0), app'(app'(add, x1), x2))
app'(app'(app'(if_rm, false), x0), app'(app'(add, x1), x2))
app'(app'(minsort, nil), nil)
app'(app'(minsort, app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, true), app'(app'(add, x0), x1)), x2)
app'(app'(app'(if_minsort, false), app'(app'(add, x0), x1)), x2)
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.
(70) QDPSizeChangeProof (EQUIVALENT transformation)
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:
- APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(f, x)
The graph contains the following edges 1 > 1, 2 > 2
- APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(f, x)
The graph contains the following edges 1 > 1, 2 > 2
- APP'(app'(map, f), app'(app'(add, x), xs)) → APP'(app'(map, f), xs)
The graph contains the following edges 1 >= 1, 2 > 2
- APP'(app'(filter, f), app'(app'(add, x), xs)) → APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs)
The graph contains the following edges 2 > 2
- APP'(app'(app'(app'(filter2, true), f), x), xs) → APP'(app'(filter, f), xs)
The graph contains the following edges 2 >= 2
- APP'(app'(app'(app'(filter2, false), f), x), xs) → APP'(app'(filter, f), xs)
The graph contains the following edges 2 >= 2
(71) YES