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


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


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


Outermost Termination of the given OTRS could not be shown:

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


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

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

   c -> f(g(c))
   f(g(X)) -> g(X)



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

Q is empty.

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

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

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

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

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

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


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

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

(6)
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(y1)) -> G_FLAT(down(y1))
   DOWN(g(y1)) -> DOWN(y1)
   DOWN(f(c)) -> F_FLAT(down(c))
   DOWN(f(c)) -> DOWN(c)
   DOWN(f(f(y3))) -> F_FLAT(down(f(y3)))
   DOWN(f(f(y3))) -> DOWN(f(y3))
   DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant))
   DOWN(f(fresh_constant)) -> DOWN(fresh_constant)

The TRS R consists of the following rules:

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

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

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

(8)
Complex Obligation (AND)

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

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

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

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

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

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

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


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

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

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


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

(15)
YES

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

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

   DOWN(g(y1)) -> DOWN(y1)

The TRS R consists of the following rules:

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

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

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

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

   DOWN(g(y1)) -> DOWN(y1)

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

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

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

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


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

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

   DOWN(g(y1)) -> DOWN(y1)

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

(21) 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(g(y1)) -> DOWN(y1)
The graph contains the following edges 1 > 1


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

(22)
YES

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

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

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

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

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

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

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


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

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

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

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


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

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

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

The TRS R consists of the following rules:

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

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

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

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

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

The TRS R consists of the following rules:

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

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

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

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


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

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

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

The TRS R consists of the following rules:

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

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

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

   (TOP(up(f(c))) -> TOP(up(f(f(g(c))))),TOP(up(f(c))) -> TOP(up(f(f(g(c))))))


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

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

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

The TRS R consists of the following rules:

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

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

(36) 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(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)) = 0
   POL(f(x_1)) = 1
   POL(f_flat(x_1)) = 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:

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


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

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

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

The TRS R consists of the following rules:

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

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP(x_1)) = x_1
   POL(c) = 1
   POL(down(x_1)) = 0
   POL(f(x_1)) = x_1
   POL(f_flat(x_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(c) -> up(f(g(c)))
   down(f(g(X))) -> up(g(X))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   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))


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

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

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

The TRS R consists of the following rules:

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

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

(40) 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:  Matrix interpretation [MATRO]:

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

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

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

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

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

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

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

<<<
 M( g_flat_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 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(c) -> up(f(g(c)))
   down(f(g(X))) -> up(g(X))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y3))) -> f_flat(down(f(y3)))
   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))


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

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

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

The TRS R consists of the following rules:

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

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

(42) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.
----------------------------------------

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

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

The TRS R consists of the following rules:

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

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

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

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

(45)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

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

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

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

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

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

The TRS R consists of the following rules:

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

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

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

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

The TRS R consists of the following rules:

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

(51) 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(g.1(y1)) -> g_flat.0(down.1(y1))
   down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.))
   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(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)) = 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


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

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

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

The TRS R consists of the following rules:

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

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

(54)
TRUE

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

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

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

The TRS R consists of the following rules:

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

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

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


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

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

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

The TRS R consists of the following rules:

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

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

(58) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.
----------------------------------------

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

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

The TRS R consists of the following rules:

   down(c) -> up(f(g(c)))
   down(f(g(X))) -> up(g(X))
   down(g(y1)) -> g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   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))

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

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

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

(61)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

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

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

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

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

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


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

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

Used ordering: Polynomial interpretation [POLO]:

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


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

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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


The following pairs can be oriented strictly and are deleted.

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

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

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

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


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

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(72)
TRUE

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

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

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

The TRS R consists of the following rules:

   down(f(g(X))) -> up(g(X))
   down(g(y1)) -> g_flat(down(y1))
   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))
   down(c) -> up(f(g(c)))

The set Q consists of the following terms:

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

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

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


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

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

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

The TRS R consists of the following rules:

   down(f(g(X))) -> up(g(X))
   down(g(y1)) -> g_flat(down(y1))
   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))
   down(c) -> up(f(g(c)))

The set Q consists of the following terms:

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

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

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

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

   c -> f(g(c))
   f(g(X)) -> g(X)

Q is empty.

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

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

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

   c -> f(g(c))
   f(g(X)) -> g(X)

The set Q consists of the following terms:

   c
   f(g(x0))


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

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

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

   C -> F(g(c))
   C -> C

The TRS R consists of the following rules:

   c -> f(g(c))
   f(g(X)) -> g(X)

The set Q consists of the following terms:

   c
   f(g(x0))

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

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

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

   C -> C

The TRS R consists of the following rules:

   c -> f(g(c))
   f(g(X)) -> g(X)

The set Q consists of the following terms:

   c
   f(g(x0))

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

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

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

   C -> C

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

   c
   f(g(x0))

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

(86) 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].

   c
   f(g(x0))


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

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

   C -> C

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

(88) 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 = C evaluates to  t =C

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

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

The DP semiunifies directly so there is only one rewrite step from C to C.




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

(89)
NO

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

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

(91)
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(c) -> go_up(f(g(c)))
   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

(93)
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)
   CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1))
   CHECK_F(redex_f(x_1)) -> REDUCE(x_1)
   REDUCE(g(x_1)) -> IN_G_1(reduce(x_1))
   REDUCE(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(c) -> go_up(f(g(c)))
   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

(95)
Complex Obligation (AND)

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

(96)
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(c) -> go_up(f(g(c)))
   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

(98)
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(X))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(99) 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(c)
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

The set Q consists of the following terms:

   redex_f(g(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.

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)) = x_1
   POL(REDUCE(x_1)) = 2*x_1
   POL(f(x_1)) = 2*x_1
   POL(g(x_1)) = 2*x_1
   POL(redex_f(x_1)) = 2*x_1
   POL(result_f(x_1)) = x_1


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

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

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

The TRS R consists of the following rules:

   redex_f(g(X)) -> result_f(g(X))

The set Q consists of the following terms:

   redex_f(g(x0))

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

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

(104)
TRUE

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

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

   REDUCE(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(c) -> go_up(f(g(c)))
   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

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

   REDUCE(g(x_1)) -> REDUCE(x_1)

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

   top(go_up(x0))
   reduce(f(x0))
   reduce(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(108) 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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))


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

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

   REDUCE(g(x_1)) -> REDUCE(x_1)

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

(110) 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:
*REDUCE(g(x_1)) -> REDUCE(x_1)
The graph contains the following edges 1 > 1


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

(111)
YES

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

(112)
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(c) -> go_up(f(g(c)))
   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

(114)
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(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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


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

(116)
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(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

(117) 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(c)) -> TOP(go_up(f(g(c)))),TOP(go_up(c)) -> TOP(go_up(f(g(c)))))
   (TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0))),TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0))))


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

(118)
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(c)) -> TOP(go_up(f(g(c))))
   TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0)))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP(x_1)) = x_1
   POL(c) = 1
   POL(check_f(x_1)) = x_1
   POL(f(x_1)) = 0
   POL(g(x_1)) = 0
   POL(go_up(x_1)) = x_1
   POL(in_f_1(x_1)) = 0
   POL(in_g_1(x_1)) = 0
   POL(redex_f(x_1)) = 0
   POL(reduce(x_1)) = 0
   POL(result_f(x_1)) = x_1

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

   redex_f(g(X)) -> result_f(g(X))
   check_f(result_f(x)) -> go_up(x)
   check_f(redex_f(x_1)) -> in_f_1(reduce(x_1))
   reduce(f(x_1)) -> check_f(redex_f(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))


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

(120)
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(in_g_1(reduce(x0)))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

   TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO]:

Non-tuple symbols: 
<<<
 M( result_f_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 1], [0, 0]] 	* 	x_1
>>>

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

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

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

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

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

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

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

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

<<<
 M( g_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 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:

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


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

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

   TOP(go_up(g(x0))) -> TOP(in_g_1(reduce(x0)))

The TRS R consists of the following rules:

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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

(124)
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(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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

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


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

(126)
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(c) -> go_up(f(g(c)))
   reduce(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(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(c)
   redex_f(g(x0))
   check_f(result_f(x0))
   check_f(redex_f(x0))
   reduce(g(x0))
   in_f_1(go_up(x0))
   in_g_1(go_up(x0))

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