167.87/114.66 MAYBE 167.87/114.67 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 167.87/114.67 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 167.87/114.67 167.87/114.67 167.87/114.67 Outermost Termination of the given OTRS could not be shown: 167.87/114.67 167.87/114.67 (0) OTRS 167.87/114.67 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 167.87/114.67 (2) QTRS 167.87/114.67 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 167.87/114.67 (4) QDP 167.87/114.67 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 167.87/114.67 (6) AND 167.87/114.67 (7) QDP 167.87/114.67 (8) UsableRulesProof [EQUIVALENT, 0 ms] 167.87/114.67 (9) QDP 167.87/114.67 (10) QReductionProof [EQUIVALENT, 0 ms] 167.87/114.67 (11) QDP 167.87/114.67 (12) MRRProof [EQUIVALENT, 23 ms] 167.87/114.67 (13) QDP 167.87/114.67 (14) PisEmptyProof [EQUIVALENT, 0 ms] 167.87/114.67 (15) YES 167.87/114.67 (16) QDP 167.87/114.67 (17) UsableRulesProof [EQUIVALENT, 0 ms] 167.87/114.67 (18) QDP 167.87/114.67 (19) QReductionProof [EQUIVALENT, 0 ms] 167.87/114.67 (20) QDP 167.87/114.67 (21) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (22) QDP 167.87/114.67 (23) UsableRulesProof [EQUIVALENT, 0 ms] 167.87/114.67 (24) QDP 167.87/114.67 (25) QReductionProof [EQUIVALENT, 0 ms] 167.87/114.67 (26) QDP 167.87/114.67 (27) Trivial-Transformation [SOUND, 0 ms] 167.87/114.67 (28) QTRS 167.87/114.67 (29) AAECC Innermost [EQUIVALENT, 3 ms] 167.87/114.67 (30) QTRS 167.87/114.67 (31) DependencyPairsProof [EQUIVALENT, 0 ms] 167.87/114.67 (32) QDP 167.87/114.67 (33) DependencyGraphProof [EQUIVALENT, 0 ms] 167.87/114.67 (34) AND 167.87/114.67 (35) QDP 167.87/114.67 (36) UsableRulesProof [EQUIVALENT, 0 ms] 167.87/114.67 (37) QDP 167.87/114.67 (38) QReductionProof [EQUIVALENT, 0 ms] 167.87/114.67 (39) QDP 167.87/114.67 (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] 167.87/114.67 (41) YES 167.87/114.67 (42) QDP 167.87/114.67 (43) UsableRulesProof [EQUIVALENT, 0 ms] 167.87/114.67 (44) QDP 167.87/114.67 (45) QReductionProof [EQUIVALENT, 0 ms] 167.87/114.67 (46) QDP 167.87/114.67 (47) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (48) QDP 167.87/114.67 (49) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (50) QDP 167.87/114.67 (51) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (52) QDP 167.87/114.67 (53) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (54) QDP 167.87/114.67 (55) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (56) QDP 167.87/114.67 (57) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (58) QDP 167.87/114.67 (59) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (60) QDP 167.87/114.67 (61) TransformationProof [EQUIVALENT, 0 ms] 167.87/114.67 (62) QDP 167.87/114.67 (63) MNOCProof [EQUIVALENT, 0 ms] 167.87/114.67 (64) QDP 167.87/114.67 (65) NonTerminationLoopProof [COMPLETE, 0 ms] 167.87/114.67 (66) NO 167.87/114.67 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (0) 167.87/114.67 Obligation: 167.87/114.67 Term rewrite system R: 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.67 id(s(x)) -> s(id(x)) 167.87/114.67 id(0) -> 0 167.87/114.67 167.87/114.67 167.87/114.67 167.87/114.67 Outermost Strategy. 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 167.87/114.67 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (2) 167.87/114.67 Obligation: 167.87/114.67 Q restricted rewrite system: 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 top(go_up(x)) -> top(reduce(x)) 167.87/114.67 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.67 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 check_f(result_f(x)) -> go_up(x) 167.87/114.67 check_id(result_id(x)) -> go_up(x) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.67 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.67 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.67 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.67 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (3) DependencyPairsProof (EQUIVALENT) 167.87/114.67 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (4) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 The TRS P consists of the following rules: 167.87/114.67 167.87/114.67 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.67 TOP(go_up(x)) -> REDUCE(x) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> REDEX_F(x_1, x_2, x_3) 167.87/114.67 REDUCE(id(x_1)) -> CHECK_ID(redex_id(x_1)) 167.87/114.67 REDUCE(id(x_1)) -> REDEX_ID(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_1(reduce(x_1), x_2, x_3) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_2(x_1, reduce(x_2), x_3) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> IN_F_3(x_1, x_2, reduce(x_3)) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> IN_ID_1(reduce(x_1)) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> REDUCE(x_1) 167.87/114.67 REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) 167.87/114.67 REDUCE(s(x_1)) -> REDUCE(x_1) 167.87/114.67 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 top(go_up(x)) -> top(reduce(x)) 167.87/114.67 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.67 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 check_f(result_f(x)) -> go_up(x) 167.87/114.67 check_id(result_id(x)) -> go_up(x) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.67 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.67 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.67 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.67 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (5) DependencyGraphProof (EQUIVALENT) 167.87/114.67 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (6) 167.87/114.67 Complex Obligation (AND) 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (7) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 The TRS P consists of the following rules: 167.87/114.67 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 167.87/114.67 REDUCE(id(x_1)) -> CHECK_ID(redex_id(x_1)) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> REDUCE(x_1) 167.87/114.67 REDUCE(s(x_1)) -> REDUCE(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 167.87/114.67 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 top(go_up(x)) -> top(reduce(x)) 167.87/114.67 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.67 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 check_f(result_f(x)) -> go_up(x) 167.87/114.67 check_id(result_id(x)) -> go_up(x) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.67 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.67 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.67 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.67 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (8) UsableRulesProof (EQUIVALENT) 167.87/114.67 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. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (9) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 The TRS P consists of the following rules: 167.87/114.67 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 167.87/114.67 REDUCE(id(x_1)) -> CHECK_ID(redex_id(x_1)) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> REDUCE(x_1) 167.87/114.67 REDUCE(s(x_1)) -> REDUCE(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 167.87/114.67 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (10) QReductionProof (EQUIVALENT) 167.87/114.67 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (11) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 The TRS P consists of the following rules: 167.87/114.67 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 167.87/114.67 REDUCE(id(x_1)) -> CHECK_ID(redex_id(x_1)) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> REDUCE(x_1) 167.87/114.67 REDUCE(s(x_1)) -> REDUCE(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 167.87/114.67 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (12) MRRProof (EQUIVALENT) 167.87/114.67 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. 167.87/114.67 167.87/114.67 Strictly oriented dependency pairs: 167.87/114.67 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_1) 167.87/114.67 REDUCE(f(x_1, x_2, x_3)) -> CHECK_F(redex_f(x_1, x_2, x_3)) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_2) 167.87/114.67 REDUCE(id(x_1)) -> CHECK_ID(redex_id(x_1)) 167.87/114.67 CHECK_ID(redex_id(x_1)) -> REDUCE(x_1) 167.87/114.67 REDUCE(s(x_1)) -> REDUCE(x_1) 167.87/114.67 CHECK_F(redex_f(x_1, x_2, x_3)) -> REDUCE(x_3) 167.87/114.67 167.87/114.67 Strictly oriented rules of the TRS R: 167.87/114.67 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 167.87/114.67 Used ordering: Polynomial interpretation [POLO]: 167.87/114.67 167.87/114.67 POL(0) = 0 167.87/114.67 POL(CHECK_F(x_1)) = 2 + x_1 167.87/114.67 POL(CHECK_ID(x_1)) = 2 + x_1 167.87/114.67 POL(REDUCE(x_1)) = 1 + 2*x_1 167.87/114.67 POL(f(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 167.87/114.67 POL(id(x_1)) = 2 + x_1 167.87/114.67 POL(redex_f(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 167.87/114.67 POL(redex_id(x_1)) = 2*x_1 167.87/114.67 POL(result_f(x_1)) = 2 + x_1 167.87/114.67 POL(result_id(x_1)) = x_1 167.87/114.67 POL(s(x_1)) = 2 + x_1 167.87/114.67 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (13) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 P is empty. 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (14) PisEmptyProof (EQUIVALENT) 167.87/114.67 The TRS P is empty. Hence, there is no (P,Q,R) chain. 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (15) 167.87/114.67 YES 167.87/114.67 167.87/114.67 ---------------------------------------- 167.87/114.67 167.87/114.67 (16) 167.87/114.67 Obligation: 167.87/114.67 Q DP problem: 167.87/114.67 The TRS P consists of the following rules: 167.87/114.67 167.87/114.67 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.67 167.87/114.67 The TRS R consists of the following rules: 167.87/114.67 167.87/114.67 top(go_up(x)) -> top(reduce(x)) 167.87/114.67 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.67 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.67 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.67 redex_id(0) -> result_id(0) 167.87/114.67 check_f(result_f(x)) -> go_up(x) 167.87/114.67 check_id(result_id(x)) -> go_up(x) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.67 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.67 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.67 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.67 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.67 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.67 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.67 167.87/114.67 The set Q consists of the following terms: 167.87/114.67 167.87/114.67 top(go_up(x0)) 167.87/114.67 reduce(f(x0, x1, x2)) 167.87/114.67 reduce(id(x0)) 167.87/114.67 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.67 redex_id(s(x0)) 167.87/114.67 redex_id(0) 167.87/114.67 check_f(result_f(x0)) 167.87/114.67 check_id(result_id(x0)) 167.87/114.67 check_f(redex_f(x0, x1, x2)) 167.87/114.67 check_id(redex_id(x0)) 167.87/114.67 reduce(s(x0)) 167.87/114.67 in_f_1(go_up(x0), x1, x2) 167.87/114.67 in_f_2(x0, go_up(x1), x2) 167.87/114.67 in_f_3(x0, x1, go_up(x2)) 167.87/114.67 in_s_1(go_up(x0)) 167.87/114.67 in_id_1(go_up(x0)) 167.87/114.67 167.87/114.67 We have to consider all minimal (P,Q,R)-chains. 167.87/114.67 ---------------------------------------- 167.87/114.68 167.87/114.68 (17) UsableRulesProof (EQUIVALENT) 167.87/114.68 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. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (18) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.68 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.68 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.68 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.68 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.68 redex_id(0) -> result_id(0) 167.87/114.68 check_id(result_id(x)) -> go_up(x) 167.87/114.68 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.68 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 check_f(result_f(x)) -> go_up(x) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.68 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 top(go_up(x0)) 167.87/114.68 reduce(f(x0, x1, x2)) 167.87/114.68 reduce(id(x0)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 redex_id(s(x0)) 167.87/114.68 redex_id(0) 167.87/114.68 check_f(result_f(x0)) 167.87/114.68 check_id(result_id(x0)) 167.87/114.68 check_f(redex_f(x0, x1, x2)) 167.87/114.68 check_id(redex_id(x0)) 167.87/114.68 reduce(s(x0)) 167.87/114.68 in_f_1(go_up(x0), x1, x2) 167.87/114.68 in_f_2(x0, go_up(x1), x2) 167.87/114.68 in_f_3(x0, x1, go_up(x2)) 167.87/114.68 in_s_1(go_up(x0)) 167.87/114.68 in_id_1(go_up(x0)) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (19) QReductionProof (EQUIVALENT) 167.87/114.68 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 167.87/114.68 167.87/114.68 top(go_up(x0)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (20) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.68 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.68 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.68 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.68 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.68 redex_id(0) -> result_id(0) 167.87/114.68 check_id(result_id(x)) -> go_up(x) 167.87/114.68 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.68 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 check_f(result_f(x)) -> go_up(x) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.68 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 reduce(f(x0, x1, x2)) 167.87/114.68 reduce(id(x0)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 redex_id(s(x0)) 167.87/114.68 redex_id(0) 167.87/114.68 check_f(result_f(x0)) 167.87/114.68 check_id(result_id(x0)) 167.87/114.68 check_f(redex_f(x0, x1, x2)) 167.87/114.68 check_id(redex_id(x0)) 167.87/114.68 reduce(s(x0)) 167.87/114.68 in_f_1(go_up(x0), x1, x2) 167.87/114.68 in_f_2(x0, go_up(x1), x2) 167.87/114.68 in_f_3(x0, x1, go_up(x2)) 167.87/114.68 in_s_1(go_up(x0)) 167.87/114.68 in_id_1(go_up(x0)) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (21) TransformationProof (EQUIVALENT) 167.87/114.68 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))),TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2)))) 167.87/114.68 (TOP(go_up(id(x0))) -> TOP(check_id(redex_id(x0))),TOP(go_up(id(x0))) -> TOP(check_id(redex_id(x0)))) 167.87/114.68 (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (22) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 TOP(go_up(f(x0, x1, x2))) -> TOP(check_f(redex_f(x0, x1, x2))) 167.87/114.68 TOP(go_up(id(x0))) -> TOP(check_id(redex_id(x0))) 167.87/114.68 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.68 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.68 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.68 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.68 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.68 redex_id(0) -> result_id(0) 167.87/114.68 check_id(result_id(x)) -> go_up(x) 167.87/114.68 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.68 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 check_f(result_f(x)) -> go_up(x) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.68 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 reduce(f(x0, x1, x2)) 167.87/114.68 reduce(id(x0)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 redex_id(s(x0)) 167.87/114.68 redex_id(0) 167.87/114.68 check_f(result_f(x0)) 167.87/114.68 check_id(result_id(x0)) 167.87/114.68 check_f(redex_f(x0, x1, x2)) 167.87/114.68 check_id(redex_id(x0)) 167.87/114.68 reduce(s(x0)) 167.87/114.68 in_f_1(go_up(x0), x1, x2) 167.87/114.68 in_f_2(x0, go_up(x1), x2) 167.87/114.68 in_f_3(x0, x1, go_up(x2)) 167.87/114.68 in_s_1(go_up(x0)) 167.87/114.68 in_id_1(go_up(x0)) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (23) UsableRulesProof (EQUIVALENT) 167.87/114.68 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. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (24) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.68 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.68 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.68 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.68 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.68 redex_id(0) -> result_id(0) 167.87/114.68 check_id(result_id(x)) -> go_up(x) 167.87/114.68 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.68 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 check_f(result_f(x)) -> go_up(x) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.68 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 top(go_up(x0)) 167.87/114.68 reduce(f(x0, x1, x2)) 167.87/114.68 reduce(id(x0)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 redex_id(s(x0)) 167.87/114.68 redex_id(0) 167.87/114.68 check_f(result_f(x0)) 167.87/114.68 check_id(result_id(x0)) 167.87/114.68 check_f(redex_f(x0, x1, x2)) 167.87/114.68 check_id(redex_id(x0)) 167.87/114.68 reduce(s(x0)) 167.87/114.68 in_f_1(go_up(x0), x1, x2) 167.87/114.68 in_f_2(x0, go_up(x1), x2) 167.87/114.68 in_f_3(x0, x1, go_up(x2)) 167.87/114.68 in_s_1(go_up(x0)) 167.87/114.68 in_id_1(go_up(x0)) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (25) QReductionProof (EQUIVALENT) 167.87/114.68 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 167.87/114.68 167.87/114.68 top(go_up(x0)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (26) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 TOP(go_up(x)) -> TOP(reduce(x)) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 reduce(f(x_1, x_2, x_3)) -> check_f(redex_f(x_1, x_2, x_3)) 167.87/114.68 reduce(id(x_1)) -> check_id(redex_id(x_1)) 167.87/114.68 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 167.87/114.68 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 167.87/114.68 redex_id(s(x)) -> result_id(s(id(x))) 167.87/114.68 redex_id(0) -> result_id(0) 167.87/114.68 check_id(result_id(x)) -> go_up(x) 167.87/114.68 check_id(redex_id(x_1)) -> in_id_1(reduce(x_1)) 167.87/114.68 in_id_1(go_up(x_1)) -> go_up(id(x_1)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> result_f(f(id(s(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 check_f(result_f(x)) -> go_up(x) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 167.87/114.68 check_f(redex_f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 167.87/114.68 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 reduce(f(x0, x1, x2)) 167.87/114.68 reduce(id(x0)) 167.87/114.68 redex_f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 redex_id(s(x0)) 167.87/114.68 redex_id(0) 167.87/114.68 check_f(result_f(x0)) 167.87/114.68 check_id(result_id(x0)) 167.87/114.68 check_f(redex_f(x0, x1, x2)) 167.87/114.68 check_id(redex_id(x0)) 167.87/114.68 reduce(s(x0)) 167.87/114.68 in_f_1(go_up(x0), x1, x2) 167.87/114.68 in_f_2(x0, go_up(x1), x2) 167.87/114.68 in_f_3(x0, x1, go_up(x2)) 167.87/114.68 in_s_1(go_up(x0)) 167.87/114.68 in_id_1(go_up(x0)) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (27) Trivial-Transformation (SOUND) 167.87/114.68 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (28) 167.87/114.68 Obligation: 167.87/114.68 Q restricted rewrite system: 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 Q is empty. 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (29) AAECC Innermost (EQUIVALENT) 167.87/114.68 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The TRS R 2 is 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The signature Sigma is {f_3} 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (30) 167.87/114.68 Obligation: 167.87/114.68 Q restricted rewrite system: 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (31) DependencyPairsProof (EQUIVALENT) 167.87/114.68 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (32) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> ID(s(s(s(s(s(s(s(s(x))))))))) 167.87/114.68 ID(s(x)) -> ID(x) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (33) DependencyGraphProof (EQUIVALENT) 167.87/114.68 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (34) 167.87/114.68 Complex Obligation (AND) 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (35) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 ID(s(x)) -> ID(x) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (36) UsableRulesProof (EQUIVALENT) 167.87/114.68 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. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (37) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 ID(s(x)) -> ID(x) 167.87/114.68 167.87/114.68 R is empty. 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (38) QReductionProof (EQUIVALENT) 167.87/114.68 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (39) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 ID(s(x)) -> ID(x) 167.87/114.68 167.87/114.68 R is empty. 167.87/114.68 Q is empty. 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (40) QDPSizeChangeProof (EQUIVALENT) 167.87/114.68 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. 167.87/114.68 167.87/114.68 From the DPs we obtained the following set of size-change graphs: 167.87/114.68 *ID(s(x)) -> ID(x) 167.87/114.68 The graph contains the following edges 1 > 1 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (41) 167.87/114.68 YES 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (42) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x)))))))), y, y) -> f(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (43) UsableRulesProof (EQUIVALENT) 167.87/114.68 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. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (44) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (45) QReductionProof (EQUIVALENT) 167.87/114.68 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 167.87/114.68 167.87/114.68 f(s(s(s(s(s(s(s(s(x0)))))))), x1, x1) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (46) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(id(s(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (47) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(id(s(s(s(s(s(s(s(s(x))))))))), y, y) at position [0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(id(s(s(s(s(s(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(id(s(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (48) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(id(s(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (49) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(id(s(s(s(s(s(s(s(x))))))))), y, y) at position [0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(id(s(s(s(s(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(id(s(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (50) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(id(s(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (51) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(id(s(s(s(s(s(s(x))))))))), y, y) at position [0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(id(s(s(s(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(id(s(s(s(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (52) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(id(s(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (53) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(id(s(s(s(s(s(x))))))))), y, y) at position [0,0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(id(s(s(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(id(s(s(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (54) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(id(s(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (55) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(id(s(s(s(s(x))))))))), y, y) at position [0,0,0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(id(s(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(id(s(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (56) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(id(s(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (57) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(id(s(s(s(x))))))))), y, y) at position [0,0,0,0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(id(s(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(id(s(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (58) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(id(s(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (59) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(id(s(s(x))))))))), y, y) at position [0,0,0,0,0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(id(s(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(id(s(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (60) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(id(s(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (61) TransformationProof (EQUIVALENT) 167.87/114.68 By rewriting [LPAR04] the rule F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(id(s(x))))))))), y, y) at position [0,0,0,0,0,0,0,0] we obtained the following new rules [LPAR04]: 167.87/114.68 167.87/114.68 (F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(s(id(x))))))))), y, y),F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(s(id(x))))))))), y, y)) 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (62) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(s(id(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 The set Q consists of the following terms: 167.87/114.68 167.87/114.68 id(s(x0)) 167.87/114.68 id(0) 167.87/114.68 167.87/114.68 We have to consider all minimal (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (63) MNOCProof (EQUIVALENT) 167.87/114.68 We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (64) 167.87/114.68 Obligation: 167.87/114.68 Q DP problem: 167.87/114.68 The TRS P consists of the following rules: 167.87/114.68 167.87/114.68 F(s(s(s(s(s(s(s(s(x)))))))), y, y) -> F(s(s(s(s(s(s(s(s(id(x))))))))), y, y) 167.87/114.68 167.87/114.68 The TRS R consists of the following rules: 167.87/114.68 167.87/114.68 id(s(x)) -> s(id(x)) 167.87/114.68 id(0) -> 0 167.87/114.68 167.87/114.68 Q is empty. 167.87/114.68 We have to consider all (P,Q,R)-chains. 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (65) NonTerminationLoopProof (COMPLETE) 167.87/114.68 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 167.87/114.68 Found a loop by semiunifying a rule from P directly. 167.87/114.68 167.87/114.68 s = F(s(s(s(s(s(s(s(s(x)))))))), y, y) evaluates to t =F(s(s(s(s(s(s(s(s(id(x))))))))), y, y) 167.87/114.68 167.87/114.68 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 167.87/114.68 * Matcher: [x / id(x)] 167.87/114.68 * Semiunifier: [ ] 167.87/114.68 167.87/114.68 -------------------------------------------------------------------------------- 167.87/114.68 Rewriting sequence 167.87/114.68 167.87/114.68 The DP semiunifies directly so there is only one rewrite step from F(s(s(s(s(s(s(s(s(x)))))))), y, y) to F(s(s(s(s(s(s(s(s(id(x))))))))), y, y). 167.87/114.68 167.87/114.68 167.87/114.68 167.87/114.68 167.87/114.68 ---------------------------------------- 167.87/114.68 167.87/114.68 (66) 167.87/114.68 NO 167.95/114.72 EOF