Term Rewriting System R:
[x, y, z]
minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
double(0) -> 0
double(s(x)) -> s(s(double(x)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
plus(s(x), y) -> plus(x, s(y))
plus(s(x), y) -> s(plus(minus(x, y), double(y)))
plus(s(plus(x, y)), z) -> s(plus(plus(x, y), z))

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

MINUS(s(x), s(y)) -> MINUS(x, y)
DOUBLE(s(x)) -> DOUBLE(x)
PLUS(s(x), y) -> PLUS(x, y)
PLUS(s(x), y) -> PLUS(x, s(y))
PLUS(s(x), y) -> PLUS(minus(x, y), double(y))
PLUS(s(x), y) -> MINUS(x, y)
PLUS(s(x), y) -> DOUBLE(y)
PLUS(s(plus(x, y)), z) -> PLUS(plus(x, y), z)

Furthermore, R contains three SCCs.


   R
DPs
       →DP Problem 1
Usable Rules (Innermost)
       →DP Problem 2
UsableRules
       →DP Problem 3
UsableRules


Dependency Pair:

MINUS(s(x), s(y)) -> MINUS(x, y)


Rules:


minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
double(0) -> 0
double(s(x)) -> s(s(double(x)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
plus(s(x), y) -> plus(x, s(y))
plus(s(x), y) -> s(plus(minus(x, y), double(y)))
plus(s(plus(x, y)), z) -> s(plus(plus(x, y), z))


Strategy:

innermost




As we are in the innermost case, we can delete all 9 non-usable-rules.


   R
DPs
       →DP Problem 1
UsableRules
           →DP Problem 4
Size-Change Principle
       →DP Problem 2
UsableRules
       →DP Problem 3
UsableRules


Dependency Pair:

MINUS(s(x), s(y)) -> MINUS(x, y)


Rule:

none


Strategy:

innermost




We number the DPs as follows:
  1. MINUS(s(x), s(y)) -> MINUS(x, y)
and get the following Size-Change Graph(s):
{1} , {1}
1>1
2>2

which lead(s) to this/these maximal multigraph(s):
{1} , {1}
1>1
2>2

DP: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.
trivial

with Argument Filtering System:
s(x1) -> s(x1)

We obtain no new DP problems.


   R
DPs
       →DP Problem 1
UsableRules
       →DP Problem 2
Usable Rules (Innermost)
       →DP Problem 3
UsableRules


Dependency Pair:

DOUBLE(s(x)) -> DOUBLE(x)


Rules:


minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
double(0) -> 0
double(s(x)) -> s(s(double(x)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
plus(s(x), y) -> plus(x, s(y))
plus(s(x), y) -> s(plus(minus(x, y), double(y)))
plus(s(plus(x, y)), z) -> s(plus(plus(x, y), z))


Strategy:

innermost




As we are in the innermost case, we can delete all 9 non-usable-rules.


   R
DPs
       →DP Problem 1
UsableRules
       →DP Problem 2
UsableRules
           →DP Problem 5
Size-Change Principle
       →DP Problem 3
UsableRules


Dependency Pair:

DOUBLE(s(x)) -> DOUBLE(x)


Rule:

none


Strategy:

innermost




We number the DPs as follows:
  1. DOUBLE(s(x)) -> DOUBLE(x)
and get the following Size-Change Graph(s):
{1} , {1}
1>1

which lead(s) to this/these maximal multigraph(s):
{1} , {1}
1>1

DP: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.
trivial

with Argument Filtering System:
s(x1) -> s(x1)

We obtain no new DP problems.


   R
DPs
       →DP Problem 1
UsableRules
       →DP Problem 2
UsableRules
       →DP Problem 3
Usable Rules (Innermost)


Dependency Pairs:

PLUS(s(x), y) -> PLUS(minus(x, y), double(y))
PLUS(s(x), y) -> PLUS(x, s(y))
PLUS(s(x), y) -> PLUS(x, y)


Rules:


minus(x, 0) -> x
minus(s(x), s(y)) -> minus(x, y)
double(0) -> 0
double(s(x)) -> s(s(double(x)))
plus(0, y) -> y
plus(s(x), y) -> s(plus(x, y))
plus(s(x), y) -> plus(x, s(y))
plus(s(x), y) -> s(plus(minus(x, y), double(y)))
plus(s(plus(x, y)), z) -> s(plus(plus(x, y), z))


Strategy:

innermost




As we are in the innermost case, we can delete all 5 non-usable-rules.


   R
DPs
       →DP Problem 1
UsableRules
       →DP Problem 2
UsableRules
       →DP Problem 3
UsableRules
           →DP Problem 6
Argument Filtering and Ordering


Dependency Pairs:

PLUS(s(x), y) -> PLUS(minus(x, y), double(y))
PLUS(s(x), y) -> PLUS(x, s(y))
PLUS(s(x), y) -> PLUS(x, y)


Rules:


minus(s(x), s(y)) -> minus(x, y)
minus(x, 0) -> x
double(0) -> 0
double(s(x)) -> s(s(double(x)))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

PLUS(s(x), y) -> PLUS(minus(x, y), double(y))
PLUS(s(x), y) -> PLUS(x, s(y))
PLUS(s(x), y) -> PLUS(x, y)


The following usable rules w.r.t. the AFS can be oriented:

minus(s(x), s(y)) -> minus(x, y)
minus(x, 0) -> x


Used ordering: Lexicographic Path Order with Precedence:
trivial

resulting in one new DP problem.
Used Argument Filtering System:
PLUS(x1, x2) -> x1
s(x1) -> s(x1)
minus(x1, x2) -> x1


   R
DPs
       →DP Problem 1
UsableRules
       →DP Problem 2
UsableRules
       →DP Problem 3
UsableRules
           →DP Problem 6
AFS
             ...
               →DP Problem 7
Dependency Graph


Dependency Pair:


Rules:


minus(s(x), s(y)) -> minus(x, y)
minus(x, 0) -> x
double(0) -> 0
double(s(x)) -> s(s(double(x)))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

Innermost Termination of R successfully shown.
Duration:
0:00 minutes