/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, 89 ms]
(4) QTRS
(5) AAECC Innermost [EQUIVALENT, 23 ms]
(6) QTRS
(7) DependencyPairsProof [EQUIVALENT, 0 ms]
(8) QDP
(9) DependencyGraphProof [EQUIVALENT, 0 ms]
(10) AND
    (11) QDP
        (12) UsableRulesProof [EQUIVALENT, 0 ms]
        (13) QDP
        (14) QReductionProof [EQUIVALENT, 0 ms]
        (15) QDP
        (16) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (17) YES
    (18) QDP
        (19) UsableRulesProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) QReductionProof [EQUIVALENT, 0 ms]
        (22) QDP
        (23) TransformationProof [EQUIVALENT, 0 ms]
        (24) QDP
        (25) DependencyGraphProof [EQUIVALENT, 0 ms]
        (26) QDP
        (27) UsableRulesProof [EQUIVALENT, 0 ms]
        (28) QDP
        (29) TransformationProof [EQUIVALENT, 0 ms]
        (30) QDP
        (31) TransformationProof [EQUIVALENT, 0 ms]
        (32) QDP
        (33) DependencyGraphProof [EQUIVALENT, 0 ms]
        (34) QDP
        (35) TransformationProof [EQUIVALENT, 0 ms]
        (36) QDP
        (37) DependencyGraphProof [EQUIVALENT, 0 ms]
        (38) QDP
        (39) TransformationProof [EQUIVALENT, 0 ms]
        (40) QDP
        (41) TransformationProof [EQUIVALENT, 0 ms]
        (42) QDP
        (43) DependencyGraphProof [EQUIVALENT, 0 ms]
        (44) QDP
        (45) TransformationProof [EQUIVALENT, 0 ms]
        (46) QDP
        (47) DependencyGraphProof [EQUIVALENT, 0 ms]
        (48) QDP
        (49) QDPOrderProof [EQUIVALENT, 1469 ms]
        (50) QDP
        (51) SplitQDPProof [EQUIVALENT, 0 ms]
        (52) AND
            (53) QDP
                (54) SemLabProof [SOUND, 0 ms]
                (55) QDP
                (56) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                (57) QDP
                (58) MRRProof [EQUIVALENT, 0 ms]
                (59) QDP
                (60) DependencyGraphProof [EQUIVALENT, 0 ms]
                (61) QDP
                (62) MRRProof [EQUIVALENT, 11 ms]
                (63) QDP
                (64) QDPOrderProof [EQUIVALENT, 0 ms]
                (65) QDP
                (66) QDPOrderProof [EQUIVALENT, 9 ms]
                (67) QDP
                (68) PisEmptyProof [SOUND, 0 ms]
                (69) TRUE
            (70) QDP
                (71) SplitQDPProof [EQUIVALENT, 0 ms]
                (72) AND
                    (73) QDP
                        (74) SemLabProof [SOUND, 0 ms]
                        (75) QDP
                        (76) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                        (77) QDP
                        (78) MRRProof [EQUIVALENT, 0 ms]
                        (79) QDP
                        (80) DependencyGraphProof [EQUIVALENT, 0 ms]
                        (81) QDP
                        (82) QDPOrderProof [EQUIVALENT, 10 ms]
                        (83) QDP
                        (84) QDPOrderProof [EQUIVALENT, 0 ms]
                        (85) QDP
                        (86) PisEmptyProof [SOUND, 0 ms]
                        (87) TRUE
                    (88) QDP
                        (89) SplitQDPProof [EQUIVALENT, 0 ms]
                        (90) AND
                            (91) QDP
                                (92) SemLabProof [SOUND, 0 ms]
                                (93) QDP
                                (94) MRRProof [EQUIVALENT, 0 ms]
                                (95) QDP
                                (96) DependencyGraphProof [EQUIVALENT, 0 ms]
                                (97) QDP
                                (98) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                                (99) QDP
                                (100) MRRProof [EQUIVALENT, 4 ms]
                                (101) QDP
                                (102) PisEmptyProof [SOUND, 0 ms]
                                (103) TRUE
                            (104) QDP
                                (105) SplitQDPProof [EQUIVALENT, 0 ms]
                                (106) AND
                                    (107) QDP
                                        (108) SemLabProof [SOUND, 0 ms]
                                        (109) QDP
                                        (110) MRRProof [EQUIVALENT, 6 ms]
                                        (111) QDP
                                        (112) DependencyGraphProof [EQUIVALENT, 0 ms]
                                        (113) QDP
                                        (114) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                                        (115) QDP
                                        (116) MRRProof [EQUIVALENT, 0 ms]
                                        (117) QDP
                                        (118) PisEmptyProof [SOUND, 0 ms]
                                        (119) TRUE
                                    (120) QDP
                                        (121) SemLabProof [SOUND, 4942 ms]
                                        (122) QDP
                                        (123) DependencyGraphProof [EQUIVALENT, 0 ms]
                                        (124) AND
                                            (125) QDP
                                                (126) MRRProof [EQUIVALENT, 5 ms]
                                                (127) QDP
                                                (128) MRRProof [EQUIVALENT, 0 ms]
                                                (129) QDP
                                                (130) MRRProof [EQUIVALENT, 0 ms]
                                                (131) QDP
                                                (132) PisEmptyProof [EQUIVALENT, 0 ms]
                                                (133) YES
                                            (134) QDP
                                                (135) MRRProof [EQUIVALENT, 0 ms]
                                                (136) QDP
                                                (137) MRRProof [EQUIVALENT, 0 ms]
                                                (138) QDP
                                                (139) MRRProof [EQUIVALENT, 0 ms]
                                                (140) QDP
                                                (141) PisEmptyProof [EQUIVALENT, 0 ms]
                                                (142) YES


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

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

   g(b) -> g(f(f(f(f(f(b))))))
   f(f(b)) -> b
   f(b) -> b
   g(f(b)) -> c



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(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   down(g(f(b))) -> up(c)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

Q is empty.

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

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

   POL(b) = 0
   POL(c) = 0
   POL(down(x_1)) = 2*x_1
   POL(f(x_1)) = x_1
   POL(f_flat(x_1)) = x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = 1 + x_1
   POL(g_flat(x_1)) = 2 + x_1
   POL(top(x_1)) = 2*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(g(f(b))) -> up(c)




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

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

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

Q is empty.

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

(5) AAECC Innermost (EQUIVALENT)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)

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

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

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

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))


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

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

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

   TOP(up(x)) -> TOP(down(x))
   TOP(up(x)) -> DOWN(x)
   DOWN(g(g(y3))) -> G_FLAT(down(g(y3)))
   DOWN(g(g(y3))) -> DOWN(g(y3))
   DOWN(g(c)) -> G_FLAT(down(c))
   DOWN(g(c)) -> DOWN(c)
   DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant))
   DOWN(g(fresh_constant)) -> DOWN(fresh_constant)
   DOWN(f(g(y6))) -> F_FLAT(down(g(y6)))
   DOWN(f(g(y6))) -> DOWN(g(y6))
   DOWN(f(c)) -> F_FLAT(down(c))
   DOWN(f(c)) -> DOWN(c)
   DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant))
   DOWN(f(fresh_constant)) -> DOWN(fresh_constant)
   DOWN(g(f(g(y9)))) -> G_FLAT(down(f(g(y9))))
   DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
   DOWN(g(f(f(y10)))) -> G_FLAT(down(f(f(y10))))
   DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
   DOWN(g(f(c))) -> G_FLAT(down(f(c)))
   DOWN(g(f(c))) -> DOWN(f(c))
   DOWN(g(f(fresh_constant))) -> G_FLAT(down(f(fresh_constant)))
   DOWN(g(f(fresh_constant))) -> DOWN(f(fresh_constant))
   DOWN(f(f(g(y12)))) -> F_FLAT(down(f(g(y12))))
   DOWN(f(f(g(y12)))) -> DOWN(f(g(y12)))
   DOWN(f(f(f(y13)))) -> F_FLAT(down(f(f(y13))))
   DOWN(f(f(f(y13)))) -> DOWN(f(f(y13)))
   DOWN(f(f(c))) -> F_FLAT(down(f(c)))
   DOWN(f(f(c))) -> DOWN(f(c))
   DOWN(f(f(fresh_constant))) -> F_FLAT(down(f(fresh_constant)))
   DOWN(f(f(fresh_constant))) -> DOWN(f(fresh_constant))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

(10)
Complex Obligation (AND)

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

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

   DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
   DOWN(f(g(y6))) -> DOWN(g(y6))
   DOWN(g(g(y3))) -> DOWN(g(y3))
   DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
   DOWN(f(f(g(y12)))) -> DOWN(f(g(y12)))
   DOWN(f(f(f(y13)))) -> DOWN(f(f(y13)))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(12) 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.
----------------------------------------

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

   DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
   DOWN(f(g(y6))) -> DOWN(g(y6))
   DOWN(g(g(y3))) -> DOWN(g(y3))
   DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
   DOWN(f(f(g(y12)))) -> DOWN(f(g(y12)))
   DOWN(f(f(f(y13)))) -> DOWN(f(f(y13)))

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

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(14) 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(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))


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

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

   DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
   DOWN(f(g(y6))) -> DOWN(g(y6))
   DOWN(g(g(y3))) -> DOWN(g(y3))
   DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
   DOWN(f(f(g(y12)))) -> DOWN(f(g(y12)))
   DOWN(f(f(f(y13)))) -> DOWN(f(f(y13)))

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

(16) 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(f(g(y6))) -> DOWN(g(y6))
The graph contains the following edges 1 > 1


*DOWN(g(g(y3))) -> DOWN(g(y3))
The graph contains the following edges 1 > 1


*DOWN(g(f(g(y9)))) -> DOWN(f(g(y9)))
The graph contains the following edges 1 > 1


*DOWN(g(f(f(y10)))) -> DOWN(f(f(y10)))
The graph contains the following edges 1 > 1


*DOWN(f(f(g(y12)))) -> DOWN(f(g(y12)))
The graph contains the following edges 1 > 1


*DOWN(f(f(f(y13)))) -> DOWN(f(f(y13)))
The graph contains the following edges 1 > 1


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

(17)
YES

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

(18)
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(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   top(up(x)) -> top(down(x))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(19) 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.
----------------------------------------

(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(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   f_flat(up(x_1)) -> up(f(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   top(up(x0))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(21) 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))


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

(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(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   f_flat(up(x_1)) -> up(f(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(23) 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(g(b))) -> TOP(up(g(f(f(f(f(f(b)))))))),TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b)))))))))
   (TOP(up(f(f(b)))) -> TOP(up(b)),TOP(up(f(f(b)))) -> TOP(up(b)))
   (TOP(up(f(b))) -> TOP(up(b)),TOP(up(f(b))) -> TOP(up(b)))
   (TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0)))),TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0)))))
   (TOP(up(g(c))) -> TOP(g_flat(down(c))),TOP(up(g(c))) -> TOP(g_flat(down(c))))
   (TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))),TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))))
   (TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))),TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))))
   (TOP(up(f(c))) -> TOP(f_flat(down(c))),TOP(up(f(c))) -> TOP(f_flat(down(c))))
   (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))))
   (TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))),TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))))
   (TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0))))),TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0))))))
   (TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))),TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))))
   (TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))),TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))))
   (TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))),TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))))
   (TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0))))),TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0))))))
   (TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))),TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))))
   (TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))),TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))))


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

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

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(f(f(b)))) -> TOP(up(b))
   TOP(up(f(b))) -> TOP(up(b))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(g(c))) -> TOP(g_flat(down(c)))
   TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant)))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(c))) -> TOP(f_flat(down(c)))
   TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   f_flat(up(x_1)) -> up(f(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
   TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(f(f(b))) -> up(b)
   down(f(b)) -> up(b)
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   f_flat(up(x_1)) -> up(f(x_1))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(27) 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.
----------------------------------------

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0)))))
   TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(29) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(g(x0))))) -> TOP(g_flat(down(f(g(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0))))),TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0))))))


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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(31) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(c)))) -> TOP(g_flat(down(f(c)))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c)))),TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c)))))


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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(g(f(c)))) -> TOP(g_flat(f_flat(down(c))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

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

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(35) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(down(f(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant)))),TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant)))))


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

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

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(fresh_constant)))) -> TOP(g_flat(f_flat(down(fresh_constant))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(39) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(f(f(g(x0))))) -> TOP(f_flat(down(f(g(x0))))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0))))),TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0))))))


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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(41) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(f(f(c)))) -> TOP(f_flat(down(f(c)))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c)))),TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c)))))


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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(c)))) -> TOP(f_flat(f_flat(down(c))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

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

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(45) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(down(f(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant)))),TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant)))))


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

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

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(fresh_constant)))) -> TOP(f_flat(f_flat(down(fresh_constant))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(49) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP(up(g(b))) -> TOP(up(g(f(f(f(f(f(b))))))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO]:

Non-tuple symbols: 
<<<
 M( b ) =  	[[1], [0]]
>>>

<<<
 M( c ) =  	[[0], [0]]
>>>

<<<
 M( down_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 0], [0, 1]] 	* 	x_1
>>>

<<<
 M( f_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 1], [1, 0]] 	* 	x_1
>>>

<<<
 M( fresh_constant ) =  	[[0], [0]]
>>>

<<<
 M( up_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 0], [0, 1]] 	* 	x_1
>>>

<<<
 M( f_flat_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 1], [1, 0]] 	* 	x_1
>>>

<<<
 M( g_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 0], [0, 0]] 	* 	x_1
>>>

<<<
 M( g_flat_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 0], [0, 0]] 	* 	x_1
>>>

Tuple symbols: 
<<<
 M( TOP_1(x_1) ) =  	[[0]] 	+ 	[[1, 0]] 	* 	x_1
>>>



Matrix type: 

We used a basic matrix type which is not further parametrizeable.





As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order.
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))


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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(51) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem

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

(52)
Complex Obligation (AND)

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

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

   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(54) 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.
b: 0
c: 1
down: 0
f: 0
fresh_constant: 0
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(c.)) -> f_flat.0(down.1(c.))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(c.)) -> g_flat.0(down.1(c.))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

   f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = 1 + x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.1(c.)) -> g_flat.0(down.1(c.))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.1(c.)) -> f_flat.0(down.1(c.))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(58) 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(g.1(c.)) -> g_flat.0(down.1(c.))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.1(c.)) -> f_flat.0(down.1(c.))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.1(c.)) -> f_flat.0(down.1(c.))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(62) 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.1(c.)) -> f_flat.0(down.1(c.))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(64) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 0
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = 0
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = 0
   POL(up.0(x_1)) = x_1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(66) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 0
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(fresh_constant.)) -> g_flat.0(down.0(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.1(c.))) -> g_flat.0(down.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.))) -> g_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(fresh_constant.)) -> f_flat.0(down.0(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(c.))) -> f_flat.0(down.0(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.0(fresh_constant.))) -> f_flat.0(down.0(f.0(fresh_constant.)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

(69)
TRUE

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   f_flat(up(x_1)) -> up(f(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(71) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem

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

(72)
Complex Obligation (AND)

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   f_flat(up(x_1)) -> up(f(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(74) 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.
b: 0
c: 0
down: 0
f: 0
fresh_constant: 1
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

   f_flat.0(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(78) 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(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(82) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP.0(up.0(f.0(f.0(f.1(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.1(x0)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 0
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = 0
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = 0
   POL(up.0(x_1)) = x_1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(84) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP.0(up.0(g.0(f.0(f.1(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.1(x0)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 0
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(f.1(y10)))) -> g_flat.0(down.0(f.0(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.))) -> g_flat.0(down.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(f.1(fresh_constant.))) -> f_flat.0(down.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.0(f.0(f.0(f.1(y13)))) -> f_flat.0(down.0(f.0(f.1(y13))))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.0(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.0(f.0(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.0(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.0(f.0(f.0(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.0(f.0(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

(87)
TRUE

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   f_flat(up(x_1)) -> up(f(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(89) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem

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

(90)
Complex Obligation (AND)

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   f_flat(up(x_1)) -> up(f(x_1))
   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   down(g(f(fresh_constant))) -> g_flat(down(f(fresh_constant)))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(f(fresh_constant))) -> f_flat(down(f(fresh_constant)))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(92) 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.
b: 0
c: 0
down: 0
f: x<sub>0</sub>
fresh_constant: 1
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.1(f.1(f.1(f.1(x0))))) -> TOP.0(f_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.))) -> g_flat.0(down.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.1(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.1(f.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(94) 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(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.1(f.1(f.1(f.1(x0))))) -> TOP.0(f_flat.0(down.1(f.1(f.1(x0)))))

Strictly oriented rules of the TRS R:

   down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
   down.0(g.1(f.1(fresh_constant.))) -> g_flat.0(down.1(f.1(fresh_constant.)))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(fresh_constant.) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.1(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.1(f.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.1(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.1(f.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(98) 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(f.1(f.1(fresh_constant.))) -> f_flat.0(down.1(f.1(fresh_constant.)))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.1(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.1(f.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.0(f.0(c.))) -> g_flat.0(down.0(f.0(c.)))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(f.0(f.0(c.))) -> f_flat.0(down.0(f.0(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.1(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(c.))
   down.1(f.1(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.0(f.0(c.)))
   down.0(g.1(f.1(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.0(f.0(f.0(c.)))
   down.1(f.1(f.1(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

(103)
TRUE

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(105) SplitQDPProof (EQUIVALENT)
We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem

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

(106)
Complex Obligation (AND)

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   down(g(f(c))) -> g_flat(down(f(c)))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(f(c))) -> f_flat(down(f(c)))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(108) 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.
b: 0
c: 1
down: 0
f: x<sub>0</sub>
fresh_constant: 0
up: 0
f_flat: 0
TOP: 0
g_flat: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.1(f.1(f.1(f.1(x0))))) -> TOP.0(f_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
   down.0(g.1(f.1(c.))) -> g_flat.0(down.1(f.1(c.)))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.1(f.1(f.1(c.))) -> f_flat.0(down.1(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.1(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.1(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.1(f.1(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(110) 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(g.1(f.1(f.1(x0))))) -> TOP.0(g_flat.0(down.1(f.1(f.1(x0)))))
   TOP.0(up.1(f.1(f.1(f.1(x0))))) -> TOP.0(f_flat.0(down.1(f.1(f.1(x0)))))

Strictly oriented rules of the TRS R:

   down.0(g.1(f.1(f.1(y10)))) -> g_flat.0(down.1(f.1(f.1(y10))))
   down.0(g.1(f.1(c.))) -> g_flat.0(down.1(f.1(c.)))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(c.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.1(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.1(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.1(f.1(f.1(c.))) -> f_flat.0(down.1(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.1(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.1(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.1(f.1(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.1(f.1(f.1(c.))) -> f_flat.0(down.1(f.1(c.)))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.1(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.1(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.1(f.1(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

(114) 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(f.1(f.1(c.))) -> f_flat.0(down.1(f.1(c.)))
   down.1(f.1(f.1(f.1(y13)))) -> f_flat.0(down.1(f.1(f.1(y13))))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = 1 + x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.1(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.1(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.1(f.1(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

   g_flat.0(up.1(x_1)) -> up.0(g.1(x_1))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = 1 + x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(f.0(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(f.0(f.0(f.0(x0))))) -> TOP.0(f_flat.0(down.0(f.0(f.0(x0)))))
   TOP.0(up.0(g.0(f.0(g.0(x0))))) -> TOP.0(g_flat.0(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.0(f.0(g.0(x0))))) -> TOP.0(f_flat.0(f_flat.0(down.0(g.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.0(f.0(f.0(f.0(f.0(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.0(f.0(g.0(y9)))) -> g_flat.0(down.0(f.0(g.0(y9))))
   down.0(g.0(f.0(g.1(y9)))) -> g_flat.0(down.0(f.0(g.1(y9))))
   down.0(g.0(f.0(f.0(y10)))) -> g_flat.0(down.0(f.0(f.0(y10))))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(f.0(f.0(b.))) -> up.0(b.)
   down.0(f.0(f.0(g.0(y12)))) -> f_flat.0(down.0(f.0(g.0(y12))))
   down.0(f.0(f.0(g.1(y12)))) -> f_flat.0(down.0(f.0(g.1(y12))))
   down.0(f.0(f.0(f.0(y13)))) -> f_flat.0(down.0(f.0(f.0(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))
   down.0(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.0(f.0(b.)))
   down.0(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.1(c.))
   down.0(g.0(fresh_constant.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.1(f.1(c.))
   down.0(f.0(fresh_constant.))
   down.0(g.0(f.0(g.0(x0))))
   down.0(g.0(f.0(g.1(x0))))
   down.0(g.0(f.0(f.0(x0))))
   down.0(g.1(f.1(f.1(x0))))
   down.0(g.1(f.1(c.)))
   down.0(g.0(f.0(fresh_constant.)))
   down.0(f.0(f.0(g.0(x0))))
   down.0(f.0(f.0(g.1(x0))))
   down.0(f.0(f.0(f.0(x0))))
   down.1(f.1(f.1(f.1(x0))))
   down.1(f.1(f.1(c.)))
   down.0(f.0(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.0(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))

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

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

(119)
TRUE

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

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

   TOP(up(g(g(x0)))) -> TOP(g_flat(down(g(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(g(f(f(x0))))) -> TOP(g_flat(down(f(f(x0)))))
   TOP(up(f(f(f(x0))))) -> TOP(f_flat(down(f(f(x0)))))
   TOP(up(g(f(g(x0))))) -> TOP(g_flat(f_flat(down(g(x0)))))
   TOP(up(f(f(g(x0))))) -> TOP(f_flat(f_flat(down(g(x0)))))

The TRS R consists of the following rules:

   down(g(b)) -> up(g(f(f(f(f(f(b)))))))
   down(g(g(y3))) -> g_flat(down(g(y3)))
   down(g(f(g(y9)))) -> g_flat(down(f(g(y9))))
   down(g(f(f(y10)))) -> g_flat(down(f(f(y10))))
   f_flat(up(x_1)) -> up(f(x_1))
   down(f(f(b))) -> up(b)
   down(f(f(g(y12)))) -> f_flat(down(f(g(y12))))
   down(f(f(f(y13)))) -> f_flat(down(f(f(y13))))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(y6))) -> f_flat(down(g(y6)))

The set Q consists of the following terms:

   down(g(b))
   down(f(f(b)))
   down(f(b))
   down(g(g(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(f(g(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(g(x0))))
   down(g(f(f(x0))))
   down(g(f(c)))
   down(g(f(fresh_constant)))
   down(f(f(g(x0))))
   down(f(f(f(x0))))
   down(f(f(c)))
   down(f(f(fresh_constant)))
   g_flat(up(x0))
   f_flat(up(x0))

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

(121) 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.
b: 0
c: 0
down: x<sub>0</sub>
f: 1 + x<sub>0</sub>
fresh_constant: 0
up: x<sub>0</sub>
f_flat: 1 + x<sub>0</sub>
TOP: 0
g: 0
g_flat: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.1(up.1(f.0(g.0(x0)))) -> TOP.1(f_flat.0(down.0(g.0(x0))))
   TOP.1(up.1(f.0(g.1(x0)))) -> TOP.1(f_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.1(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(g.1(f.0(f.1(x0))))) -> TOP.0(g_flat.1(down.1(f.0(f.1(x0)))))
   TOP.1(up.1(f.0(f.1(f.0(x0))))) -> TOP.1(f_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(f.1(f.0(f.1(x0))))) -> TOP.0(f_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(g.1(f.0(g.0(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.1(f.0(g.1(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.1(f.0(g.0(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.1(f.0(g.1(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.1(f.0(f.1(f.0(f.1(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(b.))) -> up.0(b.)
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

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

(124)
Complex Obligation (AND)

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

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

   TOP.1(up.1(f.0(g.0(x0)))) -> TOP.1(f_flat.0(down.0(g.0(x0))))
   TOP.1(up.1(f.0(g.1(x0)))) -> TOP.1(f_flat.0(down.0(g.1(x0))))
   TOP.1(up.1(f.0(f.1(f.0(x0))))) -> TOP.1(f_flat.0(down.0(f.1(f.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.1(f.0(f.1(f.0(f.1(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(b.))) -> up.0(b.)
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(126) 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(g.0(b.)) -> up.0(g.1(f.0(f.1(f.0(f.1(f.0(b.)))))))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.1(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.1(up.1(f.0(g.0(x0)))) -> TOP.1(f_flat.0(down.0(g.0(x0))))
   TOP.1(up.1(f.0(g.1(x0)))) -> TOP.1(f_flat.0(down.0(g.1(x0))))
   TOP.1(up.1(f.0(f.1(f.0(x0))))) -> TOP.1(f_flat.0(down.0(f.1(f.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(b.))) -> up.0(b.)
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(128) 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.1(f.0(b.))) -> up.0(b.)

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.1(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.1(up.1(f.0(g.0(x0)))) -> TOP.1(f_flat.0(down.0(g.0(x0))))
   TOP.1(up.1(f.0(g.1(x0)))) -> TOP.1(f_flat.0(down.0(g.1(x0))))
   TOP.1(up.1(f.0(f.1(f.0(x0))))) -> TOP.1(f_flat.0(down.0(f.1(f.0(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(130) 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.1(up.1(f.0(g.0(x0)))) -> TOP.1(f_flat.0(down.0(g.0(x0))))
   TOP.1(up.1(f.0(g.1(x0)))) -> TOP.1(f_flat.0(down.0(g.1(x0))))
   TOP.1(up.1(f.0(f.1(f.0(x0))))) -> TOP.1(f_flat.0(down.0(f.1(f.0(x0)))))


Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.1(x_1)) = x_1
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

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

(133)
YES

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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.1(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(g.1(f.0(f.1(x0))))) -> TOP.0(g_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(f.1(f.0(f.1(x0))))) -> TOP.0(f_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(g.1(f.0(g.0(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.1(f.0(g.1(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.1(f.0(g.0(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.1(f.0(g.1(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(b.)) -> up.0(g.1(f.0(f.1(f.0(f.1(f.0(b.)))))))
   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(b.))) -> up.0(b.)
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(135) 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(g.0(b.)) -> up.0(g.1(f.0(f.1(f.0(f.1(f.0(b.)))))))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = x_1
   POL(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = 1 + x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.1(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(g.1(f.0(f.1(x0))))) -> TOP.0(g_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(f.1(f.0(f.1(x0))))) -> TOP.0(f_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(g.1(f.0(g.0(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.1(f.0(g.1(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.1(f.0(g.0(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.1(f.0(g.1(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(b.))) -> up.0(b.)
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(137) 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.1(f.0(b.))) -> up.0(b.)

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(b.) = 0
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.0(up.0(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.1(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(g.1(f.0(f.1(x0))))) -> TOP.0(g_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(f.1(f.0(f.1(x0))))) -> TOP.0(f_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(g.1(f.0(g.0(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.1(f.0(g.1(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.1(f.0(g.0(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.1(f.0(g.1(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.1(x0)))))

The TRS R consists of the following rules:

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

(139) 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(g.0(g.0(x0)))) -> TOP.0(g_flat.0(down.0(g.0(x0))))
   TOP.0(up.0(g.0(g.1(x0)))) -> TOP.0(g_flat.0(down.0(g.1(x0))))
   TOP.0(up.0(g.0(f.1(f.0(x0))))) -> TOP.0(g_flat.0(down.0(f.1(f.0(x0)))))
   TOP.0(up.0(g.1(f.0(f.1(x0))))) -> TOP.0(g_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(f.1(f.0(f.1(x0))))) -> TOP.0(f_flat.1(down.1(f.0(f.1(x0)))))
   TOP.0(up.0(g.1(f.0(g.0(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(g.1(f.0(g.1(x0))))) -> TOP.0(g_flat.1(f_flat.0(down.0(g.1(x0)))))
   TOP.0(up.0(f.1(f.0(g.0(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.0(x0)))))
   TOP.0(up.0(f.1(f.0(g.1(x0))))) -> TOP.0(f_flat.1(f_flat.0(down.0(g.1(x0)))))


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(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = x_1
   POL(f_flat.1(x_1)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(g_flat.0(x_1)) = x_1
   POL(g_flat.1(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   down.0(g.0(g.0(y3))) -> g_flat.0(down.0(g.0(y3)))
   down.0(g.0(g.1(y3))) -> g_flat.0(down.0(g.1(y3)))
   down.0(g.1(f.0(g.0(y9)))) -> g_flat.1(down.1(f.0(g.0(y9))))
   down.0(g.1(f.0(g.1(y9)))) -> g_flat.1(down.1(f.0(g.1(y9))))
   down.0(g.0(f.1(f.0(y10)))) -> g_flat.0(down.0(f.1(f.0(y10))))
   down.0(g.1(f.0(f.1(y10)))) -> g_flat.1(down.1(f.0(f.1(y10))))
   f_flat.0(up.0(x_1)) -> up.1(f.0(x_1))
   f_flat.1(up.1(x_1)) -> up.0(f.1(x_1))
   down.0(f.1(f.0(g.0(y12)))) -> f_flat.1(down.1(f.0(g.0(y12))))
   down.0(f.1(f.0(g.1(y12)))) -> f_flat.1(down.1(f.0(g.1(y12))))
   down.1(f.0(f.1(f.0(y13)))) -> f_flat.0(down.0(f.1(f.0(y13))))
   down.0(f.1(f.0(f.1(y13)))) -> f_flat.1(down.1(f.0(f.1(y13))))
   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   g_flat.1(up.1(x_1)) -> up.0(g.1(x_1))
   down.1(f.0(g.0(y6))) -> f_flat.0(down.0(g.0(y6)))
   down.1(f.0(g.1(y6))) -> f_flat.0(down.0(g.1(y6)))

The set Q consists of the following terms:

   down.0(g.0(b.))
   down.0(f.1(f.0(b.)))
   down.1(f.0(b.))
   down.0(g.0(g.0(x0)))
   down.0(g.0(g.1(x0)))
   down.0(g.0(c.))
   down.0(g.0(fresh_constant.))
   down.1(f.0(g.0(x0)))
   down.1(f.0(g.1(x0)))
   down.1(f.0(c.))
   down.1(f.0(fresh_constant.))
   down.0(g.1(f.0(g.0(x0))))
   down.0(g.1(f.0(g.1(x0))))
   down.0(g.0(f.1(f.0(x0))))
   down.0(g.1(f.0(f.1(x0))))
   down.0(g.1(f.0(c.)))
   down.0(g.1(f.0(fresh_constant.)))
   down.0(f.1(f.0(g.0(x0))))
   down.0(f.1(f.0(g.1(x0))))
   down.1(f.0(f.1(f.0(x0))))
   down.0(f.1(f.0(f.1(x0))))
   down.0(f.1(f.0(c.)))
   down.0(f.1(f.0(fresh_constant.)))
   g_flat.0(up.0(x0))
   g_flat.1(up.1(x0))
   f_flat.0(up.0(x0))
   f_flat.1(up.1(x0))

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

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

(142)
YES