TIMEOUT
The TRS could not be proven terminating. The proof attempt took 60109 ms.
The following DP Processors were used
Problem 1 was processed with processor DependencyGraph (35ms).
| – Problem 2 was processed with processor BackwardInstantiation (2ms).
| | – Problem 5 remains open; application of the following processors failed [ForwardInstantiation (3ms), Propagation (1ms), ForwardNarrowing (1ms), BackwardInstantiation (1ms), ForwardInstantiation (1ms), Propagation (2ms)].
| – Problem 3 was processed with processor SubtermCriterion (1ms).
| – Problem 4 was processed with processor SubtermCriterion (2ms).
The following open problems remain:
Open Dependency Pair Problem 2
Dependency Pairs
| if#(false, x, y) | → | minus#(p(x), y) | | minus#(x, y) | → | if#(le(x, y), x, y) |
Rewrite Rules
| p(0) | → | s(s(0)) | | p(s(x)) | → | x |
| p(p(s(x))) | → | p(x) | | le(p(s(x)), x) | → | le(x, x) |
| le(0, y) | → | true | | le(s(x), 0) | → | false |
| le(s(x), s(y)) | → | le(x, y) | | minus(x, y) | → | if(le(x, y), x, y) |
| if(true, x, y) | → | 0 | | if(false, x, y) | → | s(minus(p(x), y)) |
Original Signature
Termination of terms over the following signature is verified: minus, 0, le, s, if, p, false, true
Problem 1: DependencyGraph
Dependency Pair Problem
Dependency Pairs
| minus#(x, y) | → | le#(x, y) | | if#(false, x, y) | → | minus#(p(x), y) |
| le#(p(s(x)), x) | → | le#(x, x) | | le#(s(x), s(y)) | → | le#(x, y) |
| minus#(x, y) | → | if#(le(x, y), x, y) | | p#(p(s(x))) | → | p#(x) |
| if#(false, x, y) | → | p#(x) |
Rewrite Rules
| p(0) | → | s(s(0)) | | p(s(x)) | → | x |
| p(p(s(x))) | → | p(x) | | le(p(s(x)), x) | → | le(x, x) |
| le(0, y) | → | true | | le(s(x), 0) | → | false |
| le(s(x), s(y)) | → | le(x, y) | | minus(x, y) | → | if(le(x, y), x, y) |
| if(true, x, y) | → | 0 | | if(false, x, y) | → | s(minus(p(x), y)) |
Original Signature
Termination of terms over the following signature is verified: 0, minus, s, le, if, p, true, false
Strategy
The following SCCs where found
| if#(false, x, y) → minus#(p(x), y) | minus#(x, y) → if#(le(x, y), x, y) |
| le#(s(x), s(y)) → le#(x, y) | le#(p(s(x)), x) → le#(x, x) |
Problem 2: BackwardInstantiation
Dependency Pair Problem
Dependency Pairs
| if#(false, x, y) | → | minus#(p(x), y) | | minus#(x, y) | → | if#(le(x, y), x, y) |
Rewrite Rules
| p(0) | → | s(s(0)) | | p(s(x)) | → | x |
| p(p(s(x))) | → | p(x) | | le(p(s(x)), x) | → | le(x, x) |
| le(0, y) | → | true | | le(s(x), 0) | → | false |
| le(s(x), s(y)) | → | le(x, y) | | minus(x, y) | → | if(le(x, y), x, y) |
| if(true, x, y) | → | 0 | | if(false, x, y) | → | s(minus(p(x), y)) |
Original Signature
Termination of terms over the following signature is verified: 0, minus, s, le, if, p, true, false
Strategy
Instantiation
For all potential predecessors l → r of the rule minus
#(
x,
y) → if
#(le(
x,
y),
x,
y) on dependency pair chains it holds that:
- minus#(x, y) matches r,
- all variables of minus#(x, y) are embedded in constructor contexts, i.e., each subterm of minus#(x, y), containing a variable is rooted by a constructor symbol.
Thus, minus
#(
x,
y) → if
#(le(
x,
y),
x,
y) is replaced by instances determined through the above matching. These instances are:
| minus#(p(_x), _y) → if#(le(p(_x), _y), p(_x), _y) |
Problem 3: SubtermCriterion
Dependency Pair Problem
Dependency Pairs
Rewrite Rules
| p(0) | → | s(s(0)) | | p(s(x)) | → | x |
| p(p(s(x))) | → | p(x) | | le(p(s(x)), x) | → | le(x, x) |
| le(0, y) | → | true | | le(s(x), 0) | → | false |
| le(s(x), s(y)) | → | le(x, y) | | minus(x, y) | → | if(le(x, y), x, y) |
| if(true, x, y) | → | 0 | | if(false, x, y) | → | s(minus(p(x), y)) |
Original Signature
Termination of terms over the following signature is verified: 0, minus, s, le, if, p, true, false
Strategy
Projection
The following projection was used:
Thus, the following dependency pairs are removed:
Problem 4: SubtermCriterion
Dependency Pair Problem
Dependency Pairs
| le#(s(x), s(y)) | → | le#(x, y) | | le#(p(s(x)), x) | → | le#(x, x) |
Rewrite Rules
| p(0) | → | s(s(0)) | | p(s(x)) | → | x |
| p(p(s(x))) | → | p(x) | | le(p(s(x)), x) | → | le(x, x) |
| le(0, y) | → | true | | le(s(x), 0) | → | false |
| le(s(x), s(y)) | → | le(x, y) | | minus(x, y) | → | if(le(x, y), x, y) |
| if(true, x, y) | → | 0 | | if(false, x, y) | → | s(minus(p(x), y)) |
Original Signature
Termination of terms over the following signature is verified: 0, minus, s, le, if, p, true, false
Strategy
Projection
The following projection was used:
Thus, the following dependency pairs are removed:
| le#(p(s(x)), x) | → | le#(x, x) | | le#(s(x), s(y)) | → | le#(x, y) |