Termination w.r.t. Q proof of /tmp/tmpHHbIN9/otto13.trs

Termination w.r.t. Q of the given QTRS could not be shown:

0 QTRS

↳1 AAECC Innermost (⇔)

↳2 QTRS

↳3 DependencyPairsProof (⇔)

↳4 QDP

↳5 DependencyGraphProof (⇔)

↳6 AND

  ↳7 QDP

    ↳8 QDPOrderProof (⇔)

    ↳9 QDP

    ↳10 PisEmptyProof (⇔)

    ↳11 TRUE

  ↳12 QDP

    ↳13 QDPOrderProof (⇔)

    ↳14 QDP

    ↳15 PisEmptyProof (⇔)

    ↳16 TRUE

  ↳17 QDP

    ↳18 QDPOrderProof (⇔)

    ↳19 QDP

    ↳20 PisEmptyProof (⇔)

    ↳21 TRUE

  ↳22 QDP

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

Q is empty.

(1) AAECC Innermost (EQUIVALENT transformation)

We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is

double(0) → 0
double(s(x)) → s(s(double(x)))
le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)

The TRS R 2 is

triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The signature Sigma is {triple, if, true}

(2) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

(3) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(4) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LE(0, y, z) → GREATER(y, z)
LE(s(x), s(y), s(z)) → LE(x, y, z)
GREATER(s(x), s(y)) → GREATER(x, y)
DOUBLE(s(x)) → DOUBLE(x)
TRIPLE(x) → IF(le(x, x, double(x)), x, 0, 0)
TRIPLE(x) → LE(x, x, double(x))
TRIPLE(x) → DOUBLE(x)
IF(first, x, y, z) → IF(le(s(x), y, s(z)), s(x), y, s(z))
IF(first, x, y, z) → LE(s(x), y, s(z))
IF(second, x, y, z) → IF(le(s(x), s(y), z), s(x), s(y), z)
IF(second, x, y, z) → LE(s(x), s(y), z)

The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 6 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Q DP problem:
The TRS P consists of the following rules:

DOUBLE(s(x)) → DOUBLE(x)

The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(8) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

DOUBLE(s(x)) → DOUBLE(x)

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
DOUBLE(x1) = DOUBLE(x1)
s(x1) = s(x1)
le(x1, x2, x3) = le(x2, x3)
0 = 0
greater(x1, x2) = greater(x1, x2)
false = false
first = first
second = second
double(x1) = double(x1)
triple(x1) = triple(x1)
if(x1, x2, x3, x4) = if
true = true

Lexicographic path order with status [LPO].
Quasi-Precedence:

DOUBLE₁ > [le₂, greater₂, false, first, second, if, true]
double₁ > s₁ > [le₂, greater₂, false, first, second, if, true]
double₁ > 0 > [le₂, greater₂, false, first, second, if, true]
triple₁ > 0 > [le₂, greater₂, false, first, second, if, true]

Status:

DOUBLE₁: [1]
s₁: [1]
le₂: [2,1]
0: []
greater₂: [2,1]
false: []
first: []
second: []
double₁: [1]
triple₁: [1]
if: []
true: []

The following usable rules [FROCOS05] were oriented:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

(9) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(10) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(11) TRUE

(12) Obligation:

Q DP problem:
The TRS P consists of the following rules:

GREATER(s(x), s(y)) → GREATER(x, y)

The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(13) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

GREATER(s(x), s(y)) → GREATER(x, y)

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
GREATER(x1, x2) = GREATER(x2)
s(x1) = s(x1)
le(x1, x2, x3) = le(x2, x3)
0 = 0
greater(x1, x2) = greater(x2)
false = false
first = first
second = second
double(x1) = double(x1)
triple(x1) = triple(x1)
if(x1, x2, x3, x4) = if
true = true

Lexicographic path order with status [LPO].
Quasi-Precedence:

double₁ > s₁ > GREATER₁ > [le₂, greater₁, false, first, second, if, true]
double₁ > 0 > [le₂, greater₁, false, first, second, if, true]
triple₁ > 0 > [le₂, greater₁, false, first, second, if, true]

Status:

GREATER₁: [1]
s₁: [1]
le₂: [2,1]
0: []
greater₁: [1]
false: []
first: []
second: []
double₁: [1]
triple₁: [1]
if: []
true: []

The following usable rules [FROCOS05] were oriented:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

(14) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(15) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(16) TRUE

(17) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LE(s(x), s(y), s(z)) → LE(x, y, z)

The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(18) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

LE(s(x), s(y), s(z)) → LE(x, y, z)

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
LE(x1, x2, x3) = LE(x3)
s(x1) = s(x1)
le(x1, x2, x3) = le(x2, x3)
0 = 0
greater(x1, x2) = greater(x2)
false = false
first = first
second = second
double(x1) = double(x1)
triple(x1) = triple(x1)
if(x1, x2, x3, x4) = if
true = true

Lexicographic path order with status [LPO].
Quasi-Precedence:

double₁ > s₁ > [LE₁, le₂, greater₁, false, first, second, if, true]
double₁ > 0 > [LE₁, le₂, greater₁, false, first, second, if, true]
triple₁ > 0 > [LE₁, le₂, greater₁, false, first, second, if, true]

Status:

LE₁: [1]
s₁: [1]
le₂: [2,1]
0: []
greater₁: [1]
false: []
first: []
second: []
double₁: [1]
triple₁: [1]
if: []
true: []

The following usable rules [FROCOS05] were oriented:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

(19) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.

(20) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(21) TRUE

(22) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(second, x, y, z) → IF(le(s(x), s(y), z), s(x), s(y), z)
IF(first, x, y, z) → IF(le(s(x), y, s(z)), s(x), y, s(z))

The TRS R consists of the following rules:

le(0, y, z) → greater(y, z)
le(s(x), 0, z) → false
le(s(x), s(y), 0) → false
le(s(x), s(y), s(z)) → le(x, y, z)
greater(x, 0) → first
greater(0, s(y)) → second
greater(s(x), s(y)) → greater(x, y)
double(0) → 0
double(s(x)) → s(s(double(x)))
triple(x) → if(le(x, x, double(x)), x, 0, 0)
if(false, x, y, z) → true
if(first, x, y, z) → if(le(s(x), y, s(z)), s(x), y, s(z))
if(second, x, y, z) → if(le(s(x), s(y), z), s(x), s(y), z)

The set Q consists of the following terms:

le(0, x0, x1)
le(s(x0), 0, x1)
le(s(x0), s(x1), 0)
le(s(x0), s(x1), s(x2))
greater(x0, 0)
greater(0, s(x0))
greater(s(x0), s(x1))
double(0)
double(s(x0))
triple(x0)
if(false, x0, x1, x2)
if(first, x0, x1, x2)
if(second, x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.