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