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


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


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


Outermost Termination of the given OTRS could be proven:

(0) OTRS
(1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 55 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 19 ms]
(6) QTRS
(7) AAECC Innermost [EQUIVALENT, 0 ms]
(8) QTRS
(9) DependencyPairsProof [EQUIVALENT, 0 ms]
(10) QDP
(11) DependencyGraphProof [EQUIVALENT, 0 ms]
(12) AND
    (13) QDP
        (14) UsableRulesProof [EQUIVALENT, 0 ms]
        (15) QDP
        (16) QReductionProof [EQUIVALENT, 0 ms]
        (17) QDP
        (18) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (19) YES
    (20) QDP
        (21) UsableRulesProof [EQUIVALENT, 0 ms]
        (22) QDP
        (23) QReductionProof [EQUIVALENT, 0 ms]
        (24) QDP
        (25) TransformationProof [EQUIVALENT, 0 ms]
        (26) QDP
        (27) DependencyGraphProof [EQUIVALENT, 0 ms]
        (28) QDP
        (29) SemLabProof [SOUND, 76 ms]
        (30) QDP
        (31) UsableRulesReductionPairsProof [EQUIVALENT, 7 ms]
        (32) QDP
        (33) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (34) QDP
        (35) MRRProof [EQUIVALENT, 0 ms]
        (36) QDP
        (37) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (38) QDP
        (39) MRRProof [EQUIVALENT, 0 ms]
        (40) QDP
        (41) MRRProof [EQUIVALENT, 0 ms]
        (42) QDP
        (43) PisEmptyProof [EQUIVALENT, 0 ms]
        (44) YES


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

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

   f(x, x) -> f(i(x), g(g(x)))
   f(x, y) -> x
   g(x) -> i(x)
   f(x, i(x)) -> f(x, x)
   f(i(x), i(g(x))) -> a



Outermost Strategy.

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

(1) Raffelsieper-Zantema-Transformation (SOUND)
We applied the Raffelsieper-Zantema transformation  to transform the outermost TRS to a standard TRS.
----------------------------------------

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

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(f(x, y)) -> up(x)
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   down(f(i(x), i(g(x)))) -> up(a)
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2))
   f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2))
   i_flat(up(x_1)) -> up(i(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

Q is empty.

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

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(a) = 0
   POL(block(x_1)) = 2 + 2*x_1
   POL(down(x_1)) = 2*x_1
   POL(f(x_1, x_2)) = 1 + x_1 + x_2
   POL(f_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(g(x_1)) = x_1
   POL(g_flat(x_1)) = x_1
   POL(i(x_1)) = x_1
   POL(i_flat(x_1)) = x_1
   POL(top(x_1)) = x_1
   POL(up(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(f(x, y)) -> up(x)
   down(f(i(x), i(g(x)))) -> up(a)
   f_flat(up(x_1), block(x_2)) -> up(f(x_1, x_2))
   f_flat(block(x_1), up(x_2)) -> up(f(x_1, x_2))




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

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

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

Q is empty.

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

(5) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(down(x_1)) = 2 + 2*x_1
   POL(f(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(g(x_1)) = x_1
   POL(g_flat(x_1)) = 1 + 2*x_1
   POL(i(x_1)) = x_1
   POL(i_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2 + 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   g_flat(up(x_1)) -> up(g(x_1))




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

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

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

Q is empty.

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

(7) AAECC Innermost (EQUIVALENT)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))
   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))

The TRS R 2 is 
   top(up(x)) -> top(down(x))

The signature Sigma is {top_1}
----------------------------------------

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

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))


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

(9) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

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

   TOP(up(x)) -> TOP(down(x))
   TOP(up(x)) -> DOWN(x)
   DOWN(i(y2)) -> I_FLAT(down(y2))
   DOWN(i(y2)) -> DOWN(y2)

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))

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

(11) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes.
----------------------------------------

(12)
Complex Obligation (AND)

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

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

   DOWN(i(y2)) -> DOWN(y2)

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))

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

(14) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   DOWN(i(y2)) -> DOWN(y2)

R is empty.
The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))

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

(16) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))


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

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

   DOWN(i(y2)) -> DOWN(y2)

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

(18) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*DOWN(i(y2)) -> DOWN(y2)
The graph contains the following edges 1 > 1


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

(19)
YES

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

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

   TOP(up(x)) -> TOP(down(x))

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   top(up(x)) -> top(down(x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))

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

(21) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

   TOP(up(x)) -> TOP(down(x))

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   top(up(x0))
   down(i(x0))
   i_flat(up(x0))

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

(23) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   top(up(x0))


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

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

   TOP(up(x)) -> TOP(down(x))

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   down(i(x0))
   i_flat(up(x0))

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

(25) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]:

   (TOP(up(f(x0, x0))) -> TOP(up(f(i(x0), g(g(x0))))),TOP(up(f(x0, x0))) -> TOP(up(f(i(x0), g(g(x0))))))
   (TOP(up(g(x0))) -> TOP(up(i(x0))),TOP(up(g(x0))) -> TOP(up(i(x0))))
   (TOP(up(f(x0, i(x0)))) -> TOP(up(f(x0, x0))),TOP(up(f(x0, i(x0)))) -> TOP(up(f(x0, x0))))
   (TOP(up(i(x0))) -> TOP(i_flat(down(x0))),TOP(up(i(x0))) -> TOP(i_flat(down(x0))))


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

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

   TOP(up(f(x0, x0))) -> TOP(up(f(i(x0), g(g(x0)))))
   TOP(up(g(x0))) -> TOP(up(i(x0)))
   TOP(up(f(x0, i(x0)))) -> TOP(up(f(x0, x0)))
   TOP(up(i(x0))) -> TOP(i_flat(down(x0)))

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   down(i(x0))
   i_flat(up(x0))

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:

   TOP(up(i(x0))) -> TOP(i_flat(down(x0)))

The TRS R consists of the following rules:

   down(f(x, x)) -> up(f(i(x), g(g(x))))
   down(g(x)) -> up(i(x))
   down(f(x, i(x))) -> up(f(x, x))
   down(i(y2)) -> i_flat(down(y2))
   i_flat(up(x_1)) -> up(i(x_1))

The set Q consists of the following terms:

   down(f(x0, x0))
   down(g(x0))
   down(f(x0, i(x0)))
   down(i(x0))
   i_flat(up(x0))

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

(29) 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.
down: 0
f: 0
i: 0
up: 0
i_flat: 0
TOP: 0
g: 1
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))
   TOP.0(up.0(i.1(x0))) -> TOP.0(i_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))
   down.0(f.1-1(x, x)) -> up.0(f.0-1(i.1(x), g.1(g.1(x))))
   down.1(g.0(x)) -> up.0(i.0(x))
   down.1(g.1(x)) -> up.0(i.1(x))
   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(f.1-0(x, i.1(x))) -> up.0(f.1-1(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   down.0(i.1(y2)) -> i_flat.0(down.1(y2))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))
   i_flat.0(up.1(x_1)) -> up.0(i.1(x_1))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(31) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

No dependency pairs are removed.

The following rules are removed from R:

   down.0(f.1-0(x, i.1(x))) -> up.0(f.1-1(x, x))
   i_flat.0(up.1(x_1)) -> up.0(i.1(x_1))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = 1 + x_1
   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(f.1-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(i.0(x_1)) = x_1
   POL(i.1(x_1)) = x_1
   POL(i_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))
   TOP.0(up.0(i.1(x0))) -> TOP.0(i_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(g.0(x)) -> up.0(i.0(x))
   down.1(g.1(x)) -> up.0(i.1(x))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))
   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))
   down.0(f.1-1(x, x)) -> up.0(f.0-1(i.1(x), g.1(g.1(x))))
   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   down.0(i.1(y2)) -> i_flat.0(down.1(y2))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(33) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

No dependency pairs are removed.

The following rules are removed from R:

   down.1(g.0(x)) -> up.0(i.0(x))
   down.0(f.1-1(x, x)) -> up.0(f.0-1(i.1(x), g.1(g.1(x))))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = 1 + x_1
   POL(f.0-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(f.0-1(x_1, x_2)) = x_1 + x_2
   POL(f.1-1(x_1, x_2)) = 1 + x_1 + x_2
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = x_1
   POL(i.0(x_1)) = x_1
   POL(i.1(x_1)) = 1 + x_1
   POL(i_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))
   TOP.0(up.0(i.1(x0))) -> TOP.0(i_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(g.1(x)) -> up.0(i.1(x))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))
   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))
   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   down.0(i.1(y2)) -> i_flat.0(down.1(y2))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(35) 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:

   TOP.0(up.0(i.1(x0))) -> TOP.0(i_flat.0(down.1(x0)))

Strictly oriented rules of the TRS R:

   down.0(i.1(y2)) -> i_flat.0(down.1(y2))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(f.0-1(x_1, x_2)) = x_1 + x_2
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(i.0(x_1)) = x_1
   POL(i.1(x_1)) = 1 + x_1
   POL(i_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.1(g.1(x)) -> up.0(i.1(x))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))
   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))
   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(37) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

No dependency pairs are removed.

The following rules are removed from R:

   down.1(g.1(x)) -> up.0(i.1(x))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = 1 + x_1
   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(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(i.0(x_1)) = x_1
   POL(i_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))
   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(39) 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 rules of the TRS R:

   down.0(f.0-0(x, x)) -> up.0(f.0-1(i.0(x), g.1(g.0(x))))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = x_1
   POL(f.0-0(x_1, x_2)) = 1 + x_1 + x_2
   POL(f.0-1(x_1, x_2)) = x_1 + x_2
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(i.0(x_1)) = x_1
   POL(i_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

(41) 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:

   TOP.0(up.0(i.0(x0))) -> TOP.0(i_flat.0(down.0(x0)))


Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = x_1
   POL(f.0-0(x_1, x_2)) = x_1 + x_2
   POL(i.0(x_1)) = 1 + x_1
   POL(i_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = 1 + x_1


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

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

   down.0(f.0-0(x, i.0(x))) -> up.0(f.0-0(x, x))
   down.0(i.0(y2)) -> i_flat.0(down.0(y2))
   i_flat.0(up.0(x_1)) -> up.0(i.0(x_1))

The set Q consists of the following terms:

   down.0(f.0-0(x0, x0))
   down.0(f.1-1(x0, x0))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(f.0-0(x0, i.0(x0)))
   down.0(f.1-0(x0, i.1(x0)))
   down.0(i.0(x0))
   down.0(i.1(x0))
   i_flat.0(up.0(x0))
   i_flat.0(up.1(x0))

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

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

(44)
YES