172.09/86.09 MAYBE 172.09/86.10 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 172.09/86.10 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 172.09/86.10 172.09/86.10 172.09/86.10 Outermost Termination of the given OTRS could not be shown: 172.09/86.10 172.09/86.10 (0) OTRS 172.09/86.10 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 172.09/86.10 (2) QTRS 172.09/86.10 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 172.09/86.10 (4) QDP 172.09/86.10 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (6) AND 172.09/86.10 (7) QDP 172.09/86.10 (8) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (9) QDP 172.09/86.10 (10) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (11) QDP 172.09/86.10 (12) UsableRulesReductionPairsProof [EQUIVALENT, 9 ms] 172.09/86.10 (13) QDP 172.09/86.10 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (15) TRUE 172.09/86.10 (16) QDP 172.09/86.10 (17) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (18) QDP 172.09/86.10 (19) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (20) QDP 172.09/86.10 (21) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (22) QDP 172.09/86.10 (23) QDPOrderProof [EQUIVALENT, 9 ms] 172.09/86.10 (24) QDP 172.09/86.10 (25) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (26) QDP 172.09/86.10 (27) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (28) QDP 172.09/86.10 (29) Trivial-Transformation [SOUND, 0 ms] 172.09/86.10 (30) QTRS 172.09/86.10 (31) DependencyPairsProof [EQUIVALENT, 0 ms] 172.09/86.10 (32) QDP 172.09/86.10 (33) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (34) QDP 172.09/86.10 (35) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (36) QDP 172.09/86.10 (37) NonTerminationLoopProof [COMPLETE, 0 ms] 172.09/86.10 (38) NO 172.09/86.10 (39) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 172.09/86.10 (40) QTRS 172.09/86.10 (41) AAECC Innermost [EQUIVALENT, 16 ms] 172.09/86.10 (42) QTRS 172.09/86.10 (43) DependencyPairsProof [EQUIVALENT, 0 ms] 172.09/86.10 (44) QDP 172.09/86.10 (45) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (46) AND 172.09/86.10 (47) QDP 172.09/86.10 (48) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (49) QDP 172.09/86.10 (50) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (51) QDP 172.09/86.10 (52) QDPSizeChangeProof [EQUIVALENT, 0 ms] 172.09/86.10 (53) YES 172.09/86.10 (54) QDP 172.09/86.10 (55) UsableRulesProof [EQUIVALENT, 0 ms] 172.09/86.10 (56) QDP 172.09/86.10 (57) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (58) QDP 172.09/86.10 (59) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (60) QDP 172.09/86.10 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (62) QDP 172.09/86.10 (63) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (64) QDP 172.09/86.10 (65) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (66) QDP 172.09/86.10 (67) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (68) QDP 172.09/86.10 (69) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (70) QDP 172.09/86.10 (71) TransformationProof [EQUIVALENT, 0 ms] 172.09/86.10 (72) QDP 172.09/86.10 (73) QDPOrderProof [EQUIVALENT, 9 ms] 172.09/86.10 (74) QDP 172.09/86.10 (75) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (76) QDP 172.09/86.10 (77) QDPOrderProof [EQUIVALENT, 0 ms] 172.09/86.10 (78) QDP 172.09/86.10 (79) QDPOrderProof [EQUIVALENT, 93 ms] 172.09/86.10 (80) QDP 172.09/86.10 (81) MNOCProof [EQUIVALENT, 0 ms] 172.09/86.10 (82) QDP 172.09/86.10 (83) SplitQDPProof [EQUIVALENT, 0 ms] 172.09/86.10 (84) AND 172.09/86.10 (85) QDP 172.09/86.10 (86) SemLabProof [SOUND, 0 ms] 172.09/86.10 (87) QDP 172.09/86.10 (88) UsableRulesReductionPairsProof [EQUIVALENT, 8 ms] 172.09/86.10 (89) QDP 172.09/86.10 (90) MRRProof [EQUIVALENT, 0 ms] 172.09/86.10 (91) QDP 172.09/86.10 (92) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (93) QDP 172.09/86.10 (94) MRRProof [EQUIVALENT, 0 ms] 172.09/86.10 (95) QDP 172.09/86.10 (96) PisEmptyProof [SOUND, 0 ms] 172.09/86.10 (97) TRUE 172.09/86.10 (98) QDP 172.09/86.10 (99) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (100) QDP 172.09/86.10 (101) MNOCProof [EQUIVALENT, 0 ms] 172.09/86.10 (102) QDP 172.09/86.10 (103) SplitQDPProof [EQUIVALENT, 0 ms] 172.09/86.10 (104) AND 172.09/86.10 (105) QDP 172.09/86.10 (106) SemLabProof [SOUND, 0 ms] 172.09/86.10 (107) QDP 172.09/86.10 (108) MRRProof [EQUIVALENT, 0 ms] 172.09/86.10 (109) QDP 172.09/86.10 (110) DependencyGraphProof [EQUIVALENT, 0 ms] 172.09/86.10 (111) QDP 172.09/86.10 (112) PisEmptyProof [SOUND, 0 ms] 172.09/86.10 (113) TRUE 172.09/86.10 (114) QDP 172.09/86.10 (115) QReductionProof [EQUIVALENT, 0 ms] 172.09/86.10 (116) QDP 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (0) 172.09/86.10 Obligation: 172.09/86.10 Term rewrite system R: 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 a -> f(a) 172.09/86.10 f(f(x)) -> g(x) 172.09/86.10 g(g(x)) -> c 172.09/86.10 172.09/86.10 172.09/86.10 172.09/86.10 Outermost Strategy. 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 172.09/86.10 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (2) 172.09/86.10 Obligation: 172.09/86.10 Q restricted rewrite system: 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 top(go_up(x)) -> top(reduce(x)) 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (3) DependencyPairsProof (EQUIVALENT) 172.09/86.10 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (4) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 TOP(go_up(x)) -> REDUCE(x) 172.09/86.10 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 172.09/86.10 REDUCE(f(x_1)) -> REDEX_F(x_1) 172.09/86.10 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 172.09/86.10 REDUCE(g(x_1)) -> REDEX_G(x_1) 172.09/86.10 CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) 172.09/86.10 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 172.09/86.10 CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) 172.09/86.10 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 top(go_up(x)) -> top(reduce(x)) 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (5) DependencyGraphProof (EQUIVALENT) 172.09/86.10 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (6) 172.09/86.10 Complex Obligation (AND) 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (7) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 172.09/86.10 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 top(go_up(x)) -> top(reduce(x)) 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (8) UsableRulesProof (EQUIVALENT) 172.09/86.10 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. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (9) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 172.09/86.10 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (10) QReductionProof (EQUIVALENT) 172.09/86.10 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (11) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 172.09/86.10 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (12) UsableRulesReductionPairsProof (EQUIVALENT) 172.09/86.10 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. 172.09/86.10 172.09/86.10 The following dependency pairs can be deleted: 172.09/86.10 172.09/86.10 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 172.09/86.10 The following rules are removed from R: 172.09/86.10 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 Used ordering: POLO with Polynomial interpretation [POLO]: 172.09/86.10 172.09/86.10 POL(CHECK_F(x_1)) = x_1 172.09/86.10 POL(CHECK_G(x_1)) = x_1 172.09/86.10 POL(REDUCE(x_1)) = 2*x_1 172.09/86.10 POL(c) = 0 172.09/86.10 POL(f(x_1)) = 2*x_1 172.09/86.10 POL(g(x_1)) = 2*x_1 172.09/86.10 POL(redex_f(x_1)) = 2*x_1 172.09/86.10 POL(redex_g(x_1)) = 2*x_1 172.09/86.10 POL(result_f(x_1)) = x_1 172.09/86.10 POL(result_g(x_1)) = x_1 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (13) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 172.09/86.10 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 172.09/86.10 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (14) DependencyGraphProof (EQUIVALENT) 172.09/86.10 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (15) 172.09/86.10 TRUE 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (16) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 top(go_up(x)) -> top(reduce(x)) 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (17) UsableRulesProof (EQUIVALENT) 172.09/86.10 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. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (18) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (19) QReductionProof (EQUIVALENT) 172.09/86.10 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (20) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (21) TransformationProof (EQUIVALENT) 172.09/86.10 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 172.09/86.10 172.09/86.10 (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) 172.09/86.10 (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))) 172.09/86.10 (TOP(go_up(a)) -> TOP(go_up(f(a))),TOP(go_up(a)) -> TOP(go_up(f(a)))) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (22) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 172.09/86.10 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 172.09/86.10 TOP(go_up(a)) -> TOP(go_up(f(a))) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (23) QDPOrderProof (EQUIVALENT) 172.09/86.10 We use the reduction pair processor [LPAR04,JAR06]. 172.09/86.10 172.09/86.10 172.09/86.10 The following pairs can be oriented strictly and are deleted. 172.09/86.10 172.09/86.10 TOP(go_up(a)) -> TOP(go_up(f(a))) 172.09/86.10 The remaining pairs can at least be oriented weakly. 172.09/86.10 Used ordering: Polynomial interpretation [POLO]: 172.09/86.10 172.09/86.10 POL(TOP(x_1)) = x_1 172.09/86.10 POL(a) = 1 172.09/86.10 POL(c) = 0 172.09/86.10 POL(check_f(x_1)) = x_1 172.09/86.10 POL(check_g(x_1)) = x_1 172.09/86.10 POL(f(x_1)) = 0 172.09/86.10 POL(g(x_1)) = 0 172.09/86.10 POL(go_up(x_1)) = x_1 172.09/86.10 POL(in_f_1(x_1)) = 0 172.09/86.10 POL(in_g_1(x_1)) = 0 172.09/86.10 POL(redex_f(x_1)) = 0 172.09/86.10 POL(redex_g(x_1)) = 0 172.09/86.10 POL(reduce(x_1)) = 0 172.09/86.10 POL(result_f(x_1)) = x_1 172.09/86.10 POL(result_g(x_1)) = x_1 172.09/86.10 172.09/86.10 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 172.09/86.10 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (24) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 172.09/86.10 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (25) UsableRulesProof (EQUIVALENT) 172.09/86.10 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. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (26) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (27) QReductionProof (EQUIVALENT) 172.09/86.10 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 172.09/86.10 172.09/86.10 top(go_up(x0)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (28) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(go_up(x)) -> TOP(reduce(x)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 reduce(f(x_1)) -> check_f(redex_f(x_1)) 172.09/86.10 reduce(g(x_1)) -> check_g(redex_g(x_1)) 172.09/86.10 reduce(a) -> go_up(f(a)) 172.09/86.10 redex_g(g(x)) -> result_g(c) 172.09/86.10 check_g(result_g(x)) -> go_up(x) 172.09/86.10 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 172.09/86.10 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 172.09/86.10 redex_f(f(x)) -> result_f(g(x)) 172.09/86.10 check_f(result_f(x)) -> go_up(x) 172.09/86.10 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 172.09/86.10 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 reduce(f(x0)) 172.09/86.10 reduce(g(x0)) 172.09/86.10 reduce(a) 172.09/86.10 redex_f(f(x0)) 172.09/86.10 redex_g(g(x0)) 172.09/86.10 check_f(result_f(x0)) 172.09/86.10 check_g(result_g(x0)) 172.09/86.10 check_f(redex_f(x0)) 172.09/86.10 check_g(redex_g(x0)) 172.09/86.10 in_f_1(go_up(x0)) 172.09/86.10 in_g_1(go_up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (29) Trivial-Transformation (SOUND) 172.09/86.10 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (30) 172.09/86.10 Obligation: 172.09/86.10 Q restricted rewrite system: 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 a -> f(a) 172.09/86.10 f(f(x)) -> g(x) 172.09/86.10 g(g(x)) -> c 172.09/86.10 172.09/86.10 Q is empty. 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (31) DependencyPairsProof (EQUIVALENT) 172.09/86.10 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (32) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 A -> F(a) 172.09/86.10 A -> A 172.09/86.10 F(f(x)) -> G(x) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 a -> f(a) 172.09/86.10 f(f(x)) -> g(x) 172.09/86.10 g(g(x)) -> c 172.09/86.10 172.09/86.10 Q is empty. 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (33) DependencyGraphProof (EQUIVALENT) 172.09/86.10 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (34) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 A -> A 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 a -> f(a) 172.09/86.10 f(f(x)) -> g(x) 172.09/86.10 g(g(x)) -> c 172.09/86.10 172.09/86.10 Q is empty. 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (35) UsableRulesProof (EQUIVALENT) 172.09/86.10 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (36) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 A -> A 172.09/86.10 172.09/86.10 R is empty. 172.09/86.10 Q is empty. 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (37) NonTerminationLoopProof (COMPLETE) 172.09/86.10 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 172.09/86.10 Found a loop by semiunifying a rule from P directly. 172.09/86.10 172.09/86.10 s = A evaluates to t =A 172.09/86.10 172.09/86.10 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 172.09/86.10 * Matcher: [ ] 172.09/86.10 * Semiunifier: [ ] 172.09/86.10 172.09/86.10 -------------------------------------------------------------------------------- 172.09/86.10 Rewriting sequence 172.09/86.10 172.09/86.10 The DP semiunifies directly so there is only one rewrite step from A to A. 172.09/86.10 172.09/86.10 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (38) 172.09/86.10 NO 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (39) Raffelsieper-Zantema-Transformation (SOUND) 172.09/86.10 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (40) 172.09/86.10 Obligation: 172.09/86.10 Q restricted rewrite system: 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 down(a) -> up(f(a)) 172.09/86.10 down(f(f(x))) -> up(g(x)) 172.09/86.10 down(g(g(x))) -> up(c) 172.09/86.10 top(up(x)) -> top(down(x)) 172.09/86.10 down(f(a)) -> f_flat(down(a)) 172.09/86.10 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.10 down(f(c)) -> f_flat(down(c)) 172.09/86.10 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.10 down(g(a)) -> g_flat(down(a)) 172.09/86.10 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.10 down(g(c)) -> g_flat(down(c)) 172.09/86.10 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.10 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.10 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.10 172.09/86.10 Q is empty. 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (41) AAECC Innermost (EQUIVALENT) 172.09/86.10 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 172.09/86.10 down(f(a)) -> f_flat(down(a)) 172.09/86.10 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.10 down(f(c)) -> f_flat(down(c)) 172.09/86.10 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.10 down(g(a)) -> g_flat(down(a)) 172.09/86.10 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.10 down(g(c)) -> g_flat(down(c)) 172.09/86.10 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.10 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.10 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.10 down(a) -> up(f(a)) 172.09/86.10 down(f(f(x))) -> up(g(x)) 172.09/86.10 down(g(g(x))) -> up(c) 172.09/86.10 172.09/86.10 The TRS R 2 is 172.09/86.10 top(up(x)) -> top(down(x)) 172.09/86.10 172.09/86.10 The signature Sigma is {top_1} 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (42) 172.09/86.10 Obligation: 172.09/86.10 Q restricted rewrite system: 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 down(a) -> up(f(a)) 172.09/86.10 down(f(f(x))) -> up(g(x)) 172.09/86.10 down(g(g(x))) -> up(c) 172.09/86.10 top(up(x)) -> top(down(x)) 172.09/86.10 down(f(a)) -> f_flat(down(a)) 172.09/86.10 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.10 down(f(c)) -> f_flat(down(c)) 172.09/86.10 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.10 down(g(a)) -> g_flat(down(a)) 172.09/86.10 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.10 down(g(c)) -> g_flat(down(c)) 172.09/86.10 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.10 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.10 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 down(a) 172.09/86.10 down(f(f(x0))) 172.09/86.10 down(g(g(x0))) 172.09/86.10 top(up(x0)) 172.09/86.10 down(f(a)) 172.09/86.10 down(f(g(x0))) 172.09/86.10 down(f(c)) 172.09/86.10 down(f(fresh_constant)) 172.09/86.10 down(g(a)) 172.09/86.10 down(g(f(x0))) 172.09/86.10 down(g(c)) 172.09/86.10 down(g(fresh_constant)) 172.09/86.10 f_flat(up(x0)) 172.09/86.10 g_flat(up(x0)) 172.09/86.10 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (43) DependencyPairsProof (EQUIVALENT) 172.09/86.10 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (44) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 TOP(up(x)) -> TOP(down(x)) 172.09/86.10 TOP(up(x)) -> DOWN(x) 172.09/86.10 DOWN(f(a)) -> F_FLAT(down(a)) 172.09/86.10 DOWN(f(a)) -> DOWN(a) 172.09/86.10 DOWN(f(g(y4))) -> F_FLAT(down(g(y4))) 172.09/86.10 DOWN(f(g(y4))) -> DOWN(g(y4)) 172.09/86.10 DOWN(f(c)) -> F_FLAT(down(c)) 172.09/86.10 DOWN(f(c)) -> DOWN(c) 172.09/86.10 DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) 172.09/86.10 DOWN(f(fresh_constant)) -> DOWN(fresh_constant) 172.09/86.10 DOWN(g(a)) -> G_FLAT(down(a)) 172.09/86.10 DOWN(g(a)) -> DOWN(a) 172.09/86.10 DOWN(g(f(y6))) -> G_FLAT(down(f(y6))) 172.09/86.10 DOWN(g(f(y6))) -> DOWN(f(y6)) 172.09/86.10 DOWN(g(c)) -> G_FLAT(down(c)) 172.09/86.10 DOWN(g(c)) -> DOWN(c) 172.09/86.10 DOWN(g(fresh_constant)) -> G_FLAT(down(fresh_constant)) 172.09/86.10 DOWN(g(fresh_constant)) -> DOWN(fresh_constant) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 down(a) -> up(f(a)) 172.09/86.10 down(f(f(x))) -> up(g(x)) 172.09/86.10 down(g(g(x))) -> up(c) 172.09/86.10 top(up(x)) -> top(down(x)) 172.09/86.10 down(f(a)) -> f_flat(down(a)) 172.09/86.10 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.10 down(f(c)) -> f_flat(down(c)) 172.09/86.10 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.10 down(g(a)) -> g_flat(down(a)) 172.09/86.10 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.10 down(g(c)) -> g_flat(down(c)) 172.09/86.10 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.10 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.10 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 down(a) 172.09/86.10 down(f(f(x0))) 172.09/86.10 down(g(g(x0))) 172.09/86.10 top(up(x0)) 172.09/86.10 down(f(a)) 172.09/86.10 down(f(g(x0))) 172.09/86.10 down(f(c)) 172.09/86.10 down(f(fresh_constant)) 172.09/86.10 down(g(a)) 172.09/86.10 down(g(f(x0))) 172.09/86.10 down(g(c)) 172.09/86.10 down(g(fresh_constant)) 172.09/86.10 f_flat(up(x0)) 172.09/86.10 g_flat(up(x0)) 172.09/86.10 172.09/86.10 We have to consider all minimal (P,Q,R)-chains. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (45) DependencyGraphProof (EQUIVALENT) 172.09/86.10 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 15 less nodes. 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (46) 172.09/86.10 Complex Obligation (AND) 172.09/86.10 172.09/86.10 ---------------------------------------- 172.09/86.10 172.09/86.10 (47) 172.09/86.10 Obligation: 172.09/86.10 Q DP problem: 172.09/86.10 The TRS P consists of the following rules: 172.09/86.10 172.09/86.10 DOWN(f(g(y4))) -> DOWN(g(y4)) 172.09/86.10 DOWN(g(f(y6))) -> DOWN(f(y6)) 172.09/86.10 172.09/86.10 The TRS R consists of the following rules: 172.09/86.10 172.09/86.10 down(a) -> up(f(a)) 172.09/86.10 down(f(f(x))) -> up(g(x)) 172.09/86.10 down(g(g(x))) -> up(c) 172.09/86.10 top(up(x)) -> top(down(x)) 172.09/86.10 down(f(a)) -> f_flat(down(a)) 172.09/86.10 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.10 down(f(c)) -> f_flat(down(c)) 172.09/86.10 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.10 down(g(a)) -> g_flat(down(a)) 172.09/86.10 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.10 down(g(c)) -> g_flat(down(c)) 172.09/86.10 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.10 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.10 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.10 172.09/86.10 The set Q consists of the following terms: 172.09/86.10 172.09/86.10 down(a) 172.09/86.10 down(f(f(x0))) 172.09/86.10 down(g(g(x0))) 172.09/86.10 top(up(x0)) 172.09/86.10 down(f(a)) 172.09/86.10 down(f(g(x0))) 172.09/86.10 down(f(c)) 172.09/86.10 down(f(fresh_constant)) 172.09/86.10 down(g(a)) 172.09/86.10 down(g(f(x0))) 172.09/86.10 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (48) UsableRulesProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (49) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 DOWN(f(g(y4))) -> DOWN(g(y4)) 172.09/86.11 DOWN(g(f(y6))) -> DOWN(f(y6)) 172.09/86.11 172.09/86.11 R is empty. 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 top(up(x0)) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (50) QReductionProof (EQUIVALENT) 172.09/86.11 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 top(up(x0)) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (51) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 DOWN(f(g(y4))) -> DOWN(g(y4)) 172.09/86.11 DOWN(g(f(y6))) -> DOWN(f(y6)) 172.09/86.11 172.09/86.11 R is empty. 172.09/86.11 Q is empty. 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (52) QDPSizeChangeProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 172.09/86.11 From the DPs we obtained the following set of size-change graphs: 172.09/86.11 *DOWN(g(f(y6))) -> DOWN(f(y6)) 172.09/86.11 The graph contains the following edges 1 > 1 172.09/86.11 172.09/86.11 172.09/86.11 *DOWN(f(g(y4))) -> DOWN(g(y4)) 172.09/86.11 The graph contains the following edges 1 > 1 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (53) 172.09/86.11 YES 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (54) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(x)) -> TOP(down(x)) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 top(up(x)) -> top(down(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 top(up(x0)) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (55) UsableRulesProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (56) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(x)) -> TOP(down(x)) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 top(up(x0)) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (57) QReductionProof (EQUIVALENT) 172.09/86.11 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 172.09/86.11 172.09/86.11 top(up(x0)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (58) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(x)) -> TOP(down(x)) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (59) TransformationProof (EQUIVALENT) 172.09/86.11 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(a)) -> TOP(up(f(a))),TOP(up(a)) -> TOP(up(f(a)))) 172.09/86.11 (TOP(up(f(f(x0)))) -> TOP(up(g(x0))),TOP(up(f(f(x0)))) -> TOP(up(g(x0)))) 172.09/86.11 (TOP(up(g(g(x0)))) -> TOP(up(c)),TOP(up(g(g(x0)))) -> TOP(up(c))) 172.09/86.11 (TOP(up(f(a))) -> TOP(f_flat(down(a))),TOP(up(f(a))) -> TOP(f_flat(down(a)))) 172.09/86.11 (TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))),TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0))))) 172.09/86.11 (TOP(up(f(c))) -> TOP(f_flat(down(c))),TOP(up(f(c))) -> TOP(f_flat(down(c)))) 172.09/86.11 (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))) 172.09/86.11 (TOP(up(g(a))) -> TOP(g_flat(down(a))),TOP(up(g(a))) -> TOP(g_flat(down(a)))) 172.09/86.11 (TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))),TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0))))) 172.09/86.11 (TOP(up(g(c))) -> TOP(g_flat(down(c))),TOP(up(g(c))) -> TOP(g_flat(down(c)))) 172.09/86.11 (TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))),TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant)))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (60) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(a)) -> TOP(up(f(a))) 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(g(x0)))) -> TOP(up(c)) 172.09/86.11 TOP(up(f(a))) -> TOP(f_flat(down(a))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(f(c))) -> TOP(f_flat(down(c))) 172.09/86.11 TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))) 172.09/86.11 TOP(up(g(a))) -> TOP(g_flat(down(a))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(g(c))) -> TOP(g_flat(down(c))) 172.09/86.11 TOP(up(g(fresh_constant))) -> TOP(g_flat(down(fresh_constant))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (61) DependencyGraphProof (EQUIVALENT) 172.09/86.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (62) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(g(a))) -> TOP(g_flat(down(a))) 172.09/86.11 TOP(up(f(a))) -> TOP(f_flat(down(a))) 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (63) TransformationProof (EQUIVALENT) 172.09/86.11 By rewriting [LPAR04] the rule TOP(up(g(a))) -> TOP(g_flat(down(a))) at position [0,0] we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(g(a))) -> TOP(g_flat(up(f(a)))),TOP(up(g(a))) -> TOP(g_flat(up(f(a))))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (64) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(a))) -> TOP(f_flat(down(a))) 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (65) TransformationProof (EQUIVALENT) 172.09/86.11 By rewriting [LPAR04] the rule TOP(up(f(a))) -> TOP(f_flat(down(a))) at position [0,0] we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(f(a))) -> TOP(f_flat(up(f(a)))),TOP(up(f(a))) -> TOP(f_flat(up(f(a))))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (66) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) 172.09/86.11 TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (67) TransformationProof (EQUIVALENT) 172.09/86.11 By rewriting [LPAR04] the rule TOP(up(g(a))) -> TOP(g_flat(up(f(a)))) at position [0] we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(g(a))) -> TOP(up(g(f(a)))),TOP(up(g(a))) -> TOP(up(g(f(a))))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (68) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (69) TransformationProof (EQUIVALENT) 172.09/86.11 By rewriting [LPAR04] the rule TOP(up(f(a))) -> TOP(f_flat(up(f(a)))) at position [0] we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(f(a))) -> TOP(up(f(f(a)))),TOP(up(f(a))) -> TOP(up(f(f(a))))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (70) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(f(x0)))) -> TOP(up(g(x0))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 TOP(up(f(a))) -> TOP(up(f(f(a)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (71) TransformationProof (EQUIVALENT) 172.09/86.11 By forward instantiating [JAR06] the rule TOP(up(f(f(x0)))) -> TOP(up(g(x0))) we obtained the following new rules [LPAR04]: 172.09/86.11 172.09/86.11 (TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))),TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0))))) 172.09/86.11 (TOP(up(f(f(a)))) -> TOP(up(g(a))),TOP(up(f(f(a)))) -> TOP(up(g(a)))) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (72) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 TOP(up(f(a))) -> TOP(up(f(f(a)))) 172.09/86.11 TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) 172.09/86.11 TOP(up(f(f(a)))) -> TOP(up(g(a))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (73) QDPOrderProof (EQUIVALENT) 172.09/86.11 We use the reduction pair processor [LPAR04,JAR06]. 172.09/86.11 172.09/86.11 172.09/86.11 The following pairs can be oriented strictly and are deleted. 172.09/86.11 172.09/86.11 TOP(up(f(f(a)))) -> TOP(up(g(a))) 172.09/86.11 The remaining pairs can at least be oriented weakly. 172.09/86.11 Used ordering: Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP(x_1)) = x_1 172.09/86.11 POL(a) = 1 172.09/86.11 POL(c) = 0 172.09/86.11 POL(down(x_1)) = 0 172.09/86.11 POL(f(x_1)) = x_1 172.09/86.11 POL(f_flat(x_1)) = x_1 172.09/86.11 POL(fresh_constant) = 0 172.09/86.11 POL(g(x_1)) = 0 172.09/86.11 POL(g_flat(x_1)) = 0 172.09/86.11 POL(up(x_1)) = x_1 172.09/86.11 172.09/86.11 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 172.09/86.11 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (74) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 TOP(up(f(a))) -> TOP(up(f(f(a)))) 172.09/86.11 TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (75) DependencyGraphProof (EQUIVALENT) 172.09/86.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (76) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (77) QDPOrderProof (EQUIVALENT) 172.09/86.11 We use the reduction pair processor [LPAR04,JAR06]. 172.09/86.11 172.09/86.11 172.09/86.11 The following pairs can be oriented strictly and are deleted. 172.09/86.11 172.09/86.11 TOP(up(f(f(f(y_0))))) -> TOP(up(g(f(y_0)))) 172.09/86.11 The remaining pairs can at least be oriented weakly. 172.09/86.11 Used ordering: Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP(x_1)) = x_1 172.09/86.11 POL(a) = 0 172.09/86.11 POL(c) = 0 172.09/86.11 POL(down(x_1)) = 0 172.09/86.11 POL(f(x_1)) = 1 172.09/86.11 POL(f_flat(x_1)) = 1 172.09/86.11 POL(fresh_constant) = 0 172.09/86.11 POL(g(x_1)) = 0 172.09/86.11 POL(g_flat(x_1)) = 0 172.09/86.11 POL(up(x_1)) = x_1 172.09/86.11 172.09/86.11 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 172.09/86.11 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (78) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (79) QDPOrderProof (EQUIVALENT) 172.09/86.11 We use the reduction pair processor [LPAR04,JAR06]. 172.09/86.11 172.09/86.11 172.09/86.11 The following pairs can be oriented strictly and are deleted. 172.09/86.11 172.09/86.11 TOP(up(g(a))) -> TOP(up(g(f(a)))) 172.09/86.11 The remaining pairs can at least be oriented weakly. 172.09/86.11 Used ordering: Matrix interpretation [MATRO]: 172.09/86.11 172.09/86.11 Non-tuple symbols: 172.09/86.11 <<< 172.09/86.11 M( a ) = [[1], [0]] 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( c ) = [[0], [0]] 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( down_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( f_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( fresh_constant ) = [[0], [0]] 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( up_1(x_1) ) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( f_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( g_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 <<< 172.09/86.11 M( g_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 Tuple symbols: 172.09/86.11 <<< 172.09/86.11 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 172.09/86.11 >>> 172.09/86.11 172.09/86.11 172.09/86.11 172.09/86.11 Matrix type: 172.09/86.11 172.09/86.11 We used a basic matrix type which is not further parametrizeable. 172.09/86.11 172.09/86.11 172.09/86.11 172.09/86.11 172.09/86.11 172.09/86.11 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 172.09/86.11 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 172.09/86.11 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (80) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (81) MNOCProof (EQUIVALENT) 172.09/86.11 We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (82) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 Q is empty. 172.09/86.11 We have to consider all (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (83) SplitQDPProof (EQUIVALENT) 172.09/86.11 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (84) 172.09/86.11 Complex Obligation (AND) 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (85) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(g(fresh_constant)) -> g_flat(down(fresh_constant)) 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (86) SemLabProof (SOUND) 172.09/86.11 We found the following model for the rules of the TRSs R and P. 172.09/86.11 Interpretation over the domain with elements from 0 to 1. 172.09/86.11 a: 0 172.09/86.11 c: 0 172.09/86.11 down: 0 172.09/86.11 f: 0 172.09/86.11 fresh_constant: 1 172.09/86.11 up: 0 172.09/86.11 f_flat: 0 172.09/86.11 TOP: 0 172.09/86.11 g_flat: 0 172.09/86.11 g: 0 172.09/86.11 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (87) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(g.1(x))) -> up.0(c.) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.0(c.)) -> f_flat.0(down.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.0(c.)) -> g_flat.0(down.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (88) UsableRulesReductionPairsProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 172.09/86.11 No dependency pairs are removed. 172.09/86.11 172.09/86.11 The following rules are removed from R: 172.09/86.11 172.09/86.11 g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) 172.09/86.11 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 172.09/86.11 Used ordering: POLO with Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP.0(x_1)) = x_1 172.09/86.11 POL(a.) = 0 172.09/86.11 POL(c.) = 0 172.09/86.11 POL(down.0(x_1)) = 1 + x_1 172.09/86.11 POL(down.1(x_1)) = 1 + x_1 172.09/86.11 POL(f.0(x_1)) = x_1 172.09/86.11 POL(f.1(x_1)) = x_1 172.09/86.11 POL(f_flat.0(x_1)) = x_1 172.09/86.11 POL(fresh_constant.) = 0 172.09/86.11 POL(g.0(x_1)) = x_1 172.09/86.11 POL(g.1(x_1)) = x_1 172.09/86.11 POL(g_flat.0(x_1)) = x_1 172.09/86.11 POL(up.0(x_1)) = 1 + x_1 172.09/86.11 POL(up.1(x_1)) = 1 + x_1 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (89) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.0(c.)) -> f_flat.0(down.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(g.1(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.0(c.)) -> g_flat.0(down.0(c.)) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (90) MRRProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 172.09/86.11 172.09/86.11 Strictly oriented rules of the TRS R: 172.09/86.11 172.09/86.11 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 172.09/86.11 down.0(g.1(fresh_constant.)) -> g_flat.0(down.1(fresh_constant.)) 172.09/86.11 down.0(g.0(g.1(x))) -> up.0(c.) 172.09/86.11 172.09/86.11 Used ordering: Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP.0(x_1)) = x_1 172.09/86.11 POL(a.) = 0 172.09/86.11 POL(c.) = 0 172.09/86.11 POL(down.0(x_1)) = x_1 172.09/86.11 POL(down.1(x_1)) = x_1 172.09/86.11 POL(f.0(x_1)) = x_1 172.09/86.11 POL(f.1(x_1)) = 1 + x_1 172.09/86.11 POL(f_flat.0(x_1)) = x_1 172.09/86.11 POL(fresh_constant.) = 0 172.09/86.11 POL(g.0(x_1)) = x_1 172.09/86.11 POL(g.1(x_1)) = 1 + x_1 172.09/86.11 POL(g_flat.0(x_1)) = x_1 172.09/86.11 POL(up.0(x_1)) = x_1 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (91) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.0(c.)) -> f_flat.0(down.0(c.)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.0(c.)) -> g_flat.0(down.0(c.)) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (92) DependencyGraphProof (EQUIVALENT) 172.09/86.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (93) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.0(c.)) -> f_flat.0(down.0(c.)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.0(c.)) -> g_flat.0(down.0(c.)) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (94) MRRProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 172.09/86.11 172.09/86.11 Strictly oriented rules of the TRS R: 172.09/86.11 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 172.09/86.11 Used ordering: Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP.0(x_1)) = x_1 172.09/86.11 POL(a.) = 0 172.09/86.11 POL(c.) = 0 172.09/86.11 POL(down.0(x_1)) = 1 + x_1 172.09/86.11 POL(f.0(x_1)) = x_1 172.09/86.11 POL(f.1(x_1)) = 1 + x_1 172.09/86.11 POL(f_flat.0(x_1)) = x_1 172.09/86.11 POL(g.0(x_1)) = x_1 172.09/86.11 POL(g.1(x_1)) = x_1 172.09/86.11 POL(g_flat.0(x_1)) = x_1 172.09/86.11 POL(up.0(x_1)) = 1 + x_1 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (95) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.0(c.)) -> f_flat.0(down.0(c.)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.0(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.0(c.)) -> g_flat.0(down.0(c.)) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.0(c.)) 172.09/86.11 down.0(f.1(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.0(c.)) 172.09/86.11 down.0(g.1(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (96) PisEmptyProof (SOUND) 172.09/86.11 The TRS P is empty. Hence, there is no (P,Q,R) chain. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (97) 172.09/86.11 TRUE 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (98) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (99) QReductionProof (EQUIVALENT) 172.09/86.11 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 172.09/86.11 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (100) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (101) MNOCProof (EQUIVALENT) 172.09/86.11 We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (102) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 Q is empty. 172.09/86.11 We have to consider all (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (103) SplitQDPProof (EQUIVALENT) 172.09/86.11 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (104) 172.09/86.11 Complex Obligation (AND) 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (105) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 down(f(c)) -> f_flat(down(c)) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(g(c)) -> g_flat(down(c)) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (106) SemLabProof (SOUND) 172.09/86.11 We found the following model for the rules of the TRSs R and P. 172.09/86.11 Interpretation over the domain with elements from 0 to 1. 172.09/86.11 a: 0 172.09/86.11 c: 1 172.09/86.11 down: 0 172.09/86.11 f: 0 172.09/86.11 fresh_constant: 0 172.09/86.11 up: 0 172.09/86.11 f_flat: 0 172.09/86.11 TOP: 0 172.09/86.11 g_flat: 0 172.09/86.11 g: 0 172.09/86.11 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (107) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 down.0(f.1(c.)) -> f_flat.0(down.1(c.)) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(g.1(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(g.1(c.)) -> g_flat.0(down.1(c.)) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.1(c.)) 172.09/86.11 down.0(f.0(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.1(c.)) 172.09/86.11 down.0(g.0(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (108) MRRProof (EQUIVALENT) 172.09/86.11 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. 172.09/86.11 172.09/86.11 172.09/86.11 Strictly oriented rules of the TRS R: 172.09/86.11 172.09/86.11 down.0(f.1(c.)) -> f_flat.0(down.1(c.)) 172.09/86.11 down.0(g.1(c.)) -> g_flat.0(down.1(c.)) 172.09/86.11 172.09/86.11 Used ordering: Polynomial interpretation [POLO]: 172.09/86.11 172.09/86.11 POL(TOP.0(x_1)) = x_1 172.09/86.11 POL(a.) = 0 172.09/86.11 POL(c.) = 0 172.09/86.11 POL(down.0(x_1)) = 1 + x_1 172.09/86.11 POL(down.1(x_1)) = x_1 172.09/86.11 POL(f.0(x_1)) = x_1 172.09/86.11 POL(f.1(x_1)) = x_1 172.09/86.11 POL(f_flat.0(x_1)) = x_1 172.09/86.11 POL(g.0(x_1)) = x_1 172.09/86.11 POL(g.1(x_1)) = x_1 172.09/86.11 POL(g_flat.0(x_1)) = x_1 172.09/86.11 POL(up.0(x_1)) = 1 + x_1 172.09/86.11 POL(up.1(x_1)) = 1 + x_1 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (109) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(f.0(g.1(x0)))) -> TOP.0(f_flat.0(down.0(g.1(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.1(x0)))) -> TOP.0(g_flat.0(down.0(f.1(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(g.1(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.1(c.)) 172.09/86.11 down.0(f.0(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.1(c.)) 172.09/86.11 down.0(g.0(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (110) DependencyGraphProof (EQUIVALENT) 172.09/86.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (111) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP.0(up.0(f.0(g.0(x0)))) -> TOP.0(f_flat.0(down.0(g.0(x0)))) 172.09/86.11 TOP.0(up.0(g.0(f.0(x0)))) -> TOP.0(g_flat.0(down.0(f.0(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat.0(up.0(x_1)) -> up.0(g.0(x_1)) 172.09/86.11 g_flat.0(up.1(x_1)) -> up.0(g.1(x_1)) 172.09/86.11 down.0(f.0(f.0(x))) -> up.0(g.0(x)) 172.09/86.11 down.0(f.0(f.1(x))) -> up.0(g.1(x)) 172.09/86.11 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 172.09/86.11 down.0(f.0(g.0(y4))) -> f_flat.0(down.0(g.0(y4))) 172.09/86.11 down.0(f.0(g.1(y4))) -> f_flat.0(down.0(g.1(y4))) 172.09/86.11 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 172.09/86.11 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 172.09/86.11 down.0(g.0(g.0(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(g.1(x))) -> up.1(c.) 172.09/86.11 down.0(g.0(a.)) -> g_flat.0(down.0(a.)) 172.09/86.11 down.0(g.0(f.0(y6))) -> g_flat.0(down.0(f.0(y6))) 172.09/86.11 down.0(g.0(f.1(y6))) -> g_flat.0(down.0(f.1(y6))) 172.09/86.11 down.0(a.) -> up.0(f.0(a.)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down.0(a.) 172.09/86.11 down.0(f.0(f.0(x0))) 172.09/86.11 down.0(f.0(f.1(x0))) 172.09/86.11 down.0(g.0(g.0(x0))) 172.09/86.11 down.0(g.0(g.1(x0))) 172.09/86.11 down.0(f.0(a.)) 172.09/86.11 down.0(f.0(g.0(x0))) 172.09/86.11 down.0(f.0(g.1(x0))) 172.09/86.11 down.0(f.1(c.)) 172.09/86.11 down.0(f.0(fresh_constant.)) 172.09/86.11 down.0(g.0(a.)) 172.09/86.11 down.0(g.0(f.0(x0))) 172.09/86.11 down.0(g.0(f.1(x0))) 172.09/86.11 down.0(g.1(c.)) 172.09/86.11 down.0(g.0(fresh_constant.)) 172.09/86.11 f_flat.0(up.0(x0)) 172.09/86.11 f_flat.0(up.1(x0)) 172.09/86.11 g_flat.0(up.0(x0)) 172.09/86.11 g_flat.0(up.1(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (112) PisEmptyProof (SOUND) 172.09/86.11 The TRS P is empty. Hence, there is no (P,Q,R) chain. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (113) 172.09/86.11 TRUE 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (114) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.11 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.11 172.09/86.11 The TRS R consists of the following rules: 172.09/86.11 172.09/86.11 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.11 down(f(f(x))) -> up(g(x)) 172.09/86.11 down(f(a)) -> f_flat(down(a)) 172.09/86.11 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.11 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.11 down(g(g(x))) -> up(c) 172.09/86.11 down(g(a)) -> g_flat(down(a)) 172.09/86.11 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.11 down(a) -> up(f(a)) 172.09/86.11 172.09/86.11 The set Q consists of the following terms: 172.09/86.11 172.09/86.11 down(a) 172.09/86.11 down(f(f(x0))) 172.09/86.11 down(g(g(x0))) 172.09/86.11 down(f(a)) 172.09/86.11 down(f(g(x0))) 172.09/86.11 down(f(c)) 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(a)) 172.09/86.11 down(g(f(x0))) 172.09/86.11 down(g(c)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 f_flat(up(x0)) 172.09/86.11 g_flat(up(x0)) 172.09/86.11 172.09/86.11 We have to consider all minimal (P,Q,R)-chains. 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (115) QReductionProof (EQUIVALENT) 172.09/86.11 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 172.09/86.11 172.09/86.11 down(f(fresh_constant)) 172.09/86.11 down(g(fresh_constant)) 172.09/86.11 172.09/86.11 172.09/86.11 ---------------------------------------- 172.09/86.11 172.09/86.11 (116) 172.09/86.11 Obligation: 172.09/86.11 Q DP problem: 172.09/86.11 The TRS P consists of the following rules: 172.09/86.11 172.09/86.11 TOP(up(f(g(x0)))) -> TOP(f_flat(down(g(x0)))) 172.09/86.12 TOP(up(g(f(x0)))) -> TOP(g_flat(down(f(x0)))) 172.09/86.12 172.09/86.12 The TRS R consists of the following rules: 172.09/86.12 172.09/86.12 g_flat(up(x_1)) -> up(g(x_1)) 172.09/86.12 down(f(f(x))) -> up(g(x)) 172.09/86.12 down(f(a)) -> f_flat(down(a)) 172.09/86.12 down(f(g(y4))) -> f_flat(down(g(y4))) 172.09/86.12 f_flat(up(x_1)) -> up(f(x_1)) 172.09/86.12 down(g(g(x))) -> up(c) 172.09/86.12 down(g(a)) -> g_flat(down(a)) 172.09/86.12 down(g(f(y6))) -> g_flat(down(f(y6))) 172.09/86.12 down(a) -> up(f(a)) 172.09/86.12 172.09/86.12 The set Q consists of the following terms: 172.09/86.12 172.09/86.12 down(a) 172.09/86.12 down(f(f(x0))) 172.09/86.12 down(g(g(x0))) 172.09/86.12 down(f(a)) 172.09/86.12 down(f(g(x0))) 172.09/86.12 down(f(c)) 172.09/86.12 down(g(a)) 172.09/86.12 down(g(f(x0))) 172.09/86.12 down(g(c)) 172.09/86.12 f_flat(up(x0)) 172.09/86.12 g_flat(up(x0)) 172.09/86.12 172.09/86.12 We have to consider all (P,Q,R)-chains. 172.42/86.19 EOF