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