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