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