Term Rewriting System R:
[x, y]
+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

+'(x, s(y)) -> +'(x, y)
*'(x, s(y)) -> +'(*(x, y), x)
*'(x, s(y)) -> *'(x, y)
GE(s(x), s(y)) -> GE(x, y)
-'(s(x), s(y)) -> -'(x, y)
FACT(x) -> IFFACT(x, ge(x, s(s(0))))
FACT(x) -> GE(x, s(s(0)))
IFFACT(x, true) -> *'(x, fact(-(x, s(0))))
IFFACT(x, true) -> FACT(-(x, s(0)))
IFFACT(x, true) -> -'(x, s(0))

Furthermore, R contains five SCCs.


   R
DPs
       →DP Problem 1
Argument Filtering and Ordering
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:

+'(x, s(y)) -> +'(x, y)


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





The following dependency pair can be strictly oriented:

+'(x, s(y)) -> +'(x, y)


There are no usable rules using the Ce-refinement that need to be oriented.
Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
trivial

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


   R
DPs
       →DP Problem 1
AFS
           →DP Problem 6
Dependency Graph
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
Argument Filtering and Ordering
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:

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


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





The following dependency pair can be strictly oriented:

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


There are no usable rules using the Ce-refinement that need to be oriented.
Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
trivial

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


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
           →DP Problem 7
Dependency Graph
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
Argument Filtering and Ordering
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:

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


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





The following dependency pair can be strictly oriented:

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


There are no usable rules using the Ce-refinement that need to be oriented.
Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
trivial

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


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
           →DP Problem 8
Dependency Graph
       →DP Problem 4
AFS
       →DP Problem 5
Remaining


Dependency Pair:


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
Argument Filtering and Ordering
       →DP Problem 5
Remaining


Dependency Pair:

*'(x, s(y)) -> *'(x, y)


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





The following dependency pair can be strictly oriented:

*'(x, s(y)) -> *'(x, y)


There are no usable rules using the Ce-refinement that need to be oriented.
Used ordering: Lexicographic Path Order with Non-Strict Precedence with Quasi Precedence:
trivial

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


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
           →DP Problem 9
Dependency Graph
       →DP Problem 5
Remaining


Dependency Pair:


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)





Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
AFS
       →DP Problem 2
AFS
       →DP Problem 3
AFS
       →DP Problem 4
AFS
       →DP Problem 5
Remaining Obligation(s)




The following remains to be proven:
Dependency Pairs:

IFFACT(x, true) -> FACT(-(x, s(0)))
FACT(x) -> IFFACT(x, ge(x, s(s(0))))


Rules:


+(x, 0) -> x
+(x, s(y)) -> s(+(x, y))
*(x, 0) -> 0
*(x, s(y)) -> +(*(x, y), x)
ge(x, 0) -> true
ge(0, s(y)) -> false
ge(s(x), s(y)) -> ge(x, y)
-(x, 0) -> x
-(s(x), s(y)) -> -(x, y)
fact(x) -> iffact(x, ge(x, s(s(0))))
iffact(x, true) -> *(x, fact(-(x, s(0))))
iffact(x, false) -> s(0)




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