249.23/132.35 MAYBE 249.23/132.36 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 249.23/132.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 249.23/132.36 249.23/132.36 249.23/132.36 Outermost Termination of the given OTRS could not be shown: 249.23/132.36 249.23/132.36 (0) OTRS 249.23/132.36 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 249.23/132.36 (2) QTRS 249.23/132.36 (3) QTRSRRRProof [EQUIVALENT, 63 ms] 249.23/132.36 (4) QTRS 249.23/132.36 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 249.23/132.36 (6) QDP 249.23/132.36 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (8) AND 249.23/132.36 (9) QDP 249.23/132.36 (10) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (11) QDP 249.23/132.36 (12) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (13) QDP 249.23/132.36 (14) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 249.23/132.36 (15) QDP 249.23/132.36 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (17) TRUE 249.23/132.36 (18) QDP 249.23/132.36 (19) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (20) QDP 249.23/132.36 (21) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (22) QDP 249.23/132.36 (23) TransformationProof [SOUND, 0 ms] 249.23/132.36 (24) QDP 249.23/132.36 (25) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (26) QDP 249.23/132.36 (27) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (28) QDP 249.23/132.36 (29) QDPOrderProof [EQUIVALENT, 9 ms] 249.23/132.36 (30) QDP 249.23/132.36 (31) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (32) QDP 249.23/132.36 (33) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (34) QDP 249.23/132.36 (35) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (36) QDP 249.23/132.36 (37) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (38) QDP 249.23/132.36 (39) Trivial-Transformation [SOUND, 0 ms] 249.23/132.36 (40) QTRS 249.23/132.36 (41) QTRSRRRProof [EQUIVALENT, 33 ms] 249.23/132.36 (42) QTRS 249.23/132.36 (43) DependencyPairsProof [EQUIVALENT, 0 ms] 249.23/132.36 (44) QDP 249.23/132.36 (45) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (46) QDP 249.23/132.36 (47) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (48) QDP 249.23/132.36 (49) NonTerminationLoopProof [COMPLETE, 0 ms] 249.23/132.36 (50) NO 249.23/132.36 (51) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 249.23/132.36 (52) QTRS 249.23/132.36 (53) QTRSRRRProof [EQUIVALENT, 24 ms] 249.23/132.36 (54) QTRS 249.23/132.36 (55) QTRSRRRProof [EQUIVALENT, 3 ms] 249.23/132.36 (56) QTRS 249.23/132.36 (57) AAECC Innermost [EQUIVALENT, 0 ms] 249.23/132.36 (58) QTRS 249.23/132.36 (59) DependencyPairsProof [EQUIVALENT, 14 ms] 249.23/132.36 (60) QDP 249.23/132.36 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (62) AND 249.23/132.36 (63) QDP 249.23/132.36 (64) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (65) QDP 249.23/132.36 (66) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (67) QDP 249.23/132.36 (68) QDPSizeChangeProof [EQUIVALENT, 0 ms] 249.23/132.36 (69) YES 249.23/132.36 (70) QDP 249.23/132.36 (71) UsableRulesProof [EQUIVALENT, 0 ms] 249.23/132.36 (72) QDP 249.23/132.36 (73) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (74) QDP 249.23/132.36 (75) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (76) QDP 249.23/132.36 (77) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (78) QDP 249.23/132.36 (79) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (80) QDP 249.23/132.36 (81) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (82) QDP 249.23/132.36 (83) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (84) QDP 249.23/132.36 (85) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (86) QDP 249.23/132.36 (87) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (88) QDP 249.23/132.36 (89) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (90) QDP 249.23/132.36 (91) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (92) QDP 249.23/132.36 (93) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (94) QDP 249.23/132.36 (95) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (96) QDP 249.23/132.36 (97) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (98) QDP 249.23/132.36 (99) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (100) QDP 249.23/132.36 (101) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (102) QDP 249.23/132.36 (103) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (104) QDP 249.23/132.36 (105) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (106) QDP 249.23/132.36 (107) TransformationProof [EQUIVALENT, 0 ms] 249.23/132.36 (108) QDP 249.23/132.36 (109) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (110) QDP 249.23/132.36 (111) MNOCProof [EQUIVALENT, 0 ms] 249.23/132.36 (112) QDP 249.23/132.36 (113) SplitQDPProof [EQUIVALENT, 0 ms] 249.23/132.36 (114) AND 249.23/132.36 (115) QDP 249.23/132.36 (116) SemLabProof [SOUND, 0 ms] 249.23/132.36 (117) QDP 249.23/132.36 (118) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (119) QDP 249.23/132.36 (120) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] 249.23/132.36 (121) QDP 249.23/132.36 (122) MRRProof [EQUIVALENT, 0 ms] 249.23/132.36 (123) QDP 249.23/132.36 (124) MRRProof [EQUIVALENT, 5 ms] 249.23/132.36 (125) QDP 249.23/132.36 (126) PisEmptyProof [SOUND, 0 ms] 249.23/132.36 (127) TRUE 249.23/132.36 (128) QDP 249.23/132.36 (129) SplitQDPProof [EQUIVALENT, 0 ms] 249.23/132.36 (130) AND 249.23/132.36 (131) QDP 249.23/132.36 (132) SemLabProof [SOUND, 0 ms] 249.23/132.36 (133) QDP 249.23/132.36 (134) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (135) QDP 249.23/132.36 (136) UsableRulesReductionPairsProof [EQUIVALENT, 4 ms] 249.23/132.36 (137) QDP 249.23/132.36 (138) MRRProof [EQUIVALENT, 0 ms] 249.23/132.36 (139) QDP 249.23/132.36 (140) MRRProof [EQUIVALENT, 0 ms] 249.23/132.36 (141) QDP 249.23/132.36 (142) PisEmptyProof [SOUND, 0 ms] 249.23/132.36 (143) TRUE 249.23/132.36 (144) QDP 249.23/132.36 (145) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (146) QDP 249.23/132.36 (147) SplitQDPProof [EQUIVALENT, 0 ms] 249.23/132.36 (148) AND 249.23/132.36 (149) QDP 249.23/132.36 (150) SemLabProof [SOUND, 0 ms] 249.23/132.36 (151) QDP 249.23/132.36 (152) DependencyGraphProof [EQUIVALENT, 0 ms] 249.23/132.36 (153) QDP 249.23/132.36 (154) MRRProof [EQUIVALENT, 0 ms] 249.23/132.36 (155) QDP 249.23/132.36 (156) MRRProof [EQUIVALENT, 0 ms] 249.23/132.36 (157) QDP 249.23/132.36 (158) PisEmptyProof [SOUND, 0 ms] 249.23/132.36 (159) TRUE 249.23/132.36 (160) QDP 249.23/132.36 (161) QReductionProof [EQUIVALENT, 0 ms] 249.23/132.36 (162) QDP 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (0) 249.23/132.36 Obligation: 249.23/132.36 Term rewrite system R: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 f(g(a)) -> f(s(g(b))) 249.23/132.36 f(f(x)) -> b 249.23/132.36 g(x) -> f(g(x)) 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 Outermost Strategy. 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 249.23/132.36 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (2) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 top(go_up(x)) -> top(reduce(x)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 redex_f(g(a)) -> result_f(f(s(g(b)))) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (3) QTRSRRRProof (EQUIVALENT) 249.23/132.36 Used ordering: 249.23/132.36 Polynomial interpretation [POLO]: 249.23/132.36 249.23/132.36 POL(a) = 1 249.23/132.36 POL(b) = 0 249.23/132.36 POL(check_f(x_1)) = x_1 249.23/132.36 POL(check_g(x_1)) = x_1 249.23/132.36 POL(f(x_1)) = x_1 249.23/132.36 POL(g(x_1)) = x_1 249.23/132.36 POL(go_up(x_1)) = x_1 249.23/132.36 POL(in_f_1(x_1)) = x_1 249.23/132.36 POL(in_g_1(x_1)) = x_1 249.23/132.36 POL(in_s_1(x_1)) = 2*x_1 249.23/132.36 POL(redex_f(x_1)) = x_1 249.23/132.36 POL(redex_g(x_1)) = x_1 249.23/132.36 POL(reduce(x_1)) = x_1 249.23/132.36 POL(result_f(x_1)) = x_1 249.23/132.36 POL(result_g(x_1)) = x_1 249.23/132.36 POL(s(x_1)) = 2*x_1 249.23/132.36 POL(top(x_1)) = 2*x_1 249.23/132.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 249.23/132.36 249.23/132.36 redex_f(g(a)) -> result_f(f(s(g(b)))) 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (4) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 top(go_up(x)) -> top(reduce(x)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (5) DependencyPairsProof (EQUIVALENT) 249.23/132.36 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (6) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 TOP(go_up(x)) -> REDUCE(x) 249.23/132.36 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 249.23/132.36 REDUCE(f(x_1)) -> REDEX_F(x_1) 249.23/132.36 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 249.23/132.36 REDUCE(g(x_1)) -> REDEX_G(x_1) 249.23/132.36 CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) 249.23/132.36 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 249.23/132.36 CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) 249.23/132.36 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) 249.23/132.36 REDUCE(s(x_1)) -> REDUCE(x_1) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 top(go_up(x)) -> top(reduce(x)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (7) DependencyGraphProof (EQUIVALENT) 249.23/132.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (8) 249.23/132.36 Complex Obligation (AND) 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (9) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(s(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 top(go_up(x)) -> top(reduce(x)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (10) UsableRulesProof (EQUIVALENT) 249.23/132.36 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. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (11) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(s(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (12) QReductionProof (EQUIVALENT) 249.23/132.36 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (13) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(s(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (14) UsableRulesReductionPairsProof (EQUIVALENT) 249.23/132.36 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. 249.23/132.36 249.23/132.36 The following dependency pairs can be deleted: 249.23/132.36 249.23/132.36 REDUCE(s(x_1)) -> REDUCE(x_1) 249.23/132.36 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 249.23/132.36 The following rules are removed from R: 249.23/132.36 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 Used ordering: POLO with Polynomial interpretation [POLO]: 249.23/132.36 249.23/132.36 POL(CHECK_F(x_1)) = x_1 249.23/132.36 POL(REDUCE(x_1)) = 2*x_1 249.23/132.36 POL(b) = 0 249.23/132.36 POL(f(x_1)) = 2*x_1 249.23/132.36 POL(redex_f(x_1)) = 2*x_1 249.23/132.36 POL(result_f(x_1)) = x_1 249.23/132.36 POL(s(x_1)) = 2*x_1 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (15) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 249.23/132.36 249.23/132.36 R is empty. 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (16) DependencyGraphProof (EQUIVALENT) 249.23/132.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (17) 249.23/132.36 TRUE 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (18) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 top(go_up(x)) -> top(reduce(x)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (19) UsableRulesProof (EQUIVALENT) 249.23/132.36 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. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (20) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (21) QReductionProof (EQUIVALENT) 249.23/132.36 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (22) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (23) TransformationProof (SOUND) 249.23/132.36 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.36 249.23/132.36 (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) 249.23/132.36 (TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))),TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0)))) 249.23/132.36 (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (24) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 249.23/132.36 TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) 249.23/132.36 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (25) TransformationProof (EQUIVALENT) 249.23/132.36 By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(redex_g(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.36 249.23/132.36 (TOP(go_up(g(x0))) -> TOP(check_g(result_g(f(g(x0))))),TOP(go_up(g(x0))) -> TOP(check_g(result_g(f(g(x0)))))) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (26) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 249.23/132.36 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 249.23/132.36 TOP(go_up(g(x0))) -> TOP(check_g(result_g(f(g(x0))))) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (27) TransformationProof (EQUIVALENT) 249.23/132.36 By rewriting [LPAR04] the rule TOP(go_up(g(x0))) -> TOP(check_g(result_g(f(g(x0))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.36 249.23/132.36 (TOP(go_up(g(x0))) -> TOP(go_up(f(g(x0)))),TOP(go_up(g(x0))) -> TOP(go_up(f(g(x0))))) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (28) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 249.23/132.36 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 249.23/132.36 TOP(go_up(g(x0))) -> TOP(go_up(f(g(x0)))) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (29) QDPOrderProof (EQUIVALENT) 249.23/132.36 We use the reduction pair processor [LPAR04,JAR06]. 249.23/132.36 249.23/132.36 249.23/132.36 The following pairs can be oriented strictly and are deleted. 249.23/132.36 249.23/132.36 TOP(go_up(g(x0))) -> TOP(go_up(f(g(x0)))) 249.23/132.36 The remaining pairs can at least be oriented weakly. 249.23/132.36 Used ordering: Polynomial interpretation [POLO]: 249.23/132.36 249.23/132.36 POL(TOP(x_1)) = x_1 249.23/132.36 POL(b) = 0 249.23/132.36 POL(check_f(x_1)) = x_1 249.23/132.36 POL(check_g(x_1)) = 1 249.23/132.36 POL(f(x_1)) = 0 249.23/132.36 POL(g(x_1)) = 1 + x_1 249.23/132.36 POL(go_up(x_1)) = x_1 249.23/132.36 POL(in_f_1(x_1)) = 0 249.23/132.36 POL(in_s_1(x_1)) = 0 249.23/132.36 POL(redex_f(x_1)) = 0 249.23/132.36 POL(redex_g(x_1)) = 1 + x_1 249.23/132.36 POL(reduce(x_1)) = 0 249.23/132.36 POL(result_f(x_1)) = x_1 249.23/132.36 POL(result_g(x_1)) = 1 249.23/132.36 POL(s(x_1)) = 0 249.23/132.36 249.23/132.36 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 249.23/132.36 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (30) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 249.23/132.36 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (31) QReductionProof (EQUIVALENT) 249.23/132.36 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 249.23/132.36 249.23/132.36 redex_f(g(a)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (32) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 249.23/132.36 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (33) UsableRulesProof (EQUIVALENT) 249.23/132.36 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. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (34) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (35) QReductionProof (EQUIVALENT) 249.23/132.36 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 249.23/132.36 249.23/132.36 top(go_up(x0)) 249.23/132.36 in_g_1(go_up(x0)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (36) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(g(a)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (37) QReductionProof (EQUIVALENT) 249.23/132.36 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 249.23/132.36 249.23/132.36 redex_f(g(a)) 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (38) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 TOP(go_up(x)) -> TOP(reduce(x)) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 reduce(f(x_1)) -> check_f(redex_f(x_1)) 249.23/132.36 reduce(g(x_1)) -> check_g(redex_g(x_1)) 249.23/132.36 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 249.23/132.36 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 249.23/132.36 redex_g(x) -> result_g(f(g(x))) 249.23/132.36 check_g(result_g(x)) -> go_up(x) 249.23/132.36 redex_f(f(x)) -> result_f(b) 249.23/132.36 check_f(result_f(x)) -> go_up(x) 249.23/132.36 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 249.23/132.36 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 249.23/132.36 249.23/132.36 The set Q consists of the following terms: 249.23/132.36 249.23/132.36 reduce(f(x0)) 249.23/132.36 reduce(g(x0)) 249.23/132.36 redex_f(f(x0)) 249.23/132.36 redex_g(x0) 249.23/132.36 check_f(result_f(x0)) 249.23/132.36 check_g(result_g(x0)) 249.23/132.36 check_f(redex_f(x0)) 249.23/132.36 reduce(s(x0)) 249.23/132.36 in_f_1(go_up(x0)) 249.23/132.36 in_s_1(go_up(x0)) 249.23/132.36 249.23/132.36 We have to consider all (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (39) Trivial-Transformation (SOUND) 249.23/132.36 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (40) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 f(g(a)) -> f(s(g(b))) 249.23/132.36 f(f(x)) -> b 249.23/132.36 g(x) -> f(g(x)) 249.23/132.36 249.23/132.36 Q is empty. 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (41) QTRSRRRProof (EQUIVALENT) 249.23/132.36 Used ordering: 249.23/132.36 Polynomial interpretation [POLO]: 249.23/132.36 249.23/132.36 POL(a) = 2 249.23/132.36 POL(b) = 0 249.23/132.36 POL(f(x_1)) = x_1 249.23/132.36 POL(g(x_1)) = 2*x_1 249.23/132.36 POL(s(x_1)) = x_1 249.23/132.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 249.23/132.36 249.23/132.36 f(g(a)) -> f(s(g(b))) 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (42) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 f(f(x)) -> b 249.23/132.36 g(x) -> f(g(x)) 249.23/132.36 249.23/132.36 Q is empty. 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (43) DependencyPairsProof (EQUIVALENT) 249.23/132.36 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (44) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 G(x) -> F(g(x)) 249.23/132.36 G(x) -> G(x) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 f(f(x)) -> b 249.23/132.36 g(x) -> f(g(x)) 249.23/132.36 249.23/132.36 Q is empty. 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (45) DependencyGraphProof (EQUIVALENT) 249.23/132.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (46) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 G(x) -> G(x) 249.23/132.36 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 f(f(x)) -> b 249.23/132.36 g(x) -> f(g(x)) 249.23/132.36 249.23/132.36 Q is empty. 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (47) UsableRulesProof (EQUIVALENT) 249.23/132.36 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. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (48) 249.23/132.36 Obligation: 249.23/132.36 Q DP problem: 249.23/132.36 The TRS P consists of the following rules: 249.23/132.36 249.23/132.36 G(x) -> G(x) 249.23/132.36 249.23/132.36 R is empty. 249.23/132.36 Q is empty. 249.23/132.36 We have to consider all minimal (P,Q,R)-chains. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (49) NonTerminationLoopProof (COMPLETE) 249.23/132.36 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 249.23/132.36 Found a loop by semiunifying a rule from P directly. 249.23/132.36 249.23/132.36 s = G(x) evaluates to t =G(x) 249.23/132.36 249.23/132.36 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 249.23/132.36 * Matcher: [ ] 249.23/132.36 * Semiunifier: [ ] 249.23/132.36 249.23/132.36 -------------------------------------------------------------------------------- 249.23/132.36 Rewriting sequence 249.23/132.36 249.23/132.36 The DP semiunifies directly so there is only one rewrite step from G(x) to G(x). 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (50) 249.23/132.36 NO 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (51) Raffelsieper-Zantema-Transformation (SOUND) 249.23/132.36 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (52) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.36 249.23/132.36 down(f(g(a))) -> up(f(s(g(b)))) 249.23/132.36 down(f(f(x))) -> up(b) 249.23/132.36 down(g(x)) -> up(f(g(x))) 249.23/132.36 top(up(x)) -> top(down(x)) 249.23/132.36 down(s(y2)) -> s_flat(down(y2)) 249.23/132.36 down(f(a)) -> f_flat(down(a)) 249.23/132.36 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.36 down(f(b)) -> f_flat(down(b)) 249.23/132.36 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.36 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.36 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.36 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.36 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.36 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.36 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.36 g_flat(up(x_1)) -> up(g(x_1)) 249.23/132.36 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.36 249.23/132.36 Q is empty. 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (53) QTRSRRRProof (EQUIVALENT) 249.23/132.36 Used ordering: 249.23/132.36 Polynomial interpretation [POLO]: 249.23/132.36 249.23/132.36 POL(a) = 0 249.23/132.36 POL(b) = 0 249.23/132.36 POL(down(x_1)) = 2*x_1 249.23/132.36 POL(f(x_1)) = x_1 249.23/132.36 POL(f_flat(x_1)) = x_1 249.23/132.36 POL(fresh_constant) = 0 249.23/132.36 POL(g(x_1)) = 2*x_1 249.23/132.36 POL(g_flat(x_1)) = 2 + 2*x_1 249.23/132.36 POL(s(x_1)) = x_1 249.23/132.36 POL(s_flat(x_1)) = x_1 249.23/132.36 POL(top(x_1)) = x_1 249.23/132.36 POL(up(x_1)) = 2*x_1 249.23/132.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 249.23/132.36 249.23/132.36 g_flat(up(x_1)) -> up(g(x_1)) 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 249.23/132.36 ---------------------------------------- 249.23/132.36 249.23/132.36 (54) 249.23/132.36 Obligation: 249.23/132.36 Q restricted rewrite system: 249.23/132.36 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(g(a))) -> up(f(s(g(b)))) 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 Q is empty. 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (55) QTRSRRRProof (EQUIVALENT) 249.23/132.37 Used ordering: 249.23/132.37 Polynomial interpretation [POLO]: 249.23/132.37 249.23/132.37 POL(a) = 1 249.23/132.37 POL(b) = 0 249.23/132.37 POL(down(x_1)) = 2*x_1 249.23/132.37 POL(f(x_1)) = x_1 249.23/132.37 POL(f_flat(x_1)) = x_1 249.23/132.37 POL(fresh_constant) = 0 249.23/132.37 POL(g(x_1)) = x_1 249.23/132.37 POL(s(x_1)) = 2*x_1 249.23/132.37 POL(s_flat(x_1)) = 2*x_1 249.23/132.37 POL(top(x_1)) = 2*x_1 249.23/132.37 POL(up(x_1)) = 2*x_1 249.23/132.37 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 249.23/132.37 249.23/132.37 down(f(g(a))) -> up(f(s(g(b)))) 249.23/132.37 249.23/132.37 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (56) 249.23/132.37 Obligation: 249.23/132.37 Q restricted rewrite system: 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 Q is empty. 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (57) AAECC Innermost (EQUIVALENT) 249.23/132.37 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 249.23/132.37 The TRS R 2 is 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 249.23/132.37 The signature Sigma is {top_1} 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (58) 249.23/132.37 Obligation: 249.23/132.37 Q restricted rewrite system: 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (59) DependencyPairsProof (EQUIVALENT) 249.23/132.37 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (60) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(x)) -> TOP(down(x)) 249.23/132.37 TOP(up(x)) -> DOWN(x) 249.23/132.37 DOWN(s(y2)) -> S_FLAT(down(y2)) 249.23/132.37 DOWN(s(y2)) -> DOWN(y2) 249.23/132.37 DOWN(f(a)) -> F_FLAT(down(a)) 249.23/132.37 DOWN(f(a)) -> DOWN(a) 249.23/132.37 DOWN(f(s(y6))) -> F_FLAT(down(s(y6))) 249.23/132.37 DOWN(f(s(y6))) -> DOWN(s(y6)) 249.23/132.37 DOWN(f(b)) -> F_FLAT(down(b)) 249.23/132.37 DOWN(f(b)) -> DOWN(b) 249.23/132.37 DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) 249.23/132.37 DOWN(f(fresh_constant)) -> DOWN(fresh_constant) 249.23/132.37 DOWN(f(g(f(y8)))) -> F_FLAT(down(g(f(y8)))) 249.23/132.37 DOWN(f(g(f(y8)))) -> DOWN(g(f(y8))) 249.23/132.37 DOWN(f(g(g(y9)))) -> F_FLAT(down(g(g(y9)))) 249.23/132.37 DOWN(f(g(g(y9)))) -> DOWN(g(g(y9))) 249.23/132.37 DOWN(f(g(s(y10)))) -> F_FLAT(down(g(s(y10)))) 249.23/132.37 DOWN(f(g(s(y10)))) -> DOWN(g(s(y10))) 249.23/132.37 DOWN(f(g(b))) -> F_FLAT(down(g(b))) 249.23/132.37 DOWN(f(g(b))) -> DOWN(g(b)) 249.23/132.37 DOWN(f(g(fresh_constant))) -> F_FLAT(down(g(fresh_constant))) 249.23/132.37 DOWN(f(g(fresh_constant))) -> DOWN(g(fresh_constant)) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (61) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 19 less nodes. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (62) 249.23/132.37 Complex Obligation (AND) 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (63) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 DOWN(f(s(y6))) -> DOWN(s(y6)) 249.23/132.37 DOWN(s(y2)) -> DOWN(y2) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (64) UsableRulesProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (65) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 DOWN(f(s(y6))) -> DOWN(s(y6)) 249.23/132.37 DOWN(s(y2)) -> DOWN(y2) 249.23/132.37 249.23/132.37 R is empty. 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (66) QReductionProof (EQUIVALENT) 249.23/132.37 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (67) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 DOWN(f(s(y6))) -> DOWN(s(y6)) 249.23/132.37 DOWN(s(y2)) -> DOWN(y2) 249.23/132.37 249.23/132.37 R is empty. 249.23/132.37 Q is empty. 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (68) QDPSizeChangeProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 249.23/132.37 From the DPs we obtained the following set of size-change graphs: 249.23/132.37 *DOWN(s(y2)) -> DOWN(y2) 249.23/132.37 The graph contains the following edges 1 > 1 249.23/132.37 249.23/132.37 249.23/132.37 *DOWN(f(s(y6))) -> DOWN(s(y6)) 249.23/132.37 The graph contains the following edges 1 > 1 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (69) 249.23/132.37 YES 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (70) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(x)) -> TOP(down(x)) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 top(up(x)) -> top(down(x)) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (71) UsableRulesProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (72) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(x)) -> TOP(down(x)) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 top(up(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (73) QReductionProof (EQUIVALENT) 249.23/132.37 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 249.23/132.37 249.23/132.37 top(up(x0)) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (74) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(x)) -> TOP(down(x)) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (75) TransformationProof (EQUIVALENT) 249.23/132.37 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(f(x0)))) -> TOP(up(b)),TOP(up(f(f(x0)))) -> TOP(up(b))) 249.23/132.37 (TOP(up(g(x0))) -> TOP(up(f(g(x0)))),TOP(up(g(x0))) -> TOP(up(f(g(x0))))) 249.23/132.37 (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) 249.23/132.37 (TOP(up(f(a))) -> TOP(f_flat(down(a))),TOP(up(f(a))) -> TOP(f_flat(down(a)))) 249.23/132.37 (TOP(up(f(s(x0)))) -> TOP(f_flat(down(s(x0)))),TOP(up(f(s(x0)))) -> TOP(f_flat(down(s(x0))))) 249.23/132.37 (TOP(up(f(b))) -> TOP(f_flat(down(b))),TOP(up(f(b))) -> TOP(f_flat(down(b)))) 249.23/132.37 (TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))),TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant)))) 249.23/132.37 (TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0))))),TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0)))))) 249.23/132.37 (TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))),TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0)))))) 249.23/132.37 (TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))),TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0)))))) 249.23/132.37 (TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))),TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b))))) 249.23/132.37 (TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))),TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (76) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(f(f(x0)))) -> TOP(up(b)) 249.23/132.37 TOP(up(g(x0))) -> TOP(up(f(g(x0)))) 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(a))) -> TOP(f_flat(down(a))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(down(s(x0)))) 249.23/132.37 TOP(up(f(b))) -> TOP(f_flat(down(b))) 249.23/132.37 TOP(up(f(fresh_constant))) -> TOP(f_flat(down(fresh_constant))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (77) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (78) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(down(s(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (79) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(s(x0)))) -> TOP(f_flat(down(s(x0)))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))),TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (80) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (81) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(f(x0))))) -> TOP(f_flat(down(g(f(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))),TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (82) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (83) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(g(x0))))) -> TOP(f_flat(down(g(g(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))),TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (84) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (85) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(s(x0))))) -> TOP(f_flat(down(g(s(x0))))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))),TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (86) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (87) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(b)))) -> TOP(f_flat(down(g(b)))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))),TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b)))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (88) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (89) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(down(g(fresh_constant)))) at position [0,0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))),TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant)))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (90) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (91) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(f(x0))))) -> TOP(f_flat(up(f(g(f(x0)))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(f(x0))))) -> TOP(up(f(f(g(f(x0)))))),TOP(up(f(g(f(x0))))) -> TOP(up(f(f(g(f(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (92) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 TOP(up(f(g(f(x0))))) -> TOP(up(f(f(g(f(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (93) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (94) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (95) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(g(x0))))) -> TOP(f_flat(up(f(g(g(x0)))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(g(x0))))) -> TOP(up(f(f(g(g(x0)))))),TOP(up(f(g(g(x0))))) -> TOP(up(f(f(g(g(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (96) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 TOP(up(f(g(g(x0))))) -> TOP(up(f(f(g(g(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (97) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (98) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (99) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(s(x0))))) -> TOP(f_flat(up(f(g(s(x0)))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(s(x0))))) -> TOP(up(f(f(g(s(x0)))))),TOP(up(f(g(s(x0))))) -> TOP(up(f(f(g(s(x0))))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (100) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 TOP(up(f(g(s(x0))))) -> TOP(up(f(f(g(s(x0)))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (101) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (102) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (103) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(b)))) -> TOP(f_flat(up(f(g(b))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(b)))) -> TOP(up(f(f(g(b))))),TOP(up(f(g(b)))) -> TOP(up(f(f(g(b)))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (104) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 TOP(up(f(g(b)))) -> TOP(up(f(f(g(b))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (105) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (106) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (107) TransformationProof (EQUIVALENT) 249.23/132.37 By rewriting [LPAR04] the rule TOP(up(f(g(fresh_constant)))) -> TOP(f_flat(up(f(g(fresh_constant))))) at position [0] we obtained the following new rules [LPAR04]: 249.23/132.37 249.23/132.37 (TOP(up(f(g(fresh_constant)))) -> TOP(up(f(f(g(fresh_constant))))),TOP(up(f(g(fresh_constant)))) -> TOP(up(f(f(g(fresh_constant)))))) 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (108) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 TOP(up(f(g(fresh_constant)))) -> TOP(up(f(f(g(fresh_constant))))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (109) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (110) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (111) MNOCProof (EQUIVALENT) 249.23/132.37 We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (112) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 Q is empty. 249.23/132.37 We have to consider all (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (113) SplitQDPProof (EQUIVALENT) 249.23/132.37 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (114) 249.23/132.37 Complex Obligation (AND) 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (115) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.37 down(f(a)) -> f_flat(down(a)) 249.23/132.37 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.37 down(f(b)) -> f_flat(down(b)) 249.23/132.37 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 249.23/132.37 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.37 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.37 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.37 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.37 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.37 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.37 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down(f(f(x0))) 249.23/132.37 down(g(x0)) 249.23/132.37 down(s(x0)) 249.23/132.37 down(f(a)) 249.23/132.37 down(f(s(x0))) 249.23/132.37 down(f(b)) 249.23/132.37 down(f(fresh_constant)) 249.23/132.37 down(f(g(f(x0)))) 249.23/132.37 down(f(g(g(x0)))) 249.23/132.37 down(f(g(s(x0)))) 249.23/132.37 down(f(g(b))) 249.23/132.37 down(f(g(fresh_constant))) 249.23/132.37 f_flat(up(x0)) 249.23/132.37 s_flat(up(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (116) SemLabProof (SOUND) 249.23/132.37 We found the following model for the rules of the TRSs R and P. 249.23/132.37 Interpretation over the domain with elements from 0 to 1. 249.23/132.37 s_flat: 0 249.23/132.37 s: 0 249.23/132.37 a: 0 249.23/132.37 b: 0 249.23/132.37 down: 0 249.23/132.37 f: 0 249.23/132.37 fresh_constant: 1 249.23/132.37 up: 0 249.23/132.37 f_flat: 0 249.23/132.37 TOP: 0 249.23/132.37 g: 0 249.23/132.37 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (117) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.37 TOP.0(up.0(s.1(x0))) -> TOP.0(s_flat.0(down.1(x0))) 249.23/132.37 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.37 TOP.0(up.0(f.0(s.1(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.1(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.37 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.37 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.37 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.37 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.37 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.37 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 249.23/132.37 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.37 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.37 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.37 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.37 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.37 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.37 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.37 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.37 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) -> f_flat.0(down.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.37 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.37 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.37 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x0))) 249.23/132.37 down.0(f.0(f.1(x0))) 249.23/132.37 down.0(g.0(x0)) 249.23/132.37 down.0(g.1(x0)) 249.23/132.37 down.0(s.0(x0)) 249.23/132.37 down.0(s.1(x0)) 249.23/132.37 down.0(f.0(a.)) 249.23/132.37 down.0(f.0(s.0(x0))) 249.23/132.37 down.0(f.0(s.1(x0))) 249.23/132.37 down.0(f.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(x0)))) 249.23/132.37 down.0(f.0(g.0(f.1(x0)))) 249.23/132.37 down.0(f.0(g.0(g.0(x0)))) 249.23/132.37 down.0(f.0(g.0(g.1(x0)))) 249.23/132.37 down.0(f.0(g.0(s.0(x0)))) 249.23/132.37 down.0(f.0(g.0(s.1(x0)))) 249.23/132.37 down.0(f.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x0)) 249.23/132.37 f_flat.0(up.1(x0)) 249.23/132.37 s_flat.0(up.0(x0)) 249.23/132.37 s_flat.0(up.1(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (118) DependencyGraphProof (EQUIVALENT) 249.23/132.37 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (119) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.37 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.37 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.37 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.37 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.37 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.37 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.37 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 249.23/132.37 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.37 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.37 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.37 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.37 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.37 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.37 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.37 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.37 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) -> f_flat.0(down.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.37 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.37 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.37 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x0))) 249.23/132.37 down.0(f.0(f.1(x0))) 249.23/132.37 down.0(g.0(x0)) 249.23/132.37 down.0(g.1(x0)) 249.23/132.37 down.0(s.0(x0)) 249.23/132.37 down.0(s.1(x0)) 249.23/132.37 down.0(f.0(a.)) 249.23/132.37 down.0(f.0(s.0(x0))) 249.23/132.37 down.0(f.0(s.1(x0))) 249.23/132.37 down.0(f.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(x0)))) 249.23/132.37 down.0(f.0(g.0(f.1(x0)))) 249.23/132.37 down.0(f.0(g.0(g.0(x0)))) 249.23/132.37 down.0(f.0(g.0(g.1(x0)))) 249.23/132.37 down.0(f.0(g.0(s.0(x0)))) 249.23/132.37 down.0(f.0(g.0(s.1(x0)))) 249.23/132.37 down.0(f.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x0)) 249.23/132.37 f_flat.0(up.1(x0)) 249.23/132.37 s_flat.0(up.0(x0)) 249.23/132.37 s_flat.0(up.1(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (120) UsableRulesReductionPairsProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 249.23/132.37 No dependency pairs are removed. 249.23/132.37 249.23/132.37 The following rules are removed from R: 249.23/132.37 249.23/132.37 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.37 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.37 Used ordering: POLO with Polynomial interpretation [POLO]: 249.23/132.37 249.23/132.37 POL(TOP.0(x_1)) = x_1 249.23/132.37 POL(a.) = 0 249.23/132.37 POL(b.) = 0 249.23/132.37 POL(down.0(x_1)) = 1 + x_1 249.23/132.37 POL(down.1(x_1)) = 1 + x_1 249.23/132.37 POL(f.0(x_1)) = x_1 249.23/132.37 POL(f.1(x_1)) = x_1 249.23/132.37 POL(f_flat.0(x_1)) = x_1 249.23/132.37 POL(fresh_constant.) = 0 249.23/132.37 POL(g.0(x_1)) = x_1 249.23/132.37 POL(g.1(x_1)) = x_1 249.23/132.37 POL(s.0(x_1)) = 1 + x_1 249.23/132.37 POL(s.1(x_1)) = 1 + x_1 249.23/132.37 POL(s_flat.0(x_1)) = 1 + x_1 249.23/132.37 POL(up.0(x_1)) = 1 + x_1 249.23/132.37 POL(up.1(x_1)) = 1 + x_1 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (121) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.37 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.37 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.37 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.37 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.37 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.37 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.37 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 249.23/132.37 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.37 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.37 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.37 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.37 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.37 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.37 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.37 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.37 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) -> f_flat.0(down.0(g.1(fresh_constant.))) 249.23/132.37 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.37 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x0))) 249.23/132.37 down.0(f.0(f.1(x0))) 249.23/132.37 down.0(g.0(x0)) 249.23/132.37 down.0(g.1(x0)) 249.23/132.37 down.0(s.0(x0)) 249.23/132.37 down.0(s.1(x0)) 249.23/132.37 down.0(f.0(a.)) 249.23/132.37 down.0(f.0(s.0(x0))) 249.23/132.37 down.0(f.0(s.1(x0))) 249.23/132.37 down.0(f.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(x0)))) 249.23/132.37 down.0(f.0(g.0(f.1(x0)))) 249.23/132.37 down.0(f.0(g.0(g.0(x0)))) 249.23/132.37 down.0(f.0(g.0(g.1(x0)))) 249.23/132.37 down.0(f.0(g.0(s.0(x0)))) 249.23/132.37 down.0(f.0(g.0(s.1(x0)))) 249.23/132.37 down.0(f.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x0)) 249.23/132.37 f_flat.0(up.1(x0)) 249.23/132.37 s_flat.0(up.0(x0)) 249.23/132.37 s_flat.0(up.1(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (122) MRRProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 249.23/132.37 249.23/132.37 Strictly oriented rules of the TRS R: 249.23/132.37 249.23/132.37 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.37 down.0(f.1(fresh_constant.)) -> f_flat.0(down.1(fresh_constant.)) 249.23/132.37 249.23/132.37 Used ordering: Polynomial interpretation [POLO]: 249.23/132.37 249.23/132.37 POL(TOP.0(x_1)) = x_1 249.23/132.37 POL(a.) = 0 249.23/132.37 POL(b.) = 0 249.23/132.37 POL(down.0(x_1)) = 1 + x_1 249.23/132.37 POL(down.1(x_1)) = x_1 249.23/132.37 POL(f.0(x_1)) = x_1 249.23/132.37 POL(f.1(x_1)) = x_1 249.23/132.37 POL(f_flat.0(x_1)) = x_1 249.23/132.37 POL(fresh_constant.) = 0 249.23/132.37 POL(g.0(x_1)) = x_1 249.23/132.37 POL(g.1(x_1)) = x_1 249.23/132.37 POL(s.0(x_1)) = 1 + x_1 249.23/132.37 POL(s.1(x_1)) = 1 + x_1 249.23/132.37 POL(s_flat.0(x_1)) = 1 + x_1 249.23/132.37 POL(up.0(x_1)) = 1 + x_1 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (123) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.37 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.37 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.37 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.37 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.37 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.37 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 249.23/132.37 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.37 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.37 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.37 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.37 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.37 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.37 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.37 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.37 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.37 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) -> f_flat.0(down.0(g.1(fresh_constant.))) 249.23/132.37 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.37 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x0))) 249.23/132.37 down.0(f.0(f.1(x0))) 249.23/132.37 down.0(g.0(x0)) 249.23/132.37 down.0(g.1(x0)) 249.23/132.37 down.0(s.0(x0)) 249.23/132.37 down.0(s.1(x0)) 249.23/132.37 down.0(f.0(a.)) 249.23/132.37 down.0(f.0(s.0(x0))) 249.23/132.37 down.0(f.0(s.1(x0))) 249.23/132.37 down.0(f.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(x0)))) 249.23/132.37 down.0(f.0(g.0(f.1(x0)))) 249.23/132.37 down.0(f.0(g.0(g.0(x0)))) 249.23/132.37 down.0(f.0(g.0(g.1(x0)))) 249.23/132.37 down.0(f.0(g.0(s.0(x0)))) 249.23/132.37 down.0(f.0(g.0(s.1(x0)))) 249.23/132.37 down.0(f.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x0)) 249.23/132.37 f_flat.0(up.1(x0)) 249.23/132.37 s_flat.0(up.0(x0)) 249.23/132.37 s_flat.0(up.1(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (124) MRRProof (EQUIVALENT) 249.23/132.37 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. 249.23/132.37 249.23/132.37 249.23/132.37 Strictly oriented rules of the TRS R: 249.23/132.37 249.23/132.37 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.37 249.23/132.37 Used ordering: Polynomial interpretation [POLO]: 249.23/132.37 249.23/132.37 POL(TOP.0(x_1)) = x_1 249.23/132.37 POL(a.) = 0 249.23/132.37 POL(b.) = 0 249.23/132.37 POL(down.0(x_1)) = x_1 249.23/132.37 POL(f.0(x_1)) = x_1 249.23/132.37 POL(f.1(x_1)) = 1 + x_1 249.23/132.37 POL(f_flat.0(x_1)) = x_1 249.23/132.37 POL(fresh_constant.) = 0 249.23/132.37 POL(g.0(x_1)) = x_1 249.23/132.37 POL(g.1(x_1)) = x_1 249.23/132.37 POL(s.0(x_1)) = x_1 249.23/132.37 POL(s.1(x_1)) = x_1 249.23/132.37 POL(s_flat.0(x_1)) = x_1 249.23/132.37 POL(up.0(x_1)) = x_1 249.23/132.37 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (125) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.37 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.37 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.37 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.37 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.37 down.0(f.0(a.)) -> f_flat.0(down.0(a.)) 249.23/132.37 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.37 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.37 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.37 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.37 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.37 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.37 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.37 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.37 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.37 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) -> f_flat.0(down.0(g.1(fresh_constant.))) 249.23/132.37 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.37 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.37 249.23/132.37 The set Q consists of the following terms: 249.23/132.37 249.23/132.37 down.0(f.0(f.0(x0))) 249.23/132.37 down.0(f.0(f.1(x0))) 249.23/132.37 down.0(g.0(x0)) 249.23/132.37 down.0(g.1(x0)) 249.23/132.37 down.0(s.0(x0)) 249.23/132.37 down.0(s.1(x0)) 249.23/132.37 down.0(f.0(a.)) 249.23/132.37 down.0(f.0(s.0(x0))) 249.23/132.37 down.0(f.0(s.1(x0))) 249.23/132.37 down.0(f.0(b.)) 249.23/132.37 down.0(f.1(fresh_constant.)) 249.23/132.37 down.0(f.0(g.0(f.0(x0)))) 249.23/132.37 down.0(f.0(g.0(f.1(x0)))) 249.23/132.37 down.0(f.0(g.0(g.0(x0)))) 249.23/132.37 down.0(f.0(g.0(g.1(x0)))) 249.23/132.37 down.0(f.0(g.0(s.0(x0)))) 249.23/132.37 down.0(f.0(g.0(s.1(x0)))) 249.23/132.37 down.0(f.0(g.0(b.))) 249.23/132.37 down.0(f.0(g.1(fresh_constant.))) 249.23/132.37 f_flat.0(up.0(x0)) 249.23/132.37 f_flat.0(up.1(x0)) 249.23/132.37 s_flat.0(up.0(x0)) 249.23/132.37 s_flat.0(up.1(x0)) 249.23/132.37 249.23/132.37 We have to consider all minimal (P,Q,R)-chains. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (126) PisEmptyProof (SOUND) 249.23/132.37 The TRS P is empty. Hence, there is no (P,Q,R) chain. 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (127) 249.23/132.37 TRUE 249.23/132.37 249.23/132.37 ---------------------------------------- 249.23/132.37 249.23/132.37 (128) 249.23/132.37 Obligation: 249.23/132.37 Q DP problem: 249.23/132.37 The TRS P consists of the following rules: 249.23/132.37 249.23/132.37 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.37 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.37 249.23/132.37 The TRS R consists of the following rules: 249.23/132.37 249.23/132.37 down(f(f(x))) -> up(b) 249.23/132.37 down(g(x)) -> up(f(g(x))) 249.23/132.37 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(a)) -> f_flat(down(a)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(b)) -> f_flat(down(b)) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(a)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (129) SplitQDPProof (EQUIVALENT) 249.23/132.38 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (130) 249.23/132.38 Complex Obligation (AND) 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (131) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(a)) -> f_flat(down(a)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(b)) -> f_flat(down(b)) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(a)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (132) SemLabProof (SOUND) 249.23/132.38 We found the following model for the rules of the TRSs R and P. 249.23/132.38 Interpretation over the domain with elements from 0 to 1. 249.23/132.38 s_flat: 0 249.23/132.38 s: 0 249.23/132.38 a: 1 249.23/132.38 b: 0 249.23/132.38 down: 0 249.23/132.38 f: 0 249.23/132.38 fresh_constant: 0 249.23/132.38 up: 0 249.23/132.38 f_flat: 0 249.23/132.38 TOP: 0 249.23/132.38 g: 0 249.23/132.38 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (133) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(s.1(x0))) -> TOP.0(s_flat.0(down.1(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 TOP.0(up.0(f.0(s.1(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.1(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.1(a.)) -> f_flat.0(down.1(a.)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.1(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.0(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (134) DependencyGraphProof (EQUIVALENT) 249.23/132.38 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (135) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.1(a.)) -> f_flat.0(down.1(a.)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.1(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.0(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (136) UsableRulesReductionPairsProof (EQUIVALENT) 249.23/132.38 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. 249.23/132.38 249.23/132.38 No dependency pairs are removed. 249.23/132.38 249.23/132.38 The following rules are removed from R: 249.23/132.38 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 Used ordering: POLO with Polynomial interpretation [POLO]: 249.23/132.38 249.23/132.38 POL(TOP.0(x_1)) = x_1 249.23/132.38 POL(a.) = 0 249.23/132.38 POL(b.) = 0 249.23/132.38 POL(down.0(x_1)) = 1 + x_1 249.23/132.38 POL(down.1(x_1)) = 1 + x_1 249.23/132.38 POL(f.0(x_1)) = x_1 249.23/132.38 POL(f.1(x_1)) = x_1 249.23/132.38 POL(f_flat.0(x_1)) = x_1 249.23/132.38 POL(fresh_constant.) = 0 249.23/132.38 POL(g.0(x_1)) = x_1 249.23/132.38 POL(g.1(x_1)) = x_1 249.23/132.38 POL(s.0(x_1)) = 1 + x_1 249.23/132.38 POL(s.1(x_1)) = 1 + x_1 249.23/132.38 POL(s_flat.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.1(x_1)) = 1 + x_1 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (137) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.1(a.)) -> f_flat.0(down.1(a.)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.1(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.0(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (138) MRRProof (EQUIVALENT) 249.23/132.38 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. 249.23/132.38 249.23/132.38 249.23/132.38 Strictly oriented rules of the TRS R: 249.23/132.38 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.1(a.)) -> f_flat.0(down.1(a.)) 249.23/132.38 249.23/132.38 Used ordering: Polynomial interpretation [POLO]: 249.23/132.38 249.23/132.38 POL(TOP.0(x_1)) = x_1 249.23/132.38 POL(a.) = 0 249.23/132.38 POL(b.) = 0 249.23/132.38 POL(down.0(x_1)) = 1 + x_1 249.23/132.38 POL(down.1(x_1)) = x_1 249.23/132.38 POL(f.0(x_1)) = x_1 249.23/132.38 POL(f.1(x_1)) = x_1 249.23/132.38 POL(f_flat.0(x_1)) = x_1 249.23/132.38 POL(fresh_constant.) = 0 249.23/132.38 POL(g.0(x_1)) = x_1 249.23/132.38 POL(g.1(x_1)) = x_1 249.23/132.38 POL(s.0(x_1)) = 1 + x_1 249.23/132.38 POL(s.1(x_1)) = 1 + x_1 249.23/132.38 POL(s_flat.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.0(x_1)) = 1 + x_1 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (139) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.1(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.0(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (140) MRRProof (EQUIVALENT) 249.23/132.38 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. 249.23/132.38 249.23/132.38 249.23/132.38 Strictly oriented rules of the TRS R: 249.23/132.38 249.23/132.38 down.0(f.0(f.1(x))) -> up.0(b.) 249.23/132.38 249.23/132.38 Used ordering: Polynomial interpretation [POLO]: 249.23/132.38 249.23/132.38 POL(TOP.0(x_1)) = x_1 249.23/132.38 POL(b.) = 0 249.23/132.38 POL(down.0(x_1)) = x_1 249.23/132.38 POL(f.0(x_1)) = x_1 249.23/132.38 POL(f.1(x_1)) = 1 + x_1 249.23/132.38 POL(f_flat.0(x_1)) = x_1 249.23/132.38 POL(fresh_constant.) = 0 249.23/132.38 POL(g.0(x_1)) = x_1 249.23/132.38 POL(g.1(x_1)) = x_1 249.23/132.38 POL(s.0(x_1)) = x_1 249.23/132.38 POL(s.1(x_1)) = x_1 249.23/132.38 POL(s_flat.0(x_1)) = x_1 249.23/132.38 POL(up.0(x_1)) = x_1 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (141) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.0(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(b.)) -> f_flat.0(down.0(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.0(b.))) -> f_flat.0(down.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.1(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.0(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.0(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (142) PisEmptyProof (SOUND) 249.23/132.38 The TRS P is empty. Hence, there is no (P,Q,R) chain. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (143) 249.23/132.38 TRUE 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (144) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(b)) -> f_flat(down(b)) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(a)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (145) QReductionProof (EQUIVALENT) 249.23/132.38 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 249.23/132.38 249.23/132.38 down(f(a)) 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (146) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(b)) -> f_flat(down(b)) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (147) SplitQDPProof (EQUIVALENT) 249.23/132.38 We show in the first subproof that some pairs and rules can be removed, afterwards, we continue with the remaining DP-Problem 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (148) 249.23/132.38 Complex Obligation (AND) 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (149) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(b)) -> f_flat(down(b)) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(a)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (150) SemLabProof (SOUND) 249.23/132.38 We found the following model for the rules of the TRSs R and P. 249.23/132.38 Interpretation over the domain with elements from 0 to 1. 249.23/132.38 s_flat: 0 249.23/132.38 s: 0 249.23/132.38 a: 0 249.23/132.38 b: 1 249.23/132.38 down: 0 249.23/132.38 f: 0 249.23/132.38 fresh_constant: 0 249.23/132.38 up: 0 249.23/132.38 f_flat: 0 249.23/132.38 TOP: 0 249.23/132.38 g: 0 249.23/132.38 By semantic labelling [SEMLAB] we obtain the following labelled QDP problem. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (151) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(s.1(x0))) -> TOP.0(s_flat.0(down.1(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 TOP.0(up.0(f.0(s.1(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.1(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.1(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.1(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.1(b.)) -> f_flat.0(down.1(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.1(b.))) -> f_flat.0(down.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.0(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.1(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (152) DependencyGraphProof (EQUIVALENT) 249.23/132.38 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (153) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.1(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.1(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.1(b.)) -> f_flat.0(down.1(b.)) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.1(b.))) -> f_flat.0(down.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.0(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.1(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (154) MRRProof (EQUIVALENT) 249.23/132.38 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. 249.23/132.38 249.23/132.38 249.23/132.38 Strictly oriented rules of the TRS R: 249.23/132.38 249.23/132.38 down.0(f.1(b.)) -> f_flat.0(down.1(b.)) 249.23/132.38 s_flat.0(up.1(x_1)) -> up.0(s.1(x_1)) 249.23/132.38 249.23/132.38 Used ordering: Polynomial interpretation [POLO]: 249.23/132.38 249.23/132.38 POL(TOP.0(x_1)) = x_1 249.23/132.38 POL(b.) = 0 249.23/132.38 POL(down.0(x_1)) = 1 + x_1 249.23/132.38 POL(down.1(x_1)) = x_1 249.23/132.38 POL(f.0(x_1)) = x_1 249.23/132.38 POL(f.1(x_1)) = x_1 249.23/132.38 POL(f_flat.0(x_1)) = x_1 249.23/132.38 POL(fresh_constant.) = 0 249.23/132.38 POL(g.0(x_1)) = x_1 249.23/132.38 POL(g.1(x_1)) = x_1 249.23/132.38 POL(s.0(x_1)) = 1 + x_1 249.23/132.38 POL(s.1(x_1)) = x_1 249.23/132.38 POL(s_flat.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.1(x_1)) = 1 + x_1 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (155) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.1(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.1(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.1(b.))) -> f_flat.0(down.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.0(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.1(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (156) MRRProof (EQUIVALENT) 249.23/132.38 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. 249.23/132.38 249.23/132.38 249.23/132.38 Strictly oriented rules of the TRS R: 249.23/132.38 249.23/132.38 down.0(s.1(y2)) -> s_flat.0(down.1(y2)) 249.23/132.38 249.23/132.38 Used ordering: Polynomial interpretation [POLO]: 249.23/132.38 249.23/132.38 POL(TOP.0(x_1)) = x_1 249.23/132.38 POL(b.) = 0 249.23/132.38 POL(down.0(x_1)) = 1 + x_1 249.23/132.38 POL(down.1(x_1)) = x_1 249.23/132.38 POL(f.0(x_1)) = x_1 249.23/132.38 POL(f.1(x_1)) = x_1 249.23/132.38 POL(f_flat.0(x_1)) = x_1 249.23/132.38 POL(fresh_constant.) = 0 249.23/132.38 POL(g.0(x_1)) = x_1 249.23/132.38 POL(g.1(x_1)) = x_1 249.23/132.38 POL(s.0(x_1)) = x_1 249.23/132.38 POL(s.1(x_1)) = 1 + x_1 249.23/132.38 POL(s_flat.0(x_1)) = x_1 249.23/132.38 POL(up.0(x_1)) = 1 + x_1 249.23/132.38 POL(up.1(x_1)) = 1 + x_1 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (157) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP.0(up.0(s.0(x0))) -> TOP.0(s_flat.0(down.0(x0))) 249.23/132.38 TOP.0(up.0(f.0(s.0(x0)))) -> TOP.0(f_flat.0(s_flat.0(down.0(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x))) -> up.1(b.) 249.23/132.38 down.0(f.0(f.1(x))) -> up.1(b.) 249.23/132.38 down.0(g.0(x)) -> up.0(f.0(g.0(x))) 249.23/132.38 down.0(g.1(x)) -> up.0(f.0(g.1(x))) 249.23/132.38 down.0(s.0(y2)) -> s_flat.0(down.0(y2)) 249.23/132.38 down.0(f.0(s.0(y6))) -> f_flat.0(down.0(s.0(y6))) 249.23/132.38 down.0(f.0(s.1(y6))) -> f_flat.0(down.0(s.1(y6))) 249.23/132.38 down.0(f.0(g.0(f.0(y8)))) -> f_flat.0(down.0(g.0(f.0(y8)))) 249.23/132.38 down.0(f.0(g.0(f.1(y8)))) -> f_flat.0(down.0(g.0(f.1(y8)))) 249.23/132.38 down.0(f.0(g.0(g.0(y9)))) -> f_flat.0(down.0(g.0(g.0(y9)))) 249.23/132.38 down.0(f.0(g.0(g.1(y9)))) -> f_flat.0(down.0(g.0(g.1(y9)))) 249.23/132.38 down.0(f.0(g.0(s.0(y10)))) -> f_flat.0(down.0(g.0(s.0(y10)))) 249.23/132.38 down.0(f.0(g.0(s.1(y10)))) -> f_flat.0(down.0(g.0(s.1(y10)))) 249.23/132.38 down.0(f.0(g.1(b.))) -> f_flat.0(down.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) -> f_flat.0(down.0(g.0(fresh_constant.))) 249.23/132.38 s_flat.0(up.0(x_1)) -> up.0(s.0(x_1)) 249.23/132.38 f_flat.0(up.0(x_1)) -> up.0(f.0(x_1)) 249.23/132.38 f_flat.0(up.1(x_1)) -> up.0(f.1(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down.0(f.0(f.0(x0))) 249.23/132.38 down.0(f.0(f.1(x0))) 249.23/132.38 down.0(g.0(x0)) 249.23/132.38 down.0(g.1(x0)) 249.23/132.38 down.0(s.0(x0)) 249.23/132.38 down.0(s.1(x0)) 249.23/132.38 down.0(f.0(a.)) 249.23/132.38 down.0(f.0(s.0(x0))) 249.23/132.38 down.0(f.0(s.1(x0))) 249.23/132.38 down.0(f.1(b.)) 249.23/132.38 down.0(f.0(fresh_constant.)) 249.23/132.38 down.0(f.0(g.0(f.0(x0)))) 249.23/132.38 down.0(f.0(g.0(f.1(x0)))) 249.23/132.38 down.0(f.0(g.0(g.0(x0)))) 249.23/132.38 down.0(f.0(g.0(g.1(x0)))) 249.23/132.38 down.0(f.0(g.0(s.0(x0)))) 249.23/132.38 down.0(f.0(g.0(s.1(x0)))) 249.23/132.38 down.0(f.0(g.1(b.))) 249.23/132.38 down.0(f.0(g.0(fresh_constant.))) 249.23/132.38 f_flat.0(up.0(x0)) 249.23/132.38 f_flat.0(up.1(x0)) 249.23/132.38 s_flat.0(up.0(x0)) 249.23/132.38 s_flat.0(up.1(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (158) PisEmptyProof (SOUND) 249.23/132.38 The TRS P is empty. Hence, there is no (P,Q,R) chain. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (159) 249.23/132.38 TRUE 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (160) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(a)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all minimal (P,Q,R)-chains. 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (161) QReductionProof (EQUIVALENT) 249.23/132.38 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 249.23/132.38 249.23/132.38 down(f(a)) 249.23/132.38 249.23/132.38 249.23/132.38 ---------------------------------------- 249.23/132.38 249.23/132.38 (162) 249.23/132.38 Obligation: 249.23/132.38 Q DP problem: 249.23/132.38 The TRS P consists of the following rules: 249.23/132.38 249.23/132.38 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 249.23/132.38 TOP(up(f(s(x0)))) -> TOP(f_flat(s_flat(down(x0)))) 249.23/132.38 249.23/132.38 The TRS R consists of the following rules: 249.23/132.38 249.23/132.38 down(f(f(x))) -> up(b) 249.23/132.38 down(g(x)) -> up(f(g(x))) 249.23/132.38 down(s(y2)) -> s_flat(down(y2)) 249.23/132.38 down(f(s(y6))) -> f_flat(down(s(y6))) 249.23/132.38 down(f(g(f(y8)))) -> f_flat(down(g(f(y8)))) 249.23/132.38 down(f(g(g(y9)))) -> f_flat(down(g(g(y9)))) 249.23/132.38 down(f(g(s(y10)))) -> f_flat(down(g(s(y10)))) 249.23/132.38 down(f(g(b))) -> f_flat(down(g(b))) 249.23/132.38 down(f(g(fresh_constant))) -> f_flat(down(g(fresh_constant))) 249.23/132.38 s_flat(up(x_1)) -> up(s(x_1)) 249.23/132.38 f_flat(up(x_1)) -> up(f(x_1)) 249.23/132.38 249.23/132.38 The set Q consists of the following terms: 249.23/132.38 249.23/132.38 down(f(f(x0))) 249.23/132.38 down(g(x0)) 249.23/132.38 down(s(x0)) 249.23/132.38 down(f(s(x0))) 249.23/132.38 down(f(b)) 249.23/132.38 down(f(fresh_constant)) 249.23/132.38 down(f(g(f(x0)))) 249.23/132.38 down(f(g(g(x0)))) 249.23/132.38 down(f(g(s(x0)))) 249.23/132.38 down(f(g(b))) 249.23/132.38 down(f(g(fresh_constant))) 249.23/132.38 f_flat(up(x0)) 249.23/132.38 s_flat(up(x0)) 249.23/132.38 249.23/132.38 We have to consider all (P,Q,R)-chains. 249.59/132.48 EOF