Term Rewriting System R:
[x, y, z]
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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

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(plus, app(s, x)), y) -> APP(s, app(app(plus, x), y))
APP(app(plus, app(s, x)), y) -> APP(app(plus, x), y)
APP(app(plus, app(s, x)), y) -> APP(plus, x)
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(plus, app(app(minus, y), app(s, app(s, z))))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(plus, app(app(plus, y), app(s, app(s, z))))

Furthermore, R contains one SCC.


   R
DPs
       →DP Problem 1
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
two new Dependency Pairs are created:

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x''), 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))
four new Dependency Pairs are created:

APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, 0))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 3
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x''), 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x), app(s, 0)))
two new Dependency Pairs are created:

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 4
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x''), 0))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x''), 0))
two new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 5
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, 0))
two new Dependency Pairs are created:

APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 6
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(app(plus, x''), app(s, 0))))
four new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 7
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x), app(s, 0)))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 8
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), app(app(minus, x'''), 0))
two new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 9
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), app(app(minus, x''), 0))
two new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 10
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(minus, y), app(s, app(s, z)))), x''')
one new Dependency Pair is created:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 11
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, 0)))
two new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 12
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
four new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 13
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 14
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), app(app(minus, x''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 15
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), app(app(minus, x'''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 16
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), app(app(minus, x''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 17
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, 0))))
two new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 18
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
four new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 19
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x), app(s, 0)))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 20
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 21
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 22
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x'''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 23
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), app(app(minus, x''), 0))
three new Dependency Pairs are created:

APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 24
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, 0)))))
two new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(s, 0)))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 25
Narrowing Transformation


Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x0))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x0), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x''), y')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'), y'')), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x'''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x''''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x'''))))), app(s, app(s, app(s, app(s, y'')))))) -> APP(app(plus, app(app(minus, x'''), y'')), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, app(s, app(s, app(s, app(s, y'))))))) -> APP(app(plus, app(app(minus, x''), y')), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, app(s, x''''))))), app(s, app(s, app(s, app(s, 0)))))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, x'')))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(plus, app(s, app(s, 0))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, 0))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x0))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x0), z'')), x''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x0'))), app(s, app(s, 0)))) -> APP(app(plus, x0'), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, x''))), app(s, app(s, 0)))) -> APP(app(plus, x''), app(app(minus, x'''), 0))
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, app(s, x'''))), app(s, app(s, z'')))) -> APP(app(plus, app(app(minus, x'''), z'')), x'''')
APP(app(plus, app(app(minus, app(s, x'')), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x''), 0))
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, app(s, x''')))), app(s, app(s, app(s, 0))))) -> APP(app(plus, x'''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, app(s, x'))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(app(plus, x'), app(s, 0)))))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(s, 0)))
APP(app(plus, app(app(plus, app(s, 0)), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, 0)))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x'), app(s, z'))), x''')
APP(app(plus, app(app(minus, app(s, x'''')), app(s, 0))), app(app(minus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(app(minus, x''), app(s, z'))), x'''')
APP(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, app(s, app(s, x''''))), app(s, app(s, 0)))) -> APP(app(plus, x''''), app(app(minus, x), app(s, 0)))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, app(s, x'')), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(app(plus, x''), app(s, 0))))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, app(s, x')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x'), app(s, app(s, z'))))), app(s, 0))
APP(app(plus, app(app(plus, 0), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, 0))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(app(plus, x), app(s, 0)))
APP(app(plus, app(s, x)), y) -> APP(app(plus, 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(app(quot, app(app(minus, x), y)), app(s, y))
APP(app(minus, app(s, x)), app(s, y)) -> APP(app(minus, x), y)
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(minus, x'), y')), x''')


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(plus, 0), y) -> y
app(app(plus, app(s, x)), y) -> app(s, app(app(plus, x), y))
app(app(plus, app(app(minus, x), app(s, 0))), app(app(minus, y), app(s, app(s, z)))) -> app(app(plus, app(app(minus, y), app(s, app(s, z)))), app(app(minus, x), app(s, 0)))
app(app(plus, app(app(plus, x), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> app(app(plus, app(app(plus, y), app(s, app(s, z)))), app(app(plus, x), app(s, 0)))





On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
four new Dependency Pairs are created:

APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, 0))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))))

The transformation is resulting in one new DP problem:



   R
DPs
       →DP Problem 1
Nar
           →DP Problem 2
Nar
             ...
               →DP Problem 26
Remaining Obligation(s)




The following remains to be proven:
Dependency Pairs:

APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, app(s, x'')))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(s, app(app(plus, x''), app(s, 0))))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, 0))))), app(s, 0))), app(app(plus, y), app(s, app(s, z)))) -> APP(app(plus, app(app(plus, y), app(s, app(s, z)))), app(s, app(s, app(s, app(s, app(s, 0))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, app(s, x'')), app(s, app(s, z')))) -> APP(app(plus, app(s, app(app(plus, x''), app(s, app(s, z'))))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, app(s, x'))))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(s, app(app(plus, x'), app(s, 0)))))))
APP(app(plus, app(app(plus, app(s, app(s, app(s, 0)))), app(s, 0))), app(app(plus, 0), app(s, app(s, z')))) -> APP(app(plus, app(s, app(s, z'))), app(s, app(s, app(s, app(s, 0)))))
APP(app(plus, app(app(minus, app(s, x''')), app(s, 0))), app(app(minus, app(s, app(s, app(s, x')))), app(s, app(s, app(s, y'))))) -> APP(app(plus, app(app(