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


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


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


Outermost Termination of the given OTRS could not be shown:

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


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

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

   f(g(x)) -> g(g(f(f(x))))
   g(g(g(x))) -> c



Outermost Strategy.

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

(1) Thiemann-SpecialC-Transformation (EQUIVALENT)
We applied the Thiemann-SpecialC transformation  to transform the outermost TRS to an innermost TRS.
----------------------------------------

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

   top(go_up(x)) -> top(reduce(x))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   redex_g(g(g(x))) -> result_g(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

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

   TOP(go_up(x)) -> TOP(reduce(x))
   TOP(go_up(x)) -> REDUCE(x)
   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
   REDUCE(f(x_1)) -> REDEX_F(x_1)
   REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
   REDUCE(g(x_1)) -> REDEX_G(x_1)
   CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1))
   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1))
   CHECK_G(redex_g(x_1)) -> REDUCE(x_1)

The TRS R consists of the following rules:

   top(go_up(x)) -> top(reduce(x))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   redex_g(g(g(x))) -> result_g(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

(6)
Complex Obligation (AND)

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

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

   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))

The TRS R consists of the following rules:

   top(go_up(x)) -> top(reduce(x))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   redex_g(g(g(x))) -> result_g(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

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

   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))

The TRS R consists of the following rules:

   redex_f(g(x)) -> result_f(g(g(f(f(x)))))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(10) 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(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))

The TRS R consists of the following rules:

   redex_f(g(x)) -> result_f(g(g(f(f(x)))))

The set Q consists of the following terms:

   redex_f(g(x0))

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

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

   redex_f(g(x)) -> result_f(g(g(f(f(x)))))

Used ordering: Polynomial interpretation [POLO]:

   POL(CHECK_F(x_1)) = x_1
   POL(REDUCE(x_1)) = 1 + 2*x_1
   POL(f(x_1)) = x_1
   POL(g(x_1)) = 2*x_1
   POL(redex_f(x_1)) = 1 + 2*x_1
   POL(result_f(x_1)) = x_1


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

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

   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))

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

   redex_f(g(x0))

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

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

The following dependency pairs can be deleted:

   REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1))
No rules are removed from R.

Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(CHECK_F(x_1)) = 2*x_1
   POL(REDUCE(x_1)) = 2*x_1
   POL(f(x_1)) = 2*x_1
   POL(redex_f(x_1)) = x_1


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

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

   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)

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

   redex_f(g(x0))

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

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

(17)
TRUE

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

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

   REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
   CHECK_G(redex_g(x_1)) -> REDUCE(x_1)

The TRS R consists of the following rules:

   top(go_up(x)) -> top(reduce(x))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   redex_g(g(g(x))) -> result_g(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_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:

   REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
   CHECK_G(redex_g(x_1)) -> REDUCE(x_1)

The TRS R consists of the following rules:

   redex_g(g(g(x))) -> result_g(c)

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_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(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

   REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
   CHECK_G(redex_g(x_1)) -> REDUCE(x_1)

The TRS R consists of the following rules:

   redex_g(g(g(x))) -> result_g(c)

The set Q consists of the following terms:

   redex_g(g(g(x0)))

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

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

The following dependency pairs can be deleted:

   REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1))
The following rules are removed from R:

   redex_g(g(g(x))) -> result_g(c)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(CHECK_G(x_1)) = x_1
   POL(REDUCE(x_1)) = 2*x_1
   POL(c) = 0
   POL(g(x_1)) = 2 + 2*x_1
   POL(redex_g(x_1)) = 2*x_1
   POL(result_g(x_1)) = 2 + x_1


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

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

   CHECK_G(redex_g(x_1)) -> REDUCE(x_1)

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

   redex_g(g(g(x0)))

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

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

(26)
TRUE

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

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

   TOP(go_up(x)) -> TOP(reduce(x))

The TRS R consists of the following rules:

   top(go_up(x)) -> top(reduce(x))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   redex_g(g(g(x))) -> result_g(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

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

   TOP(go_up(x)) -> TOP(reduce(x))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_g(g(g(x))) -> result_g(c)
   check_g(result_g(x)) -> go_up(x)
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(30) 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(go_up(x0))


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

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

   TOP(go_up(x)) -> TOP(reduce(x))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_g(g(g(x))) -> result_g(c)
   check_g(result_g(x)) -> go_up(x)
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))

The set Q consists of the following terms:

   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

   (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))))
   (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))))


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

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

   TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))
   TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_g(g(g(x))) -> result_g(c)
   check_g(result_g(x)) -> go_up(x)
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))

The set Q consists of the following terms:

   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

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

   TOP(go_up(x)) -> TOP(reduce(x))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_g(g(g(x))) -> result_g(c)
   check_g(result_g(x)) -> go_up(x)
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(36) 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(go_up(x0))


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

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

   TOP(go_up(x)) -> TOP(reduce(x))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   redex_g(g(g(x))) -> result_g(c)
   check_g(result_g(x)) -> go_up(x)
   check_g(redex_g(x_1)) -> in_g_1(reduce(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   redex_f(g(x)) -> result_f(g(g(f(f(x)))))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))

The set Q consists of the following terms:

   reduce(f(x0))
   reduce(g(x0))
   redex_f(g(x0))
   redex_g(g(g(x0)))
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_f(redex_f(x0))
   check_g(redex_g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(38) Trivial-Transformation (SOUND)
We applied the Trivial transformation  to transform the outermost TRS to a standard TRS.
----------------------------------------

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

   f(g(x)) -> g(g(f(f(x))))
   g(g(g(x))) -> c

Q is empty.

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

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

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

   F(g(x)) -> G(g(f(f(x))))
   F(g(x)) -> G(f(f(x)))
   F(g(x)) -> F(f(x))
   F(g(x)) -> F(x)

The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(f(x))))
   g(g(g(x))) -> c

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

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

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

   F(g(x)) -> F(x)
   F(g(x)) -> F(f(x))

The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(f(x))))
   g(g(g(x))) -> c

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

(44) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule F(g(x)) -> F(f(x)) at position [0] we obtained the following new rules [LPAR04]:

   (F(g(g(x0))) -> F(g(g(f(f(x0))))),F(g(g(x0))) -> F(g(g(f(f(x0))))))


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

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

   F(g(x)) -> F(x)
   F(g(g(x0))) -> F(g(g(f(f(x0)))))

The TRS R consists of the following rules:

   f(g(x)) -> g(g(f(f(x))))
   g(g(g(x))) -> c

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

(46) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = F(g(g(x0))) evaluates to  t =F(g(g(f(f(x0)))))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [x0 / f(f(x0))]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from F(g(g(x0))) to F(g(g(f(f(x0))))).




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

(47)
NO

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

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

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

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

Q is empty.

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

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

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

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

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

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   top(up(x)) -> top(down(x))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   top(up(x0))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))


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

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

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

   TOP(up(x)) -> TOP(down(x))
   TOP(up(x)) -> DOWN(x)
   DOWN(f(f(y3))) -> F_FLAT(down(f(y3)))
   DOWN(f(f(y3))) -> DOWN(f(y3))
   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(y6))) -> G_FLAT(down(f(y6)))
   DOWN(g(f(y6))) -> DOWN(f(y6))
   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(g(g(f(y9)))) -> G_FLAT(down(g(f(y9))))
   DOWN(g(g(f(y9)))) -> DOWN(g(f(y9)))
   DOWN(g(g(c))) -> G_FLAT(down(g(c)))
   DOWN(g(g(c))) -> DOWN(g(c))
   DOWN(g(g(fresh_constant))) -> G_FLAT(down(g(fresh_constant)))
   DOWN(g(g(fresh_constant))) -> DOWN(g(fresh_constant))

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   top(up(x)) -> top(down(x))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   top(up(x0))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

(55)
Complex Obligation (AND)

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

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

   DOWN(f(f(y3))) -> DOWN(f(y3))

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   top(up(x)) -> top(down(x))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   top(up(x0))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

   DOWN(f(f(y3))) -> DOWN(f(y3))

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

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

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

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

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


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

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

   DOWN(f(f(y3))) -> DOWN(f(y3))

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

(61) 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(f(y3))) -> DOWN(f(y3))
The graph contains the following edges 1 > 1


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

(62)
YES

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   top(up(x)) -> top(down(x))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   top(up(x0))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   top(up(x0))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(g(g(g(x)))) -> up(c)
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   down(g(f(y6))) -> g_flat(down(f(y6)))
   down(g(c)) -> g_flat(down(c))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(g(f(y9)))) -> g_flat(down(g(f(y9))))
   down(g(g(c))) -> g_flat(down(g(c)))
   down(g(g(fresh_constant))) -> g_flat(down(g(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

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

The TRS R consists of the following rules:

   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(g(c)) -> g_flat(down(c))
   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(f(y6))) -> g_flat(down(f(y6)))

The set Q consists of the following terms:

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

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

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

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


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

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

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

The TRS R consists of the following rules:

   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(g(c)) -> g_flat(down(c))
   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(f(y6))) -> g_flat(down(f(y6)))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(c)) -> g_flat(down(c))

The set Q consists of the following terms:

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

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

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

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


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(c)) -> g_flat(down(c))

The set Q consists of the following terms:

   down(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(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 1 less node.
----------------------------------------

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   down(g(c)) -> g_flat(down(c))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

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

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

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

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


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

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

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

The TRS R consists of the following rules:

   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   down(g(fresh_constant)) -> g_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

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

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

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

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

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

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

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

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

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

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

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

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

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

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

Tuple symbols: 
<<<
 M( TOP_1(x_1) ) =  	[[0]] 	+ 	[[0, 1]] 	* 	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(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   g_flat(up(x_1)) -> up(g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

(97)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   down(f(fresh_constant)) -> f_flat(down(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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

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

The TRS R consists of the following rules:

   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   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))
   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))

The set Q consists of the following terms:

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

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

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

No dependency pairs are removed.

The following rules are removed from R:

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

   POL(TOP.0(x_1)) = x_1
   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)) = 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


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

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

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

The TRS R consists of the following rules:

   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))

The set Q consists of the following terms:

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

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

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

No dependency pairs are removed.

The following rules are removed from R:

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

   POL(TOP.0(x_1)) = x_1
   POL(c.) = 0
   POL(down.0(x_1)) = 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(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


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

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

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

The TRS R consists of the following rules:

   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   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))

The set Q consists of the following terms:

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

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

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

(108)
TRUE

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

(110) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN].

   down(f(fresh_constant))
   down(g(fresh_constant))
   down(g(g(fresh_constant)))


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(g(f(x0)))
   down(g(c))
   down(g(g(f(x0))))
   down(g(g(c)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

(113)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   down(f(c)) -> f_flat(down(c))
   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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

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

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

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

The TRS R consists of the following rules:

   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   down.0(f.1(c.)) -> f_flat.0(down.1(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))
   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))

The set Q consists of the following terms:

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

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

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

No dependency pairs are removed.

The following rules are removed from R:

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

   POL(TOP.0(x_1)) = x_1
   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


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

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

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

The TRS R consists of the following rules:

   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))

The set Q consists of the following terms:

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

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

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

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

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

The TRS R consists of the following rules:

   g_flat.0(up.0(x_1)) -> up.0(g.0(x_1))
   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(g.1(x))) -> up.0(g.0(g.0(f.0(f.1(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   f_flat.0(up.0(x_1)) -> up.0(f.0(x_1))

The set Q consists of the following terms:

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

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

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

No dependency pairs are removed.

The following rules are removed from R:

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

   POL(TOP.0(x_1)) = x_1
   POL(down.0(x_1)) = 1 + x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = x_1
   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


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

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

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

The TRS R consists of the following rules:

   down.0(f.0(g.0(x))) -> up.0(g.0(g.0(f.0(f.0(x)))))
   down.0(f.0(f.0(y3))) -> f_flat.0(down.0(f.0(y3)))
   down.0(f.0(f.1(y3))) -> f_flat.0(down.0(f.1(y3)))
   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))

The set Q consists of the following terms:

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

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

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

(124)
TRUE

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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(f(c))
   down(f(fresh_constant))
   down(g(f(x0)))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(f(x0))))
   down(g(g(c)))
   down(g(g(fresh_constant)))
   f_flat(up(x0))
   g_flat(up(x0))

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

(126) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN].

   down(f(c))
   down(f(fresh_constant))
   down(g(c))
   down(g(fresh_constant))
   down(g(g(c)))
   down(g(g(fresh_constant)))


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

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

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

The TRS R consists of the following rules:

   down(f(g(x))) -> up(g(g(f(f(x)))))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   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(f(g(x0)))
   down(g(g(g(x0))))
   down(f(f(x0)))
   down(g(f(x0)))
   down(g(g(f(x0))))
   f_flat(up(x0))
   g_flat(up(x0))

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