Term Rewriting System R:
[x, y, p, xs]
app(app(and, true), true) -> true
app(app(and, x), false) -> false
app(app(and, false), y) -> false
app(app(or, true), y) -> true
app(app(or, x), true) -> true
app(app(or, false), false) -> false
app(app(forall, p), nil) -> true
app(app(forall, p), app(app(cons, x), xs)) -> app(app(and, app(p, x)), app(app(forall, p), xs))
app(app(forsome, p), nil) -> false
app(app(forsome, p), app(app(cons, x), xs)) -> app(app(or, app(p, x)), app(app(forsome, p), xs))

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

APP(app(forall, p), app(app(cons, x), xs)) -> APP(app(and, app(p, x)), app(app(forall, p), xs))
APP(app(forall, p), app(app(cons, x), xs)) -> APP(and, app(p, x))
APP(app(forall, p), app(app(cons, x), xs)) -> APP(p, x)
APP(app(forall, p), app(app(cons, x), xs)) -> APP(app(forall, p), xs)
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(app(or, app(p, x)), app(app(forsome, p), xs))
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(or, app(p, x))
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(p, x)
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(app(forsome, p), xs)

Furthermore, R contains one SCC.


   R
DPs
       →DP Problem 1
Remaining Obligation(s)




The following remains to be proven:
Dependency Pairs:

APP(app(forsome, p), app(app(cons, x), xs)) -> APP(app(forsome, p), xs)
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(p, x)
APP(app(forsome, p), app(app(cons, x), xs)) -> APP(app(or, app(p, x)), app(app(forsome, p), xs))
APP(app(forall, p), app(app(cons, x), xs)) -> APP(app(forall, p), xs)
APP(app(forall, p), app(app(cons, x), xs)) -> APP(p, x)
APP(app(forall, p), app(app(cons, x), xs)) -> APP(app(and, app(p, x)), app(app(forall, p), xs))


Rules:


app(app(and, true), true) -> true
app(app(and, x), false) -> false
app(app(and, false), y) -> false
app(app(or, true), y) -> true
app(app(or, x), true) -> true
app(app(or, false), false) -> false
app(app(forall, p), nil) -> true
app(app(forall, p), app(app(cons, x), xs)) -> app(app(and, app(p, x)), app(app(forall, p), xs))
app(app(forsome, p), nil) -> false
app(app(forsome, p), app(app(cons, x), xs)) -> app(app(or, app(p, x)), app(app(forsome, p), xs))


Strategy:

innermost



Innermost Termination of R could not be shown.
Duration:
0:04 minutes