/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) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms]
(2) QTRS
    (3) QTRSRRRProof [EQUIVALENT, 79 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) 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) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (24) YES
        (25) QDP
            (26) UsableRulesProof [EQUIVALENT, 0 ms]
            (27) QDP
                (28) QReductionProof [EQUIVALENT, 0 ms]
                (29) QDP
                (30) TransformationProof [SOUND, 0 ms]
                (31) QDP
                (32) TransformationProof [EQUIVALENT, 0 ms]
                (33) QDP
                (34) TransformationProof [EQUIVALENT, 0 ms]
                (35) QDP
                (36) TransformationProof [SOUND, 0 ms]
                (37) QDP
                (38) TransformationProof [EQUIVALENT, 0 ms]
                (39) QDP
                (40) QDPOrderProof [EQUIVALENT, 15 ms]
                (41) QDP
                (42) QDPOrderProof [EQUIVALENT, 0 ms]
                (43) QDP
                (44) QDPOrderProof [EQUIVALENT, 8 ms]
                (45) QDP
                (46) QDPOrderProof [EQUIVALENT, 313 ms]
                (47) QDP
            (48) UsableRulesProof [EQUIVALENT, 0 ms]
            (49) QDP
                (50) QReductionProof [EQUIVALENT, 0 ms]
                (51) QDP
(52) Trivial-Transformation [SOUND, 0 ms]
(53) QTRS
    (54) QTRSRRRProof [EQUIVALENT, 65 ms]
    (55) QTRS
    (56) Overlay + Local Confluence [EQUIVALENT, 0 ms]
    (57) QTRS
    (58) DependencyPairsProof [EQUIVALENT, 0 ms]
    (59) QDP
    (60) DependencyGraphProof [EQUIVALENT, 0 ms]
    (61) QDP
    (62) UsableRulesProof [EQUIVALENT, 0 ms]
    (63) QDP
    (64) QReductionProof [EQUIVALENT, 0 ms]
    (65) QDP
    (66) TransformationProof [EQUIVALENT, 0 ms]
    (67) QDP
    (68) NonTerminationLoopProof [COMPLETE, 0 ms]
    (69) NO
(70) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
(71) QTRS
    (72) QTRSRRRProof [EQUIVALENT, 66 ms]
    (73) QTRS
    (74) QTRSRRRProof [EQUIVALENT, 19 ms]
    (75) QTRS
    (76) QTRSRRRProof [EQUIVALENT, 15 ms]
    (77) QTRS
    (78) QTRSRRRProof [EQUIVALENT, 18 ms]
    (79) QTRS
    (80) AAECC Innermost [EQUIVALENT, 0 ms]
    (81) QTRS
    (82) DependencyPairsProof [EQUIVALENT, 0 ms]
    (83) QDP
    (84) DependencyGraphProof [EQUIVALENT, 0 ms]
    (85) AND
        (86) QDP
            (87) UsableRulesProof [EQUIVALENT, 0 ms]
            (88) QDP
            (89) QReductionProof [EQUIVALENT, 0 ms]
            (90) QDP
            (91) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (92) YES
        (93) QDP
            (94) UsableRulesProof [EQUIVALENT, 0 ms]
            (95) QDP
            (96) QReductionProof [EQUIVALENT, 0 ms]
            (97) QDP
            (98) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (99) YES
        (100) QDP
            (101) UsableRulesProof [EQUIVALENT, 0 ms]
            (102) QDP
            (103) QReductionProof [EQUIVALENT, 0 ms]
            (104) QDP
            (105) TransformationProof [EQUIVALENT, 0 ms]
            (106) QDP
            (107) DependencyGraphProof [EQUIVALENT, 0 ms]
            (108) QDP
            (109) TransformationProof [EQUIVALENT, 0 ms]
            (110) QDP
            (111) TransformationProof [EQUIVALENT, 0 ms]
            (112) QDP
            (113) TransformationProof [EQUIVALENT, 0 ms]
            (114) QDP
            (115) TransformationProof [EQUIVALENT, 0 ms]
            (116) QDP
            (117) QDPOrderProof [EQUIVALENT, 13 ms]
            (118) QDP
            (119) QDPOrderProof [EQUIVALENT, 11 ms]
            (120) QDP
            (121) DependencyGraphProof [EQUIVALENT, 0 ms]
            (122) QDP
            (123) QDPOrderProof [EQUIVALENT, 8 ms]
            (124) QDP
            (125) QDPOrderProof [EQUIVALENT, 8 ms]
            (126) QDP
            (127) QDPOrderProof [EQUIVALENT, 502 ms]
            (128) QDP
            (129) MNOCProof [EQUIVALENT, 0 ms]
            (130) QDP
            (131) SplitQDPProof [EQUIVALENT, 0 ms]
            (132) AND
                (133) QDP
                    (134) SemLabProof [SOUND, 0 ms]
                    (135) QDP
                    (136) DependencyGraphProof [EQUIVALENT, 0 ms]
                    (137) QDP
                    (138) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                    (139) QDP
                    (140) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                    (141) QDP
                    (142) PisEmptyProof [SOUND, 0 ms]
                    (143) TRUE
                (144) QDP
                    (145) QReductionProof [EQUIVALENT, 0 ms]
                    (146) QDP
                        (147) MNOCProof [EQUIVALENT, 0 ms]
                        (148) QDP
                    (149) SplitQDPProof [EQUIVALENT, 0 ms]
                    (150) AND
                        (151) QDP
                            (152) SemLabProof [SOUND, 0 ms]
                            (153) QDP
                            (154) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                            (155) QDP
                            (156) MRRProof [EQUIVALENT, 0 ms]
                            (157) QDP
                            (158) QDPOrderProof [EQUIVALENT, 0 ms]
                            (159) QDP
                            (160) PisEmptyProof [SOUND, 0 ms]
                            (161) TRUE
                        (162) QDP
                            (163) QReductionProof [EQUIVALENT, 0 ms]
                            (164) QDP
                            (165) SplitQDPProof [EQUIVALENT, 0 ms]
                            (166) AND
                                (167) QDP
                                    (168) SemLabProof [SOUND, 0 ms]
                                    (169) QDP
                                    (170) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
                                    (171) QDP
                                    (172) MRRProof [EQUIVALENT, 0 ms]
                                    (173) QDP
                                    (174) QDPOrderProof [EQUIVALENT, 0 ms]
                                    (175) QDP
                                    (176) PisEmptyProof [SOUND, 0 ms]
                                    (177) TRUE
                                (178) QDP
                                    (179) QReductionProof [EQUIVALENT, 0 ms]
                                    (180) QDP


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

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

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   c -> n__c
   activate(n__g(X)) -> g(X)
   activate(n__c) -> c
   activate(X) -> X



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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   reduce(c) -> go_up(n__c)
   redex_activate(n__g(X)) -> result_activate(g(X))
   redex_activate(n__c) -> result_activate(c)
   redex_activate(X) -> result_activate(X)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))


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

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

   POL(activate(x_1)) = 1 + 2*x_1
   POL(c) = 1
   POL(check_activate(x_1)) = x_1
   POL(check_f(x_1)) = x_1
   POL(check_g(x_1)) = x_1
   POL(f(x_1)) = 1 + 2*x_1
   POL(g(x_1)) = x_1
   POL(go_up(x_1)) = x_1
   POL(in_activate_1(x_1)) = 1 + 2*x_1
   POL(in_f_1(x_1)) = 1 + 2*x_1
   POL(in_g_1(x_1)) = x_1
   POL(in_n__g_1(x_1)) = x_1
   POL(n__c) = 0
   POL(n__g(x_1)) = x_1
   POL(redex_activate(x_1)) = 1 + 2*x_1
   POL(redex_f(x_1)) = 1 + 2*x_1
   POL(redex_g(x_1)) = x_1
   POL(reduce(x_1)) = x_1
   POL(result_activate(x_1)) = x_1
   POL(result_f(x_1)) = x_1
   POL(result_g(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   reduce(c) -> go_up(n__c)
   redex_activate(n__g(X)) -> result_activate(g(X))
   redex_activate(X) -> result_activate(X)




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

(4)
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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   redex_activate(n__c) -> result_activate(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_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(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)
   REDUCE(activate(x_1)) -> CHECK_ACTIVATE(redex_activate(x_1))
   REDUCE(activate(x_1)) -> REDEX_ACTIVATE(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)
   CHECK_ACTIVATE(redex_activate(x_1)) -> IN_ACTIVATE_1(reduce(x_1))
   CHECK_ACTIVATE(redex_activate(x_1)) -> REDUCE(x_1)
   REDUCE(n__g(x_1)) -> IN_N__G_1(reduce(x_1))
   REDUCE(n__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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   redex_activate(n__c) -> result_activate(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_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 12 less nodes.
----------------------------------------

(8)
Complex Obligation (AND)

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

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

   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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   redex_activate(n__c) -> result_activate(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_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:

   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(n__g(X)) -> result_f(g(activate(X)))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_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].

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))


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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

   redex_f(n__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))
The following rules are removed from R:

   redex_f(n__g(X)) -> result_f(g(activate(X)))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(CHECK_F(x_1)) = x_1
   POL(REDUCE(x_1)) = 2*x_1
   POL(activate(x_1)) = 2*x_1
   POL(f(x_1)) = 2*x_1
   POL(g(x_1)) = 2*x_1
   POL(n__g(x_1)) = 2*x_1
   POL(redex_f(x_1)) = 2*x_1
   POL(result_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(n__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(n__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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   redex_activate(n__c) -> result_activate(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_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(n__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(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))


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

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

   REDUCE(n__g(x_1)) -> REDUCE(x_1)

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

(23) 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(n__g(x_1)) -> REDUCE(x_1)
The graph contains the following edges 1 > 1


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

(24)
YES

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

(25)
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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   redex_f(n__g(X)) -> result_f(g(activate(X)))
   redex_g(X) -> result_g(n__g(X))
   redex_activate(n__c) -> result_activate(c)
   check_f(result_f(x)) -> go_up(x)
   check_g(result_g(x)) -> go_up(x)
   check_activate(result_activate(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))
   check_activate(redex_activate(x_1)) -> in_activate_1(reduce(x_1))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_g_1(go_up(x_1)) -> go_up(g(x_1))
   in_activate_1(go_up(x_1)) -> go_up(activate(x_1))

The set Q consists of the following terms:

   top(go_up(x0))
   reduce(f(x0))
   reduce(g(x0))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))

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

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

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

   reduce(f(x_1)) -> check_f(redex_f(x_1))
   reduce(g(x_1)) -> check_g(redex_g(x_1))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))

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

(28) 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))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))


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

(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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(30) TransformationProof (SOUND)
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))))
   (TOP(go_up(activate(x0))) -> TOP(check_activate(redex_activate(x0))),TOP(go_up(activate(x0))) -> TOP(check_activate(redex_activate(x0))))
   (TOP(go_up(c)) -> TOP(go_up(f(n__g(n__c)))),TOP(go_up(c)) -> TOP(go_up(f(n__g(n__c)))))
   (TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0))),TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0))))


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

(31)
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)))
   TOP(go_up(activate(x0))) -> TOP(check_activate(redex_activate(x0)))
   TOP(go_up(c)) -> TOP(go_up(f(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(32) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(go_up(g(x0))) -> TOP(check_g(result_g(n__g(x0)))),TOP(go_up(g(x0))) -> TOP(check_g(result_g(n__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(activate(x0))) -> TOP(check_activate(redex_activate(x0)))
   TOP(go_up(c)) -> TOP(go_up(f(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0)))
   TOP(go_up(g(x0))) -> TOP(check_g(result_g(n__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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(34) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(result_g(n__g(x0)))) at position [0] we obtained the following new rules [LPAR04]:

   (TOP(go_up(g(x0))) -> TOP(go_up(n__g(x0))),TOP(go_up(g(x0))) -> TOP(go_up(n__g(x0))))


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

(35)
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(activate(x0))) -> TOP(check_activate(redex_activate(x0)))
   TOP(go_up(c)) -> TOP(go_up(f(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0)))
   TOP(go_up(g(x0))) -> TOP(go_up(n__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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(36) TransformationProof (SOUND)
By narrowing [LPAR04] the rule TOP(go_up(activate(x0))) -> TOP(check_activate(redex_activate(x0))) at position [0,0] we obtained the following new rules [LPAR04]:

   (TOP(go_up(activate(n__c))) -> TOP(check_activate(result_activate(c))),TOP(go_up(activate(n__c))) -> TOP(check_activate(result_activate(c))))


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

(37)
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(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0)))
   TOP(go_up(g(x0))) -> TOP(go_up(n__g(x0)))
   TOP(go_up(activate(n__c))) -> TOP(check_activate(result_activate(c)))

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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(38) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule TOP(go_up(activate(n__c))) -> TOP(check_activate(result_activate(c))) at position [0] we obtained the following new rules [LPAR04]:

   (TOP(go_up(activate(n__c))) -> TOP(go_up(c)),TOP(go_up(activate(n__c))) -> TOP(go_up(c)))


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

(39)
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(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0)))
   TOP(go_up(g(x0))) -> TOP(go_up(n__g(x0)))
   TOP(go_up(activate(n__c))) -> TOP(go_up(c))

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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_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(go_up(activate(n__c))) -> TOP(go_up(c))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = x_1
   POL(c) = 0
   POL(check_activate(x_1)) = 1
   POL(check_f(x_1)) = x_1
   POL(check_g(x_1)) = 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_n__g_1(x_1)) = 0
   POL(n__c) = 1
   POL(n__g(x_1)) = 0
   POL(redex_activate(x_1)) = x_1
   POL(redex_f(x_1)) = 0
   POL(redex_g(x_1)) = 1 + x_1
   POL(reduce(x_1)) = 0
   POL(result_activate(x_1)) = x_1
   POL(result_f(x_1)) = x_1
   POL(result_g(x_1)) = 1 + x_1

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

   redex_f(n__g(X)) -> result_f(g(activate(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_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))


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

(41)
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(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(x0)))
   TOP(go_up(g(x0))) -> TOP(go_up(n__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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = x_1
   POL(c) = 1
   POL(check_activate(x_1)) = 1
   POL(check_f(x_1)) = x_1
   POL(check_g(x_1)) = 1
   POL(f(x_1)) = 1
   POL(g(x_1)) = 1
   POL(go_up(x_1)) = x_1
   POL(in_f_1(x_1)) = 1
   POL(in_n__g_1(x_1)) = 0
   POL(n__c) = 0
   POL(n__g(x_1)) = 0
   POL(redex_activate(x_1)) = 0
   POL(redex_f(x_1)) = 1
   POL(redex_g(x_1)) = 1 + x_1
   POL(reduce(x_1)) = x_1
   POL(result_activate(x_1)) = 1 + x_1
   POL(result_f(x_1)) = x_1
   POL(result_g(x_1)) = 1 + x_1

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

   redex_f(n__g(X)) -> result_f(g(activate(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_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))


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

(43)
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(n__g(n__c))))
   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(44) 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(n__g(n__c))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = x_1
   POL(c) = 1
   POL(check_activate(x_1)) = 1
   POL(check_f(x_1)) = x_1
   POL(check_g(x_1)) = 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_n__g_1(x_1)) = 0
   POL(n__c) = 0
   POL(n__g(x_1)) = 0
   POL(redex_activate(x_1)) = 0
   POL(redex_f(x_1)) = 0
   POL(redex_g(x_1)) = 1 + x_1
   POL(reduce(x_1)) = 0
   POL(result_activate(x_1)) = x_1
   POL(result_f(x_1)) = x_1
   POL(result_g(x_1)) = 1 + x_1

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

   redex_f(n__g(X)) -> result_f(g(activate(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_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))


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

(45)
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(n__g(x0))) -> TOP(in_n__g_1(reduce(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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

(46) 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]] 	+ 	[[0, 1], [1, 1]] 	* 	x_1
>>>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tuple symbols: 
<<<
 M( TOP_1(x_1) ) =  	[[0]] 	+ 	[[1, 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:

   redex_f(n__g(X)) -> result_f(g(activate(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(g(x_1)) -> check_g(redex_g(x_1))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   in_f_1(go_up(x_1)) -> go_up(f(x_1))
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)


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

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

   TOP(go_up(n__g(x0))) -> TOP(in_n__g_1(reduce(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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

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

(49)
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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))

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

(50) 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))
   in_g_1(go_up(x0))
   in_activate_1(go_up(x0))


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

(51)
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))
   reduce(activate(x_1)) -> check_activate(redex_activate(x_1))
   reduce(c) -> go_up(f(n__g(n__c)))
   reduce(n__g(x_1)) -> in_n__g_1(reduce(x_1))
   in_n__g_1(go_up(x_1)) -> go_up(n__g(x_1))
   redex_activate(n__c) -> result_activate(c)
   check_activate(result_activate(x)) -> go_up(x)
   redex_g(X) -> result_g(n__g(X))
   check_g(result_g(x)) -> go_up(x)
   redex_f(n__g(X)) -> result_f(g(activate(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))
   reduce(activate(x0))
   reduce(c)
   redex_f(n__g(x0))
   redex_g(x0)
   redex_activate(x0)
   check_f(result_f(x0))
   check_g(result_g(x0))
   check_activate(result_activate(x0))
   check_f(redex_f(x0))
   reduce(n__g(x0))
   in_f_1(go_up(x0))
   in_n__g_1(go_up(x0))

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

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

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

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   c -> n__c
   activate(n__g(X)) -> g(X)
   activate(n__c) -> c
   activate(X) -> X

Q is empty.

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

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

   POL(activate(x_1)) = 1 + 2*x_1
   POL(c) = 1
   POL(f(x_1)) = 1 + 2*x_1
   POL(g(x_1)) = x_1
   POL(n__c) = 0
   POL(n__g(x_1)) = x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   c -> n__c
   activate(n__g(X)) -> g(X)
   activate(X) -> X




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

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

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   activate(n__c) -> c

Q is empty.

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

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

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

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   activate(n__c) -> c

The set Q consists of the following terms:

   c
   f(n__g(x0))
   g(x0)
   activate(n__c)


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

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

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

   C -> F(n__g(n__c))
   F(n__g(X)) -> G(activate(X))
   F(n__g(X)) -> ACTIVATE(X)
   ACTIVATE(n__c) -> C

The TRS R consists of the following rules:

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   activate(n__c) -> c

The set Q consists of the following terms:

   c
   f(n__g(x0))
   g(x0)
   activate(n__c)

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

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

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

   F(n__g(X)) -> ACTIVATE(X)
   ACTIVATE(n__c) -> C
   C -> F(n__g(n__c))

The TRS R consists of the following rules:

   c -> f(n__g(n__c))
   f(n__g(X)) -> g(activate(X))
   g(X) -> n__g(X)
   activate(n__c) -> c

The set Q consists of the following terms:

   c
   f(n__g(x0))
   g(x0)
   activate(n__c)

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

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

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

   F(n__g(X)) -> ACTIVATE(X)
   ACTIVATE(n__c) -> C
   C -> F(n__g(n__c))

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

   c
   f(n__g(x0))
   g(x0)
   activate(n__c)

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

(64) 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(n__g(x0))
   g(x0)
   activate(n__c)


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

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

   F(n__g(X)) -> ACTIVATE(X)
   ACTIVATE(n__c) -> C
   C -> F(n__g(n__c))

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

(66) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(n__g(X)) -> ACTIVATE(X) we obtained the following new rules [LPAR04]:

   (F(n__g(n__c)) -> ACTIVATE(n__c),F(n__g(n__c)) -> ACTIVATE(n__c))


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

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

   ACTIVATE(n__c) -> C
   C -> F(n__g(n__c))
   F(n__g(n__c)) -> ACTIVATE(n__c)

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

(68) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the right:

s = ACTIVATE(n__c) evaluates to  t =ACTIVATE(n__c)

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

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

ACTIVATE(n__c) -> C
 with rule ACTIVATE(n__c) -> C and matcher [ ].

C -> F(n__g(n__c))
with rule C -> F(n__g(n__c)) at position [] and matcher [ ]

F(n__g(n__c)) -> ACTIVATE(n__c)
with rule F(n__g(n__c)) -> ACTIVATE(n__c) at position [] and matcher [ ]

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.




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

(69)
NO

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

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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(c) -> up(n__c)
   down(activate(n__g(X))) -> up(g(X))
   down(activate(n__c)) -> up(c)
   down(activate(X)) -> up(X)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   g_flat(up(x_1)) -> up(g(x_1))
   activate_flat(up(x_1)) -> up(activate(x_1))

Q is empty.

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

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

   POL(activate(x_1)) = x_1
   POL(activate_flat(x_1)) = x_1
   POL(c) = 0
   POL(down(x_1)) = 2*x_1
   POL(f(x_1)) = 2*x_1
   POL(f_flat(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = 2*x_1
   POL(g_flat(x_1)) = 2 + 2*x_1
   POL(n__c) = 0
   POL(n__g(x_1)) = 2*x_1
   POL(n__g_flat(x_1)) = 2*x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

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




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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(c) -> up(n__c)
   down(activate(n__g(X))) -> up(g(X))
   down(activate(n__c)) -> up(c)
   down(activate(X)) -> up(X)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   activate_flat(up(x_1)) -> up(activate(x_1))

Q is empty.

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

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

   POL(activate(x_1)) = x_1
   POL(activate_flat(x_1)) = 1 + x_1
   POL(c) = 0
   POL(down(x_1)) = 2*x_1
   POL(f(x_1)) = x_1
   POL(f_flat(x_1)) = x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = 2*x_1
   POL(n__c) = 0
   POL(n__g(x_1)) = 2*x_1
   POL(n__g_flat(x_1)) = 2*x_1
   POL(top(x_1)) = x_1
   POL(up(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   activate_flat(up(x_1)) -> up(activate(x_1))




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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(c) -> up(n__c)
   down(activate(n__g(X))) -> up(g(X))
   down(activate(n__c)) -> up(c)
   down(activate(X)) -> up(X)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

Q is empty.

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

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

   POL(activate(x_1)) = 2*x_1
   POL(c) = 2
   POL(down(x_1)) = 2*x_1
   POL(f(x_1)) = 2*x_1
   POL(f_flat(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = x_1
   POL(n__c) = 1
   POL(n__g(x_1)) = x_1
   POL(n__g_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(c) -> up(n__c)




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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__g(X))) -> up(g(X))
   down(activate(n__c)) -> up(c)
   down(activate(X)) -> up(X)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

Q is empty.

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

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

   POL(activate(x_1)) = 1 + x_1
   POL(c) = 1
   POL(down(x_1)) = 2*x_1
   POL(f(x_1)) = 1 + 2*x_1
   POL(f_flat(x_1)) = 2 + 2*x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = x_1
   POL(n__c) = 0
   POL(n__g(x_1)) = x_1
   POL(n__g_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(activate(n__g(X))) -> up(g(X))
   down(activate(X)) -> up(X)




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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

Q is empty.

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

(80) AAECC Innermost (EQUIVALENT)
We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)

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

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

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

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))


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

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

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

   TOP(up(x)) -> TOP(down(x))
   TOP(up(x)) -> DOWN(x)
   DOWN(n__g(y1)) -> N__G_FLAT(down(y1))
   DOWN(n__g(y1)) -> DOWN(y1)
   DOWN(f(c)) -> F_FLAT(down(c))
   DOWN(f(c)) -> DOWN(c)
   DOWN(f(f(y5))) -> F_FLAT(down(f(y5)))
   DOWN(f(f(y5))) -> DOWN(f(y5))
   DOWN(f(n__c)) -> F_FLAT(down(n__c))
   DOWN(f(n__c)) -> DOWN(n__c)
   DOWN(f(g(y7))) -> F_FLAT(down(g(y7)))
   DOWN(f(g(y7))) -> DOWN(g(y7))
   DOWN(f(activate(y8))) -> F_FLAT(down(activate(y8)))
   DOWN(f(activate(y8))) -> DOWN(activate(y8))
   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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

(85)
Complex Obligation (AND)

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

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

   DOWN(f(f(y5))) -> DOWN(f(y5))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   DOWN(f(f(y5))) -> DOWN(f(y5))

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

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(89) 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(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))


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

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

   DOWN(f(f(y5))) -> DOWN(f(y5))

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

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


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

(92)
YES

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

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

   DOWN(n__g(y1)) -> DOWN(y1)

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   DOWN(n__g(y1)) -> DOWN(y1)

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

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(96) 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(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))


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

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

   DOWN(n__g(y1)) -> DOWN(y1)

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

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


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

(99)
YES

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

(100)
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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   top(up(x)) -> top(down(x))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

(102)
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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   top(up(x0))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


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

(104)
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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(105) 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(n__g(n__c)))),TOP(up(c)) -> TOP(up(f(n__g(n__c)))))
   (TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0)))),TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0)))))
   (TOP(up(g(x0))) -> TOP(up(n__g(x0))),TOP(up(g(x0))) -> TOP(up(n__g(x0))))
   (TOP(up(activate(n__c))) -> TOP(up(c)),TOP(up(activate(n__c))) -> TOP(up(c)))
   (TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0))),TOP(up(n__g(x0))) -> TOP(n__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(n__c))) -> TOP(f_flat(down(n__c))),TOP(up(f(n__c))) -> TOP(f_flat(down(n__c))))
   (TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))),TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))))
   (TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0)))),TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0)))))
   (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))))


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

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

   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(activate(n__c))) -> TOP(up(c))
   TOP(up(n__g(x0))) -> TOP(n__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(n__c))) -> TOP(f_flat(down(n__c)))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(c))) -> TOP(f_flat(down(c)))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(109) 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(n__g(n__c))))),TOP(up(f(c))) -> TOP(f_flat(up(f(n__g(n__c))))))


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(f_flat(up(f(n__g(n__c)))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(f_flat(up(f(n__g(n__c)))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(up(n__g(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

   (TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c))))),TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c))))))


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(g(x0)))) -> TOP(f_flat(up(n__g(x0))))
   TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c)))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

   (TOP(up(f(g(x0)))) -> TOP(up(f(n__g(x0)))),TOP(up(f(g(x0)))) -> TOP(up(f(n__g(x0)))))


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(c)) -> TOP(up(f(n__g(n__c))))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c)))))
   TOP(up(f(g(x0)))) -> TOP(up(f(n__g(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = 0
   POL(c) = 1
   POL(down(x_1)) = 0
   POL(f(x_1)) = 0
   POL(f_flat(x_1)) = 0
   POL(fresh_constant) = 0
   POL(g(x_1)) = 0
   POL(n__c) = 0
   POL(n__g(x_1)) = 0
   POL(n__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:

   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(g(x0))) -> TOP(up(n__g(x0)))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c)))))
   TOP(up(f(g(x0)))) -> TOP(up(f(n__g(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(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(up(g(x0))) -> TOP(up(n__g(x0)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = 0
   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)) = 1
   POL(n__c) = 0
   POL(n__g(x_1)) = 0
   POL(n__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:

   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

   TOP(up(f(n__g(x0)))) -> TOP(up(g(activate(x0))))
   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c)))))
   TOP(up(f(g(x0)))) -> TOP(up(f(n__g(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))
   TOP(up(f(c))) -> TOP(up(f(f(n__g(n__c)))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(123) 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(n__g(n__c)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = x_1
   POL(c) = 1
   POL(down(x_1)) = x_1
   POL(f(x_1)) = x_1
   POL(f_flat(x_1)) = x_1
   POL(fresh_constant) = 0
   POL(g(x_1)) = 0
   POL(n__c) = 1
   POL(n__g(x_1)) = 0
   POL(n__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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))
   TOP(up(f(f(x0)))) -> TOP(f_flat(down(f(x0))))
   TOP(up(f(activate(x0)))) -> TOP(f_flat(down(activate(x0))))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP(x_1)) = x_1
   POL(activate(x_1)) = 1
   POL(c) = 0
   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(n__c) = 0
   POL(n__g(x_1)) = 0
   POL(n__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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

   TOP(up(n__g(x0))) -> TOP(n__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(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(127) 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], [1, 1]] 	* 	x_1
>>>

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

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

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

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

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

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

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

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

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

Tuple symbols: 
<<<
 M( TOP_1(x_1) ) =  	[[0]] 	+ 	[[1, 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(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))


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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

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

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

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

(132)
Complex Obligation (AND)

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   down(f(fresh_constant)) -> f_flat(down(fresh_constant))
   f_flat(up(x_1)) -> up(f(x_1))
   n__g_flat(up(x_1)) -> up(n__g(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.0(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.0(activate.0(X)))
   down.0(f.0(n__g.1(X))) -> up.0(g.0(activate.1(X)))
   down.0(g.0(X)) -> up.0(n__g.0(X))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.0(activate.0(n__c.)) -> up.0(c.)
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   down.0(f.0(activate.0(y8))) -> f_flat.0(down.0(activate.0(y8)))
   down.0(f.0(activate.1(y8))) -> f_flat.0(down.0(activate.1(y8)))
   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))
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   n__g_flat.0(up.1(x_1)) -> up.0(n__g.1(x_1))

The set Q consists of the following terms:

   down.0(c.)
   down.0(f.0(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.0(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(activate.0(x0)))
   down.0(f.0(activate.1(x0)))
   down.0(f.1(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.0(activate.0(X)))
   down.0(f.0(n__g.1(X))) -> up.0(g.0(activate.1(X)))
   down.0(g.0(X)) -> up.0(n__g.0(X))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.0(activate.0(n__c.)) -> up.0(c.)
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   down.0(f.0(activate.0(y8))) -> f_flat.0(down.0(activate.0(y8)))
   down.0(f.0(activate.1(y8))) -> f_flat.0(down.0(activate.1(y8)))
   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))
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   n__g_flat.0(up.1(x_1)) -> up.0(n__g.1(x_1))

The set Q consists of the following terms:

   down.0(c.)
   down.0(f.0(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.0(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(activate.0(x0)))
   down.0(f.0(activate.1(x0)))
   down.0(f.1(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

(138) 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(X)) -> up.0(n__g.1(X))
   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))
   n__g_flat.0(up.1(x_1)) -> up.0(n__g.1(x_1))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(activate.0(x_1)) = x_1
   POL(activate.1(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(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.0(activate.0(X)))
   down.0(f.0(n__g.1(X))) -> up.0(g.0(activate.1(X)))
   down.0(g.0(X)) -> up.0(n__g.0(X))
   down.0(activate.0(n__c.)) -> up.0(c.)
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   down.0(f.0(activate.0(y8))) -> f_flat.0(down.0(activate.0(y8)))
   down.0(f.0(activate.1(y8))) -> f_flat.0(down.0(activate.1(y8)))
   n__g_flat.0(up.0(x_1)) -> up.0(n__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(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.0(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(activate.0(x0)))
   down.0(f.0(activate.1(x0)))
   down.0(f.1(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

(140) 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(n__g.1(X))) -> up.0(g.0(activate.1(X)))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(activate.0(x_1)) = 1 + x_1
   POL(activate.1(x_1)) = 1 + x_1
   POL(c.) = 1
   POL(down.0(x_1)) = 1 + x_1
   POL(down.1(x_1)) = 1 + x_1
   POL(f.0(x_1)) = 1 + x_1
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = 1 + x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.0(activate.0(X)))
   down.0(g.0(X)) -> up.0(n__g.0(X))
   down.0(activate.0(n__c.)) -> up.0(c.)
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   down.0(f.0(activate.0(y8))) -> f_flat.0(down.0(activate.0(y8)))
   down.0(f.0(activate.1(y8))) -> f_flat.0(down.0(activate.1(y8)))
   n__g_flat.0(up.0(x_1)) -> up.0(n__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(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.0(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.0(activate.0(x0)))
   down.0(f.0(activate.1(x0)))
   down.0(f.1(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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

(143)
TRUE

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

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

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

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

(150)
Complex Obligation (AND)

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(activate(n__c)) -> up(c)
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   down(f(activate(y8))) -> f_flat(down(activate(y8)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

(152) 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: 0
n__g: 0
up: 0
n__g_flat: 0
f_flat: 0
n__c: 0
activate: 1
TOP: 0
g: 0
By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
----------------------------------------

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.0(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.1(activate.0(X)))
   down.0(f.0(n__g.1(X))) -> up.0(g.1(activate.1(X)))
   down.0(g.0(X)) -> up.0(n__g.0(X))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.1(activate.0(n__c.)) -> up.0(c.)
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   down.0(f.1(activate.0(y8))) -> f_flat.0(down.1(activate.0(y8)))
   down.0(f.1(activate.1(y8))) -> f_flat.0(down.1(activate.1(y8)))
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   n__g_flat.0(up.1(x_1)) -> up.0(n__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(c.)
   down.0(f.0(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.1(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(activate.0(x0)))
   down.0(f.1(activate.1(x0)))
   down.0(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

(154) 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.0(X)) -> up.0(n__g.0(X))
   down.0(f.1(activate.0(y8))) -> f_flat.0(down.1(activate.0(y8)))
   down.0(f.1(activate.1(y8))) -> f_flat.0(down.1(activate.1(y8)))
   n__g_flat.0(up.1(x_1)) -> up.0(n__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(activate.0(x_1)) = x_1
   POL(activate.1(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(g.0(x_1)) = 1 + x_1
   POL(g.1(x_1)) = x_1
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1
   POL(up.1(x_1)) = 1 + x_1


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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.0(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(activate.0(n__c.)) -> up.0(c.)
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.1(activate.0(X)))
   down.0(f.0(n__g.1(X))) -> up.0(g.1(activate.1(X)))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   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(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.1(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(activate.0(x0)))
   down.0(f.1(activate.1(x0)))
   down.0(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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


Strictly oriented rules of the TRS R:

   down.0(f.0(n__g.1(X))) -> up.0(g.1(activate.1(X)))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(activate.0(x_1)) = 1 + x_1
   POL(activate.1(x_1)) = x_1
   POL(c.) = 1
   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)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = x_1


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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.0(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(activate.0(n__c.)) -> up.0(c.)
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.1(activate.0(X)))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   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(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.1(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(activate.0(x0)))
   down.0(f.1(activate.1(x0)))
   down.0(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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


The following pairs can be oriented strictly and are deleted.

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

   POL(TOP.0(x_1)) = x_1
   POL(activate.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)) = 0
   POL(f.1(x_1)) = x_1
   POL(f_flat.0(x_1)) = 0
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = 0
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = 0
   POL(n__g.1(x_1)) = 1 + x_1
   POL(n__g_flat.0(x_1)) = 0
   POL(up.0(x_1)) = x_1

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

   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))


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

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

   TOP.0(up.0(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))

The TRS R consists of the following rules:

   down.1(activate.0(n__c.)) -> up.0(c.)
   n__g_flat.0(up.0(x_1)) -> up.0(n__g.0(x_1))
   down.0(c.) -> up.0(f.0(n__g.0(n__c.)))
   down.0(f.0(n__g.0(X))) -> up.0(g.1(activate.0(X)))
   down.0(g.1(X)) -> up.0(n__g.1(X))
   down.0(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.0(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.0(f.0(c.)) -> f_flat.0(down.0(c.))
   down.0(f.0(f.0(y5))) -> f_flat.0(down.0(f.0(y5)))
   down.0(f.0(f.1(y5))) -> f_flat.0(down.0(f.1(y5)))
   down.0(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.0(f.0(g.0(y7))) -> f_flat.0(down.0(g.0(y7)))
   down.0(f.0(g.1(y7))) -> f_flat.0(down.0(g.1(y7)))
   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(n__g.0(x0)))
   down.0(f.0(n__g.1(x0)))
   down.0(g.0(x0))
   down.0(g.1(x0))
   down.1(activate.0(n__c.))
   down.0(n__g.0(x0))
   down.0(n__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.0(n__c.))
   down.0(f.0(g.0(x0)))
   down.0(f.0(g.1(x0)))
   down.0(f.1(activate.0(x0)))
   down.0(f.1(activate.1(x0)))
   down.0(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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

(161)
TRUE

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(activate(n__c)) -> up(c)
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(activate(n__c)) -> up(c)
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

(166)
Complex Obligation (AND)

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(activate(n__c)) -> up(c)
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(n__c)) -> f_flat(down(n__c))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   f_flat(up(x_1)) -> up(f(x_1))

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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

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

   TOP.0(up.1(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.1(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.0(activate.0(n__c.)) -> up.1(c.)
   n__g_flat.0(up.0(x_1)) -> up.1(n__g.0(x_1))
   n__g_flat.0(up.1(x_1)) -> up.1(n__g.1(x_1))
   down.1(c.) -> up.1(f.1(n__g.0(n__c.)))
   down.1(f.1(n__g.0(X))) -> up.1(g.0(activate.0(X)))
   down.1(f.1(n__g.1(X))) -> up.1(g.0(activate.1(X)))
   down.1(g.0(X)) -> up.1(n__g.0(X))
   down.1(g.1(X)) -> up.1(n__g.1(X))
   down.1(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.1(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.1(f.1(c.)) -> f_flat.0(down.1(c.))
   down.1(f.1(f.0(y5))) -> f_flat.0(down.1(f.0(y5)))
   down.1(f.1(f.1(y5))) -> f_flat.0(down.1(f.1(y5)))
   down.1(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   down.1(f.1(g.0(y7))) -> f_flat.0(down.1(g.0(y7)))
   down.1(f.1(g.1(y7))) -> f_flat.0(down.1(g.1(y7)))
   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.1(c.)
   down.1(f.1(n__g.0(x0)))
   down.1(f.1(n__g.1(x0)))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(activate.0(n__c.))
   down.1(n__g.0(x0))
   down.1(n__g.1(x0))
   down.1(f.1(c.))
   down.1(f.1(f.0(x0)))
   down.1(f.1(f.1(x0)))
   down.1(f.0(n__c.))
   down.1(f.1(g.0(x0)))
   down.1(f.1(g.1(x0)))
   down.1(f.0(activate.0(x0)))
   down.1(f.0(activate.1(x0)))
   down.1(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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

   n__g_flat.0(up.0(x_1)) -> up.1(n__g.0(x_1))
   down.1(g.1(X)) -> up.1(n__g.1(X))
   down.1(f.0(n__c.)) -> f_flat.0(down.0(n__c.))
   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(activate.0(x_1)) = x_1
   POL(activate.1(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)) = 1 + x_1
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.0(x_1)) = 1 + x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.0(up.1(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.1(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(c.) -> up.1(f.1(n__g.0(n__c.)))
   down.1(f.1(n__g.0(X))) -> up.1(g.0(activate.0(X)))
   down.1(f.1(n__g.1(X))) -> up.1(g.0(activate.1(X)))
   down.1(g.0(X)) -> up.1(n__g.0(X))
   down.1(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.1(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.1(f.1(c.)) -> f_flat.0(down.1(c.))
   down.1(f.1(f.0(y5))) -> f_flat.0(down.1(f.0(y5)))
   down.1(f.1(f.1(y5))) -> f_flat.0(down.1(f.1(y5)))
   down.1(f.1(g.0(y7))) -> f_flat.0(down.1(g.0(y7)))
   down.1(f.1(g.1(y7))) -> f_flat.0(down.1(g.1(y7)))
   n__g_flat.0(up.1(x_1)) -> up.1(n__g.1(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(activate.0(n__c.)) -> up.1(c.)

The set Q consists of the following terms:

   down.1(c.)
   down.1(f.1(n__g.0(x0)))
   down.1(f.1(n__g.1(x0)))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(activate.0(n__c.))
   down.1(n__g.0(x0))
   down.1(n__g.1(x0))
   down.1(f.1(c.))
   down.1(f.1(f.0(x0)))
   down.1(f.1(f.1(x0)))
   down.1(f.0(n__c.))
   down.1(f.1(g.0(x0)))
   down.1(f.1(g.1(x0)))
   down.1(f.0(activate.0(x0)))
   down.1(f.0(activate.1(x0)))
   down.1(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

(172) 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.1(n__g.1(X))) -> up.1(g.0(activate.1(X)))

Used ordering: Polynomial interpretation [POLO]:

   POL(TOP.0(x_1)) = x_1
   POL(activate.0(x_1)) = 1 + x_1
   POL(activate.1(x_1)) = x_1
   POL(c.) = 1
   POL(down.0(x_1)) = x_1
   POL(down.1(x_1)) = x_1
   POL(f.0(x_1)) = x_1
   POL(f.1(x_1)) = 1 + x_1
   POL(f_flat.0(x_1)) = 1 + x_1
   POL(g.0(x_1)) = x_1
   POL(g.1(x_1)) = x_1
   POL(n__c.) = 0
   POL(n__g.0(x_1)) = x_1
   POL(n__g.1(x_1)) = x_1
   POL(n__g_flat.0(x_1)) = x_1
   POL(up.1(x_1)) = x_1


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

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

   TOP.0(up.1(n__g.0(x0))) -> TOP.0(n__g_flat.0(down.0(x0)))
   TOP.0(up.1(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(c.) -> up.1(f.1(n__g.0(n__c.)))
   down.1(f.1(n__g.0(X))) -> up.1(g.0(activate.0(X)))
   down.1(g.0(X)) -> up.1(n__g.0(X))
   down.1(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.1(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.1(f.1(c.)) -> f_flat.0(down.1(c.))
   down.1(f.1(f.0(y5))) -> f_flat.0(down.1(f.0(y5)))
   down.1(f.1(f.1(y5))) -> f_flat.0(down.1(f.1(y5)))
   down.1(f.1(g.0(y7))) -> f_flat.0(down.1(g.0(y7)))
   down.1(f.1(g.1(y7))) -> f_flat.0(down.1(g.1(y7)))
   n__g_flat.0(up.1(x_1)) -> up.1(n__g.1(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(activate.0(n__c.)) -> up.1(c.)

The set Q consists of the following terms:

   down.1(c.)
   down.1(f.1(n__g.0(x0)))
   down.1(f.1(n__g.1(x0)))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(activate.0(n__c.))
   down.1(n__g.0(x0))
   down.1(n__g.1(x0))
   down.1(f.1(c.))
   down.1(f.1(f.0(x0)))
   down.1(f.1(f.1(x0)))
   down.1(f.0(n__c.))
   down.1(f.1(g.0(x0)))
   down.1(f.1(g.1(x0)))
   down.1(f.0(activate.0(x0)))
   down.1(f.0(activate.1(x0)))
   down.1(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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


The following pairs can be oriented strictly and are deleted.

   TOP.0(up.1(n__g.0(x0))) -> TOP.0(n__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(activate.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)) = 0
   POL(g.1(x_1)) = x_1
   POL(n__c.) = 1
   POL(n__g.0(x_1)) = 1
   POL(n__g.1(x_1)) = 0
   POL(n__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:

   n__g_flat.0(up.1(x_1)) -> up.1(n__g.1(x_1))


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

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

   TOP.0(up.1(n__g.1(x0))) -> TOP.0(n__g_flat.0(down.1(x0)))

The TRS R consists of the following rules:

   down.1(c.) -> up.1(f.1(n__g.0(n__c.)))
   down.1(f.1(n__g.0(X))) -> up.1(g.0(activate.0(X)))
   down.1(g.0(X)) -> up.1(n__g.0(X))
   down.1(n__g.0(y1)) -> n__g_flat.0(down.0(y1))
   down.1(n__g.1(y1)) -> n__g_flat.0(down.1(y1))
   down.1(f.1(c.)) -> f_flat.0(down.1(c.))
   down.1(f.1(f.0(y5))) -> f_flat.0(down.1(f.0(y5)))
   down.1(f.1(f.1(y5))) -> f_flat.0(down.1(f.1(y5)))
   down.1(f.1(g.0(y7))) -> f_flat.0(down.1(g.0(y7)))
   down.1(f.1(g.1(y7))) -> f_flat.0(down.1(g.1(y7)))
   n__g_flat.0(up.1(x_1)) -> up.1(n__g.1(x_1))
   f_flat.0(up.1(x_1)) -> up.1(f.1(x_1))
   down.0(activate.0(n__c.)) -> up.1(c.)

The set Q consists of the following terms:

   down.1(c.)
   down.1(f.1(n__g.0(x0)))
   down.1(f.1(n__g.1(x0)))
   down.1(g.0(x0))
   down.1(g.1(x0))
   down.0(activate.0(n__c.))
   down.1(n__g.0(x0))
   down.1(n__g.1(x0))
   down.1(f.1(c.))
   down.1(f.1(f.0(x0)))
   down.1(f.1(f.1(x0)))
   down.1(f.0(n__c.))
   down.1(f.1(g.0(x0)))
   down.1(f.1(g.1(x0)))
   down.1(f.0(activate.0(x0)))
   down.1(f.0(activate.1(x0)))
   down.1(f.0(fresh_constant.))
   f_flat.0(up.0(x0))
   f_flat.0(up.1(x0))
   n__g_flat.0(up.0(x0))
   n__g_flat.0(up.1(x0))

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

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

(177)
TRUE

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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(activate(n__c)) -> up(c)

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   down(f(fresh_constant))
   f_flat(up(x0))
   n__g_flat(up(x0))

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

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


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

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

   TOP(up(n__g(x0))) -> TOP(n__g_flat(down(x0)))

The TRS R consists of the following rules:

   down(c) -> up(f(n__g(n__c)))
   down(f(n__g(X))) -> up(g(activate(X)))
   down(g(X)) -> up(n__g(X))
   down(n__g(y1)) -> n__g_flat(down(y1))
   down(f(c)) -> f_flat(down(c))
   down(f(f(y5))) -> f_flat(down(f(y5)))
   down(f(g(y7))) -> f_flat(down(g(y7)))
   n__g_flat(up(x_1)) -> up(n__g(x_1))
   f_flat(up(x_1)) -> up(f(x_1))
   down(activate(n__c)) -> up(c)

The set Q consists of the following terms:

   down(c)
   down(f(n__g(x0)))
   down(g(x0))
   down(activate(n__c))
   down(n__g(x0))
   down(f(c))
   down(f(f(x0)))
   down(f(n__c))
   down(f(g(x0)))
   down(f(activate(x0)))
   f_flat(up(x0))
   n__g_flat(up(x0))

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