/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) QTRS
(1) Overlay + Local Confluence [EQUIVALENT, 0 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 0 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) QDP
(7) TransformationProof [EQUIVALENT, 0 ms]
(8) QDP
(9) TransformationProof [EQUIVALENT, 0 ms]
(10) QDP
(11) TransformationProof [EQUIVALENT, 0 ms]
(12) QDP
(13) TransformationProof [EQUIVALENT, 0 ms]
(14) QDP
(15) TransformationProof [EQUIVALENT, 0 ms]
(16) QDP
(17) TransformationProof [EQUIVALENT, 0 ms]
(18) QDP
(19) TransformationProof [EQUIVALENT, 0 ms]
(20) QDP
(21) SemLabProof [SOUND, 186 ms]
(22) QDP
(23) DependencyGraphProof [EQUIVALENT, 0 ms]
(24) QDP
(25) MRRProof [EQUIVALENT, 11 ms]
(26) QDP
(27) DependencyGraphProof [EQUIVALENT, 0 ms]
(28) QDP
(29) MRRProof [EQUIVALENT, 0 ms]
(30) QDP
(31) PisEmptyProof [EQUIVALENT, 0 ms]
(32) YES


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

Q is empty.

----------------------------------------

(1) Overlay + Local Confluence (EQUIVALENT)
The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)


----------------------------------------

(3) DependencyPairsProof (EQUIVALENT)
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:

   F(f(a, x), y) -> F(a, f(f(x, h(y)), a))
   F(f(a, x), y) -> F(f(x, h(y)), a)
   F(f(a, x), y) -> F(x, h(y))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(6)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x), y) -> F(x, h(y))
   F(f(a, x), y) -> F(f(x, h(y)), a)

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(7) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(f(a, x), y) -> F(x, h(y)) we obtained the following new rules [LPAR04]:

   (F(f(a, x0), h(z1)) -> F(x0, h(h(z1))),F(f(a, x0), h(z1)) -> F(x0, h(h(z1))))
   (F(f(a, x0), a) -> F(x0, h(a)),F(f(a, x0), a) -> F(x0, h(a)))


----------------------------------------

(8)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x), y) -> F(f(x, h(y)), a)
   F(f(a, x0), h(z1)) -> F(x0, h(h(z1)))
   F(f(a, x0), a) -> F(x0, h(a))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(9) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(f(a, x), y) -> F(f(x, h(y)), a) we obtained the following new rules [LPAR04]:

   (F(f(a, x0), a) -> F(f(x0, h(a)), a),F(f(a, x0), a) -> F(f(x0, h(a)), a))
   (F(f(a, x0), h(h(z1))) -> F(f(x0, h(h(h(z1)))), a),F(f(a, x0), h(h(z1))) -> F(f(x0, h(h(h(z1)))), a))
   (F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a),F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a))


----------------------------------------

(10)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), h(z1)) -> F(x0, h(h(z1)))
   F(f(a, x0), a) -> F(x0, h(a))
   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(h(z1))) -> F(f(x0, h(h(h(z1)))), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(11) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(f(a, x0), h(z1)) -> F(x0, h(h(z1))) we obtained the following new rules [LPAR04]:

   (F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1)))),F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1)))))
   (F(f(a, x0), h(a)) -> F(x0, h(h(a))),F(f(a, x0), h(a)) -> F(x0, h(h(a))))


----------------------------------------

(12)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), a) -> F(x0, h(a))
   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(h(z1))) -> F(f(x0, h(h(h(z1)))), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)
   F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1))))
   F(f(a, x0), h(a)) -> F(x0, h(h(a)))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(13) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(f(a, x0), h(h(z1))) -> F(f(x0, h(h(h(z1)))), a) we obtained the following new rules [LPAR04]:

   (F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a),F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a))
   (F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a),F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a))


----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), a) -> F(x0, h(a))
   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)
   F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1))))
   F(f(a, x0), h(a)) -> F(x0, h(h(a)))
   F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a)
   F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a)

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(15) TransformationProof (EQUIVALENT)
By forward instantiating [JAR06] the rule F(f(a, x0), a) -> F(x0, h(a)) we obtained the following new rules [LPAR04]:

   (F(f(a, f(a, y_0)), a) -> F(f(a, y_0), h(a)),F(f(a, f(a, y_0)), a) -> F(f(a, y_0), h(a)))


----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)
   F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1))))
   F(f(a, x0), h(a)) -> F(x0, h(h(a)))
   F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a)
   F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a)
   F(f(a, f(a, y_0)), a) -> F(f(a, y_0), h(a))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(17) TransformationProof (EQUIVALENT)
By forward instantiating [JAR06] the rule F(f(a, x0), h(h(z1))) -> F(x0, h(h(h(z1)))) we obtained the following new rules [LPAR04]:

   (F(f(a, f(a, y_0)), h(h(x1))) -> F(f(a, y_0), h(h(h(x1)))),F(f(a, f(a, y_0)), h(h(x1))) -> F(f(a, y_0), h(h(h(x1)))))


----------------------------------------

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)
   F(f(a, x0), h(a)) -> F(x0, h(h(a)))
   F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a)
   F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a)
   F(f(a, f(a, y_0)), a) -> F(f(a, y_0), h(a))
   F(f(a, f(a, y_0)), h(h(x1))) -> F(f(a, y_0), h(h(h(x1))))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(19) TransformationProof (EQUIVALENT)
By forward instantiating [JAR06] the rule F(f(a, x0), h(a)) -> F(x0, h(h(a))) we obtained the following new rules [LPAR04]:

   (F(f(a, f(a, y_0)), h(a)) -> F(f(a, y_0), h(h(a))),F(f(a, f(a, y_0)), h(a)) -> F(f(a, y_0), h(h(a))))
   (F(f(a, f(a, f(a, y_0))), h(a)) -> F(f(a, f(a, y_0)), h(h(a))),F(f(a, f(a, f(a, y_0))), h(a)) -> F(f(a, f(a, y_0)), h(h(a))))


----------------------------------------

(20)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(f(a, x0), a) -> F(f(x0, h(a)), a)
   F(f(a, x0), h(a)) -> F(f(x0, h(h(a))), a)
   F(f(a, x0), h(h(h(z1)))) -> F(f(x0, h(h(h(h(z1))))), a)
   F(f(a, x0), h(h(a))) -> F(f(x0, h(h(h(a)))), a)
   F(f(a, f(a, y_0)), a) -> F(f(a, y_0), h(a))
   F(f(a, f(a, y_0)), h(h(x1))) -> F(f(a, y_0), h(h(h(x1))))
   F(f(a, f(a, y_0)), h(a)) -> F(f(a, y_0), h(h(a)))
   F(f(a, f(a, f(a, y_0))), h(a)) -> F(f(a, f(a, y_0)), h(h(a)))

The TRS R consists of the following rules:

   f(f(a, x), y) -> f(a, f(f(x, h(y)), a))

The set Q consists of the following terms:

   f(f(a, x0), x1)

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

(21) SemLabProof (SOUND)
We found the following model for the rules of the TRSs R and P.
Interpretation over the domain with elements from 0 to 1.
a: 1
f: 0
h: 0
F: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

(22)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F.0-1(f.1-0(a., x0), a.) -> F.0-1(f.0-0(x0, h.1(a.)), a.)
   F.0-1(f.1-1(a., x0), a.) -> F.0-1(f.1-0(x0, h.1(a.)), a.)
   F.0-1(f.1-0(a., f.1-0(a., y_0)), a.) -> F.0-0(f.1-0(a., y_0), h.1(a.))
   F.0-1(f.1-0(a., f.1-1(a., y_0)), a.) -> F.0-0(f.1-1(a., y_0), h.1(a.))
   F.0-0(f.1-0(a., x0), h.1(a.)) -> F.0-1(f.0-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-1(a., x0), h.1(a.)) -> F.0-1(f.1-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-0(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-1(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-1(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., x0), h.0(h.1(a.))) -> F.0-1(f.0-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-1(a., x0), h.0(h.1(a.))) -> F.0-1(f.1-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.1(a.)) -> F.0-0(f.1-0(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.1(a.)) -> F.0-0(f.1-1(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-0(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-1(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.1(x1))))

The TRS R consists of the following rules:

   f.0-0(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.0(y)), a.))
   f.0-1(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.1(y)), a.))
   f.0-0(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.0(y)), a.))
   f.0-1(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.1(y)), a.))

The set Q consists of the following terms:

   f.0-0(f.1-0(a., x0), x1)
   f.0-1(f.1-0(a., x0), x1)
   f.0-0(f.1-1(a., x0), x1)
   f.0-1(f.1-1(a., x0), x1)

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

(23) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
----------------------------------------

(24)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F.0-1(f.1-0(a., x0), a.) -> F.0-1(f.0-0(x0, h.1(a.)), a.)
   F.0-1(f.1-0(a., f.1-0(a., y_0)), a.) -> F.0-0(f.1-0(a., y_0), h.1(a.))
   F.0-0(f.1-0(a., x0), h.1(a.)) -> F.0-1(f.0-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.1(a.)) -> F.0-0(f.1-0(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., x0), h.0(h.1(a.))) -> F.0-1(f.0-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-1(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-1(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.1(a.)) -> F.0-0(f.1-1(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-1(a., x0), h.0(h.1(a.))) -> F.0-1(f.1-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., f.1-0(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-1(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(a.)))

The TRS R consists of the following rules:

   f.0-0(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.0(y)), a.))
   f.0-1(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.1(y)), a.))
   f.0-0(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.0(y)), a.))
   f.0-1(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.1(y)), a.))

The set Q consists of the following terms:

   f.0-0(f.1-0(a., x0), x1)
   f.0-1(f.1-0(a., x0), x1)
   f.0-0(f.1-1(a., x0), x1)
   f.0-1(f.1-1(a., x0), x1)

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

(25) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.

Strictly oriented dependency pairs:

   F.0-0(f.1-1(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-1(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.1-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-1(a., x0), h.0(h.1(a.))) -> F.0-1(f.1-0(x0, h.0(h.0(h.1(a.)))), a.)

Strictly oriented rules of the TRS R:

   f.0-0(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.0(y)), a.))
   f.0-1(f.1-1(a., x), y) -> f.1-0(a., f.0-1(f.1-0(x, h.1(y)), a.))

Used ordering: Polynomial interpretation [POLO]:

   POL(F.0-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(F.0-1(x_1, x_2)) = 1 + x_1 + x_2
   POL(a.) = 0
   POL(f.0-0(x_1, x_2)) = x_1 + x_2
   POL(f.0-1(x_1, x_2)) = x_1 + x_2
   POL(f.1-0(x_1, x_2)) = x_1 + x_2
   POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2
   POL(h.0(x_1)) = x_1
   POL(h.1(x_1)) = x_1


----------------------------------------

(26)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F.0-1(f.1-0(a., x0), a.) -> F.0-1(f.0-0(x0, h.1(a.)), a.)
   F.0-1(f.1-0(a., f.1-0(a., y_0)), a.) -> F.0-0(f.1-0(a., y_0), h.1(a.))
   F.0-0(f.1-0(a., x0), h.1(a.)) -> F.0-1(f.0-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.1(a.)) -> F.0-0(f.1-0(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., x0), h.0(h.1(a.))) -> F.0-1(f.0-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-1(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., f.1-1(a., y_0)), h.1(a.)) -> F.0-0(f.1-1(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-0(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-1(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(a.)))

The TRS R consists of the following rules:

   f.0-0(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.0(y)), a.))
   f.0-1(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.1(y)), a.))

The set Q consists of the following terms:

   f.0-0(f.1-0(a., x0), x1)
   f.0-1(f.1-0(a., x0), x1)
   f.0-0(f.1-1(a., x0), x1)
   f.0-1(f.1-1(a., x0), x1)

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

(27) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
----------------------------------------

(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F.0-1(f.1-0(a., x0), a.) -> F.0-1(f.0-0(x0, h.1(a.)), a.)
   F.0-1(f.1-0(a., f.1-0(a., y_0)), a.) -> F.0-0(f.1-0(a., y_0), h.1(a.))
   F.0-0(f.1-0(a., x0), h.1(a.)) -> F.0-1(f.0-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.1(a.)) -> F.0-0(f.1-0(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., x0), h.0(h.1(a.))) -> F.0-1(f.0-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., f.1-0(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-1(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(a.)))

The TRS R consists of the following rules:

   f.0-0(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.0(y)), a.))
   f.0-1(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.1(y)), a.))

The set Q consists of the following terms:

   f.0-0(f.1-0(a., x0), x1)
   f.0-1(f.1-0(a., x0), x1)
   f.0-0(f.1-1(a., x0), x1)
   f.0-1(f.1-1(a., x0), x1)

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

(29) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.

Strictly oriented dependency pairs:

   F.0-1(f.1-0(a., x0), a.) -> F.0-1(f.0-0(x0, h.1(a.)), a.)
   F.0-1(f.1-0(a., f.1-0(a., y_0)), a.) -> F.0-0(f.1-0(a., y_0), h.1(a.))
   F.0-0(f.1-0(a., x0), h.1(a.)) -> F.0-1(f.0-0(x0, h.0(h.1(a.))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.1(a.)) -> F.0-0(f.1-0(a., y_0), h.0(h.1(a.)))
   F.0-0(f.1-0(a., x0), h.0(h.1(a.))) -> F.0-1(f.0-0(x0, h.0(h.0(h.1(a.)))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.1(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.1(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.1(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.0(x1))) -> F.0-0(f.1-0(a., y_0), h.0(h.0(h.0(x1))))
   F.0-0(f.1-0(a., x0), h.0(h.0(h.0(z1)))) -> F.0-1(f.0-0(x0, h.0(h.0(h.0(h.0(z1))))), a.)
   F.0-0(f.1-0(a., f.1-0(a., f.1-0(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-0(a., y_0)), h.0(h.1(a.)))
   F.0-0(f.1-0(a., f.1-0(a., f.1-1(a., y_0))), h.1(a.)) -> F.0-0(f.1-0(a., f.1-1(a., y_0)), h.0(h.1(a.)))


Used ordering: Polynomial interpretation [POLO]:

   POL(F.0-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(F.0-1(x_1, x_2)) = 1 + x_1 + x_2
   POL(a.) = 0
   POL(f.0-0(x_1, x_2)) = x_1 + x_2
   POL(f.0-1(x_1, x_2)) = x_1 + x_2
   POL(f.1-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(f.1-1(x_1, x_2)) = x_1 + x_2
   POL(h.0(x_1)) = x_1
   POL(h.1(x_1)) = x_1


----------------------------------------

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

   f.0-0(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.0(y)), a.))
   f.0-1(f.1-0(a., x), y) -> f.1-0(a., f.0-1(f.0-0(x, h.1(y)), a.))

The set Q consists of the following terms:

   f.0-0(f.1-0(a., x0), x1)
   f.0-1(f.1-0(a., x0), x1)
   f.0-0(f.1-1(a., x0), x1)
   f.0-1(f.1-1(a., x0), x1)

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

(31) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------

(32)
YES