186.57/64.46 MAYBE 186.57/64.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 186.57/64.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 186.57/64.47 186.57/64.47 186.57/64.47 Outermost Termination of the given OTRS could not be shown: 186.57/64.47 186.57/64.47 (0) OTRS 186.57/64.47 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 186.57/64.47 (2) QTRS 186.57/64.47 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 186.57/64.47 (4) QDP 186.57/64.47 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 186.57/64.47 (6) AND 186.57/64.47 (7) QDP 186.57/64.47 (8) UsableRulesProof [EQUIVALENT, 0 ms] 186.57/64.47 (9) QDP 186.57/64.47 (10) QReductionProof [EQUIVALENT, 0 ms] 186.57/64.47 (11) QDP 186.57/64.47 (12) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 186.57/64.47 (13) QDP 186.57/64.47 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 186.57/64.47 (15) TRUE 186.57/64.47 (16) QDP 186.57/64.47 (17) UsableRulesProof [EQUIVALENT, 0 ms] 186.57/64.47 (18) QDP 186.57/64.47 (19) QReductionProof [EQUIVALENT, 0 ms] 186.57/64.47 (20) QDP 186.57/64.47 (21) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (22) QDP 186.57/64.47 (23) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (24) QDP 186.57/64.47 (25) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (26) QDP 186.57/64.47 (27) QDPOrderProof [EQUIVALENT, 5 ms] 186.57/64.47 (28) QDP 186.57/64.47 (29) UsableRulesProof [EQUIVALENT, 0 ms] 186.57/64.47 (30) QDP 186.57/64.47 (31) QReductionProof [EQUIVALENT, 0 ms] 186.57/64.47 (32) QDP 186.57/64.47 (33) Trivial-Transformation [SOUND, 0 ms] 186.57/64.47 (34) QTRS 186.57/64.47 (35) DependencyPairsProof [EQUIVALENT, 0 ms] 186.57/64.47 (36) QDP 186.57/64.47 (37) DependencyGraphProof [EQUIVALENT, 0 ms] 186.57/64.47 (38) QDP 186.57/64.47 (39) UsableRulesProof [EQUIVALENT, 1 ms] 186.57/64.47 (40) QDP 186.57/64.47 (41) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (42) QDP 186.57/64.47 (43) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (44) QDP 186.57/64.47 (45) NonTerminationLoopProof [COMPLETE, 0 ms] 186.57/64.47 (46) NO 186.57/64.47 (47) Raffelsieper-Zantema-Transformation [SOUND, 53 ms] 186.57/64.47 (48) QTRS 186.57/64.47 (49) DependencyPairsProof [EQUIVALENT, 0 ms] 186.57/64.47 (50) QDP 186.57/64.47 (51) DependencyGraphProof [EQUIVALENT, 0 ms] 186.57/64.47 (52) AND 186.57/64.47 (53) QDP 186.57/64.47 (54) UsableRulesProof [EQUIVALENT, 0 ms] 186.57/64.47 (55) QDP 186.57/64.47 (56) QDPSizeChangeProof [EQUIVALENT, 0 ms] 186.57/64.47 (57) YES 186.57/64.47 (58) QDP 186.57/64.47 (59) TransformationProof [EQUIVALENT, 0 ms] 186.57/64.47 (60) QDP 186.57/64.47 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 186.57/64.47 (62) QDP 186.57/64.47 (63) QDPOrderProof [EQUIVALENT, 30 ms] 186.57/64.47 (64) QDP 186.57/64.47 (65) QDPOrderProof [EQUIVALENT, 309 ms] 186.57/64.47 (66) QDP 186.57/64.47 186.57/64.47 186.57/64.47 ---------------------------------------- 186.57/64.47 186.57/64.47 (0) 186.57/64.47 Obligation: 186.57/64.47 Term rewrite system R: 186.57/64.47 The TRS R consists of the following rules: 186.57/64.47 186.57/64.47 cons(x, cons(y, cons(z, xs))) -> big 186.57/64.47 inf(x) -> cons(x, inf(s(x))) 186.57/64.47 186.57/64.47 186.57/64.47 186.57/64.47 Outermost Strategy. 186.57/64.47 186.57/64.47 ---------------------------------------- 186.57/64.47 186.57/64.47 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 186.57/64.47 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 186.57/64.47 ---------------------------------------- 186.57/64.47 186.57/64.47 (2) 186.57/64.47 Obligation: 186.57/64.47 Q restricted rewrite system: 186.57/64.47 The TRS R consists of the following rules: 186.57/64.47 186.57/64.47 top(go_up(x)) -> top(reduce(x)) 186.57/64.47 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.47 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.47 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.47 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.47 check_cons(result_cons(x)) -> go_up(x) 186.57/64.47 check_inf(result_inf(x)) -> go_up(x) 186.57/64.47 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.47 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.47 check_inf(redex_inf(x_1)) -> in_inf_1(reduce(x_1)) 186.57/64.47 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.47 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.47 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.47 in_inf_1(go_up(x_1)) -> go_up(inf(x_1)) 186.57/64.47 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.47 186.57/64.47 The set Q consists of the following terms: 186.57/64.47 186.57/64.47 top(go_up(x0)) 186.57/64.47 reduce(cons(x0, x1)) 186.57/64.47 reduce(inf(x0)) 186.57/64.47 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.47 redex_inf(x0) 186.57/64.47 check_cons(result_cons(x0)) 186.57/64.47 check_inf(result_inf(x0)) 186.57/64.47 check_cons(redex_cons(x0, x1)) 186.57/64.47 reduce(s(x0)) 186.57/64.47 in_cons_1(go_up(x0), x1) 186.57/64.47 in_cons_2(x0, go_up(x1)) 186.57/64.47 in_inf_1(go_up(x0)) 186.57/64.47 in_s_1(go_up(x0)) 186.57/64.47 186.57/64.47 186.57/64.47 ---------------------------------------- 186.57/64.47 186.57/64.47 (3) DependencyPairsProof (EQUIVALENT) 186.57/64.47 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 186.57/64.47 ---------------------------------------- 186.57/64.47 186.57/64.47 (4) 186.57/64.47 Obligation: 186.57/64.47 Q DP problem: 186.57/64.47 The TRS P consists of the following rules: 186.57/64.47 186.57/64.47 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.47 TOP(go_up(x)) -> REDUCE(x) 186.57/64.47 REDUCE(cons(x_1, x_2)) -> CHECK_CONS(redex_cons(x_1, x_2)) 186.57/64.47 REDUCE(cons(x_1, x_2)) -> REDEX_CONS(x_1, x_2) 186.57/64.47 REDUCE(inf(x_1)) -> CHECK_INF(redex_inf(x_1)) 186.57/64.47 REDUCE(inf(x_1)) -> REDEX_INF(x_1) 186.57/64.47 CHECK_CONS(redex_cons(x_1, x_2)) -> IN_CONS_1(reduce(x_1), x_2) 186.57/64.47 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_1) 186.57/64.47 CHECK_CONS(redex_cons(x_1, x_2)) -> IN_CONS_2(x_1, reduce(x_2)) 186.57/64.47 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_2) 186.57/64.47 CHECK_INF(redex_inf(x_1)) -> IN_INF_1(reduce(x_1)) 186.57/64.47 CHECK_INF(redex_inf(x_1)) -> REDUCE(x_1) 186.57/64.47 REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) 186.57/64.47 REDUCE(s(x_1)) -> REDUCE(x_1) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 top(go_up(x)) -> top(reduce(x)) 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 check_inf(redex_inf(x_1)) -> in_inf_1(reduce(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_inf_1(go_up(x_1)) -> go_up(inf(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (5) DependencyGraphProof (EQUIVALENT) 186.57/64.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 9 less nodes. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (6) 186.57/64.48 Complex Obligation (AND) 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (7) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_1) 186.57/64.48 REDUCE(cons(x_1, x_2)) -> CHECK_CONS(redex_cons(x_1, x_2)) 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_2) 186.57/64.48 REDUCE(s(x_1)) -> REDUCE(x_1) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 top(go_up(x)) -> top(reduce(x)) 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 check_inf(redex_inf(x_1)) -> in_inf_1(reduce(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_inf_1(go_up(x_1)) -> go_up(inf(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (8) UsableRulesProof (EQUIVALENT) 186.57/64.48 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. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (9) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_1) 186.57/64.48 REDUCE(cons(x_1, x_2)) -> CHECK_CONS(redex_cons(x_1, x_2)) 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_2) 186.57/64.48 REDUCE(s(x_1)) -> REDUCE(x_1) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (10) QReductionProof (EQUIVALENT) 186.57/64.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (11) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_1) 186.57/64.48 REDUCE(cons(x_1, x_2)) -> CHECK_CONS(redex_cons(x_1, x_2)) 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_2) 186.57/64.48 REDUCE(s(x_1)) -> REDUCE(x_1) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (12) UsableRulesReductionPairsProof (EQUIVALENT) 186.57/64.48 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. 186.57/64.48 186.57/64.48 The following dependency pairs can be deleted: 186.57/64.48 186.57/64.48 REDUCE(cons(x_1, x_2)) -> CHECK_CONS(redex_cons(x_1, x_2)) 186.57/64.48 REDUCE(s(x_1)) -> REDUCE(x_1) 186.57/64.48 The following rules are removed from R: 186.57/64.48 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 Used ordering: POLO with Polynomial interpretation [POLO]: 186.57/64.48 186.57/64.48 POL(CHECK_CONS(x_1)) = 2*x_1 186.57/64.48 POL(REDUCE(x_1)) = 2*x_1 186.57/64.48 POL(big) = 0 186.57/64.48 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 186.57/64.48 POL(redex_cons(x_1, x_2)) = 2*x_1 + x_2 186.57/64.48 POL(result_cons(x_1)) = x_1 186.57/64.48 POL(s(x_1)) = x_1 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (13) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_1) 186.57/64.48 CHECK_CONS(redex_cons(x_1, x_2)) -> REDUCE(x_2) 186.57/64.48 186.57/64.48 R is empty. 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (14) DependencyGraphProof (EQUIVALENT) 186.57/64.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (15) 186.57/64.48 TRUE 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (16) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 top(go_up(x)) -> top(reduce(x)) 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 check_inf(redex_inf(x_1)) -> in_inf_1(reduce(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_inf_1(go_up(x_1)) -> go_up(inf(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (17) UsableRulesProof (EQUIVALENT) 186.57/64.48 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. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (18) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (19) QReductionProof (EQUIVALENT) 186.57/64.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (20) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (21) TransformationProof (EQUIVALENT) 186.57/64.48 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1))),TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1)))) 186.57/64.48 (TOP(go_up(inf(x0))) -> TOP(check_inf(redex_inf(x0))),TOP(go_up(inf(x0))) -> TOP(check_inf(redex_inf(x0)))) 186.57/64.48 (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (22) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1))) 186.57/64.48 TOP(go_up(inf(x0))) -> TOP(check_inf(redex_inf(x0))) 186.57/64.48 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (23) TransformationProof (EQUIVALENT) 186.57/64.48 By rewriting [LPAR04] the rule TOP(go_up(inf(x0))) -> TOP(check_inf(redex_inf(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (TOP(go_up(inf(x0))) -> TOP(check_inf(result_inf(cons(x0, inf(s(x0)))))),TOP(go_up(inf(x0))) -> TOP(check_inf(result_inf(cons(x0, inf(s(x0))))))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (24) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1))) 186.57/64.48 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 186.57/64.48 TOP(go_up(inf(x0))) -> TOP(check_inf(result_inf(cons(x0, inf(s(x0)))))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (25) TransformationProof (EQUIVALENT) 186.57/64.48 By rewriting [LPAR04] the rule TOP(go_up(inf(x0))) -> TOP(check_inf(result_inf(cons(x0, inf(s(x0)))))) at position [0] we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (TOP(go_up(inf(x0))) -> TOP(go_up(cons(x0, inf(s(x0))))),TOP(go_up(inf(x0))) -> TOP(go_up(cons(x0, inf(s(x0)))))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (26) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1))) 186.57/64.48 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 186.57/64.48 TOP(go_up(inf(x0))) -> TOP(go_up(cons(x0, inf(s(x0))))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (27) QDPOrderProof (EQUIVALENT) 186.57/64.48 We use the reduction pair processor [LPAR04,JAR06]. 186.57/64.48 186.57/64.48 186.57/64.48 The following pairs can be oriented strictly and are deleted. 186.57/64.48 186.57/64.48 TOP(go_up(inf(x0))) -> TOP(go_up(cons(x0, inf(s(x0))))) 186.57/64.48 The remaining pairs can at least be oriented weakly. 186.57/64.48 Used ordering: Polynomial interpretation [POLO]: 186.57/64.48 186.57/64.48 POL(TOP(x_1)) = x_1 186.57/64.48 POL(big) = 0 186.57/64.48 POL(check_cons(x_1)) = x_1 186.57/64.48 POL(check_inf(x_1)) = 1 186.57/64.48 POL(cons(x_1, x_2)) = 0 186.57/64.48 POL(go_up(x_1)) = x_1 186.57/64.48 POL(in_cons_1(x_1, x_2)) = 0 186.57/64.48 POL(in_cons_2(x_1, x_2)) = 0 186.57/64.48 POL(in_s_1(x_1)) = 0 186.57/64.48 POL(inf(x_1)) = 1 186.57/64.48 POL(redex_cons(x_1, x_2)) = 0 186.57/64.48 POL(redex_inf(x_1)) = x_1 186.57/64.48 POL(reduce(x_1)) = 0 186.57/64.48 POL(result_cons(x_1)) = x_1 186.57/64.48 POL(result_inf(x_1)) = 1 186.57/64.48 POL(s(x_1)) = 0 186.57/64.48 186.57/64.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 186.57/64.48 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (28) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(cons(x0, x1))) -> TOP(check_cons(redex_cons(x0, x1))) 186.57/64.48 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (29) UsableRulesProof (EQUIVALENT) 186.57/64.48 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. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (30) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (31) QReductionProof (EQUIVALENT) 186.57/64.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 186.57/64.48 186.57/64.48 top(go_up(x0)) 186.57/64.48 in_inf_1(go_up(x0)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (32) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(go_up(x)) -> TOP(reduce(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 reduce(cons(x_1, x_2)) -> check_cons(redex_cons(x_1, x_2)) 186.57/64.48 reduce(inf(x_1)) -> check_inf(redex_inf(x_1)) 186.57/64.48 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 186.57/64.48 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 186.57/64.48 redex_inf(x) -> result_inf(cons(x, inf(s(x)))) 186.57/64.48 check_inf(result_inf(x)) -> go_up(x) 186.57/64.48 redex_cons(x, cons(y, cons(z, xs))) -> result_cons(big) 186.57/64.48 check_cons(result_cons(x)) -> go_up(x) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_1(reduce(x_1), x_2) 186.57/64.48 check_cons(redex_cons(x_1, x_2)) -> in_cons_2(x_1, reduce(x_2)) 186.57/64.48 in_cons_2(x_1, go_up(x_2)) -> go_up(cons(x_1, x_2)) 186.57/64.48 in_cons_1(go_up(x_1), x_2) -> go_up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 The set Q consists of the following terms: 186.57/64.48 186.57/64.48 reduce(cons(x0, x1)) 186.57/64.48 reduce(inf(x0)) 186.57/64.48 redex_cons(x0, cons(x1, cons(x2, x3))) 186.57/64.48 redex_inf(x0) 186.57/64.48 check_cons(result_cons(x0)) 186.57/64.48 check_inf(result_inf(x0)) 186.57/64.48 check_cons(redex_cons(x0, x1)) 186.57/64.48 reduce(s(x0)) 186.57/64.48 in_cons_1(go_up(x0), x1) 186.57/64.48 in_cons_2(x0, go_up(x1)) 186.57/64.48 in_s_1(go_up(x0)) 186.57/64.48 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (33) Trivial-Transformation (SOUND) 186.57/64.48 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (34) 186.57/64.48 Obligation: 186.57/64.48 Q restricted rewrite system: 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 cons(x, cons(y, cons(z, xs))) -> big 186.57/64.48 inf(x) -> cons(x, inf(s(x))) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (35) DependencyPairsProof (EQUIVALENT) 186.57/64.48 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (36) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 INF(x) -> CONS(x, inf(s(x))) 186.57/64.48 INF(x) -> INF(s(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 cons(x, cons(y, cons(z, xs))) -> big 186.57/64.48 inf(x) -> cons(x, inf(s(x))) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (37) DependencyGraphProof (EQUIVALENT) 186.57/64.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (38) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 INF(x) -> INF(s(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 cons(x, cons(y, cons(z, xs))) -> big 186.57/64.48 inf(x) -> cons(x, inf(s(x))) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (39) UsableRulesProof (EQUIVALENT) 186.57/64.48 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (40) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 INF(x) -> INF(s(x)) 186.57/64.48 186.57/64.48 R is empty. 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (41) TransformationProof (EQUIVALENT) 186.57/64.48 By instantiating [LPAR04] the rule INF(x) -> INF(s(x)) we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (INF(s(z0)) -> INF(s(s(z0))),INF(s(z0)) -> INF(s(s(z0)))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (42) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 INF(s(z0)) -> INF(s(s(z0))) 186.57/64.48 186.57/64.48 R is empty. 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (43) TransformationProof (EQUIVALENT) 186.57/64.48 By instantiating [LPAR04] the rule INF(s(z0)) -> INF(s(s(z0))) we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (INF(s(s(z0))) -> INF(s(s(s(z0)))),INF(s(s(z0))) -> INF(s(s(s(z0))))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (44) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 INF(s(s(z0))) -> INF(s(s(s(z0)))) 186.57/64.48 186.57/64.48 R is empty. 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (45) NonTerminationLoopProof (COMPLETE) 186.57/64.48 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 186.57/64.48 Found a loop by semiunifying a rule from P directly. 186.57/64.48 186.57/64.48 s = INF(s(s(z0))) evaluates to t =INF(s(s(s(z0)))) 186.57/64.48 186.57/64.48 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 186.57/64.48 * Matcher: [z0 / s(z0)] 186.57/64.48 * Semiunifier: [ ] 186.57/64.48 186.57/64.48 -------------------------------------------------------------------------------- 186.57/64.48 Rewriting sequence 186.57/64.48 186.57/64.48 The DP semiunifies directly so there is only one rewrite step from INF(s(s(z0))) to INF(s(s(s(z0)))). 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (46) 186.57/64.48 NO 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (47) Raffelsieper-Zantema-Transformation (SOUND) 186.57/64.48 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (48) 186.57/64.48 Obligation: 186.57/64.48 Q restricted rewrite system: 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (49) DependencyPairsProof (EQUIVALENT) 186.57/64.48 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (50) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(x)) -> TOP(down(x)) 186.57/64.48 TOP(up(x)) -> DOWN(x) 186.57/64.48 DOWN(s(y3)) -> S_FLAT(down(y3)) 186.57/64.48 DOWN(s(y3)) -> DOWN(y3) 186.57/64.48 DOWN(cons(y32, big)) -> CONS_FLAT(down(y32), block(big)) 186.57/64.48 DOWN(cons(y32, big)) -> DOWN(y32) 186.57/64.48 DOWN(cons(y32, big)) -> CONS_FLAT(block(y32), down(big)) 186.57/64.48 DOWN(cons(y32, big)) -> DOWN(big) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> CONS_FLAT(down(y37), block(inf(y38))) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> DOWN(y37) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> CONS_FLAT(block(y37), down(inf(y38))) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> DOWN(inf(y38)) 186.57/64.48 DOWN(cons(y48, s(y49))) -> CONS_FLAT(down(y48), block(s(y49))) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(y48) 186.57/64.48 DOWN(cons(y48, s(y49))) -> CONS_FLAT(block(y48), down(s(y49))) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(s(y49)) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> CONS_FLAT(down(y59), block(fresh_constant)) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> DOWN(y59) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> CONS_FLAT(block(y59), down(fresh_constant)) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> DOWN(fresh_constant) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> CONS_FLAT(down(y15), block(cons(y162, big))) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> CONS_FLAT(block(y15), down(cons(y162, big))) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(cons(y162, big)) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> CONS_FLAT(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> CONS_FLAT(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(cons(y167, inf(y168))) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> CONS_FLAT(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> CONS_FLAT(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(cons(y178, s(y179))) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> CONS_FLAT(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> CONS_FLAT(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(cons(y189, fresh_constant)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (51) DependencyGraphProof (EQUIVALENT) 186.57/64.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 21 less nodes. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (52) 186.57/64.48 Complex Obligation (AND) 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (53) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 DOWN(cons(y32, big)) -> DOWN(y32) 186.57/64.48 DOWN(s(y3)) -> DOWN(y3) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> DOWN(y37) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(y48) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(s(y49)) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> DOWN(y59) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(cons(y162, big)) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(cons(y167, inf(y168))) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(cons(y178, s(y179))) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(cons(y189, fresh_constant)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (54) UsableRulesProof (EQUIVALENT) 186.57/64.48 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (55) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 DOWN(cons(y32, big)) -> DOWN(y32) 186.57/64.48 DOWN(s(y3)) -> DOWN(y3) 186.57/64.48 DOWN(cons(y37, inf(y38))) -> DOWN(y37) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(y48) 186.57/64.48 DOWN(cons(y48, s(y49))) -> DOWN(s(y49)) 186.57/64.48 DOWN(cons(y59, fresh_constant)) -> DOWN(y59) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y162, big))) -> DOWN(cons(y162, big)) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(cons(y167, inf(y168))) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(cons(y178, s(y179))) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(y15) 186.57/64.48 DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(cons(y189, fresh_constant)) 186.57/64.48 186.57/64.48 R is empty. 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (56) QDPSizeChangeProof (EQUIVALENT) 186.57/64.48 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. 186.57/64.48 186.57/64.48 From the DPs we obtained the following set of size-change graphs: 186.57/64.48 *DOWN(cons(y15, cons(y162, big))) -> DOWN(cons(y162, big)) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y48, s(y49))) -> DOWN(s(y49)) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(cons(y167, inf(y168))) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(cons(y178, s(y179))) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(cons(y189, fresh_constant)) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(s(y3)) -> DOWN(y3) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y32, big)) -> DOWN(y32) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y37, inf(y38))) -> DOWN(y37) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y48, s(y49))) -> DOWN(y48) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y59, fresh_constant)) -> DOWN(y59) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y162, big))) -> DOWN(y15) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y167, inf(y168)))) -> DOWN(y15) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y178, s(y179)))) -> DOWN(y15) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 *DOWN(cons(y15, cons(y189, fresh_constant))) -> DOWN(y15) 186.57/64.48 The graph contains the following edges 1 > 1 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (57) 186.57/64.48 YES 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (58) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(x)) -> TOP(down(x)) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (59) TransformationProof (EQUIVALENT) 186.57/64.48 By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]: 186.57/64.48 186.57/64.48 (TOP(up(cons(x0, cons(x1, cons(x2, x3))))) -> TOP(up(big)),TOP(up(cons(x0, cons(x1, cons(x2, x3))))) -> TOP(up(big))) 186.57/64.48 (TOP(up(inf(x0))) -> TOP(up(cons(x0, inf(s(x0))))),TOP(up(inf(x0))) -> TOP(up(cons(x0, inf(s(x0)))))) 186.57/64.48 (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0)))) 186.57/64.48 (TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big))),TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big)))) 186.57/64.48 (TOP(up(cons(x0, big))) -> TOP(cons_flat(block(x0), down(big))),TOP(up(cons(x0, big))) -> TOP(cons_flat(block(x0), down(big)))) 186.57/64.48 (TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1)))),TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1))))) 186.57/64.48 (TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1)))),TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1))))) 186.57/64.48 (TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1)))),TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1))))) 186.57/64.48 (TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1)))),TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1))))) 186.57/64.48 (TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant))),TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant)))) 186.57/64.48 (TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(block(x0), down(fresh_constant))),TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(block(x0), down(fresh_constant)))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big)))),TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big)))),TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2))))),TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2)))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2))))),TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2)))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2))))),TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2)))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2))))),TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2)))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant)))),TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant))))) 186.57/64.48 (TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant)))),TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant))))) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (60) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(cons(x0, cons(x1, cons(x2, x3))))) -> TOP(up(big)) 186.57/64.48 TOP(up(inf(x0))) -> TOP(up(cons(x0, inf(s(x0))))) 186.57/64.48 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 186.57/64.48 TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big))) 186.57/64.48 TOP(up(cons(x0, big))) -> TOP(cons_flat(block(x0), down(big))) 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1)))) 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1)))) 186.57/64.48 TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant))) 186.57/64.48 TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(block(x0), down(fresh_constant))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant)))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (61) DependencyGraphProof (EQUIVALENT) 186.57/64.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (62) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(inf(x0))) -> TOP(up(cons(x0, inf(s(x0))))) 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1)))) 186.57/64.48 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 186.57/64.48 TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big))) 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1)))) 186.57/64.48 TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant)))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (63) QDPOrderProof (EQUIVALENT) 186.57/64.48 We use the reduction pair processor [LPAR04,JAR06]. 186.57/64.48 186.57/64.48 186.57/64.48 The following pairs can be oriented strictly and are deleted. 186.57/64.48 186.57/64.48 TOP(up(inf(x0))) -> TOP(up(cons(x0, inf(s(x0))))) 186.57/64.48 The remaining pairs can at least be oriented weakly. 186.57/64.48 Used ordering: Polynomial interpretation [POLO]: 186.57/64.48 186.57/64.48 POL(TOP(x_1)) = x_1 186.57/64.48 POL(big) = 0 186.57/64.48 POL(block(x_1)) = 0 186.57/64.48 POL(cons(x_1, x_2)) = 0 186.57/64.48 POL(cons_flat(x_1, x_2)) = 0 186.57/64.48 POL(down(x_1)) = 0 186.57/64.48 POL(fresh_constant) = 0 186.57/64.48 POL(inf(x_1)) = 1 186.57/64.48 POL(s(x_1)) = 0 186.57/64.48 POL(s_flat(x_1)) = 0 186.57/64.48 POL(up(x_1)) = x_1 186.57/64.48 186.57/64.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 186.57/64.48 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (64) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1)))) 186.57/64.48 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 186.57/64.48 TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big))) 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1)))) 186.57/64.48 TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant)))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (65) QDPOrderProof (EQUIVALENT) 186.57/64.48 We use the reduction pair processor [LPAR04,JAR06]. 186.57/64.48 186.57/64.48 186.57/64.48 The following pairs can be oriented strictly and are deleted. 186.57/64.48 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(block(x0), down(inf(x1)))) 186.57/64.48 The remaining pairs can at least be oriented weakly. 186.57/64.48 Used ordering: Matrix interpretation [MATRO]: 186.57/64.48 186.57/64.48 Non-tuple symbols: 186.57/64.48 <<< 186.57/64.48 M( s_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( s_flat_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( block_1(x_1) ) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( down_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( fresh_constant ) = [[0], [0]] 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( up_1(x_1) ) = [[0], [0]] + [[0, 1], [1, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( cons_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 0]] * x_2 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( big ) = [[0], [0]] 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( inf_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 <<< 186.57/64.48 M( cons_flat_2(x_1, x_2) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 186.57/64.48 >>> 186.57/64.48 186.57/64.48 Tuple symbols: 186.57/64.48 <<< 186.57/64.48 M( TOP_1(x_1) ) = [[0]] + [[1, 0]] * x_1 186.57/64.48 >>> 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 Matrix type: 186.57/64.48 186.57/64.48 We used a basic matrix type which is not further parametrizeable. 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 186.57/64.48 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 186.57/64.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 186.57/64.48 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 186.57/64.48 186.57/64.48 ---------------------------------------- 186.57/64.48 186.57/64.48 (66) 186.57/64.48 Obligation: 186.57/64.48 Q DP problem: 186.57/64.48 The TRS P consists of the following rules: 186.57/64.48 186.57/64.48 TOP(up(cons(x0, inf(x1)))) -> TOP(cons_flat(down(x0), block(inf(x1)))) 186.57/64.48 TOP(up(s(x0))) -> TOP(s_flat(down(x0))) 186.57/64.48 TOP(up(cons(x0, big))) -> TOP(cons_flat(down(x0), block(big))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(down(x0), block(s(x1)))) 186.57/64.48 TOP(up(cons(x0, s(x1)))) -> TOP(cons_flat(block(x0), down(s(x1)))) 186.57/64.48 TOP(up(cons(x0, fresh_constant))) -> TOP(cons_flat(down(x0), block(fresh_constant))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(down(x0), block(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, big)))) -> TOP(cons_flat(block(x0), down(cons(x1, big)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, inf(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, inf(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(down(x0), block(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, s(x2))))) -> TOP(cons_flat(block(x0), down(cons(x1, s(x2))))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(down(x0), block(cons(x1, fresh_constant)))) 186.57/64.48 TOP(up(cons(x0, cons(x1, fresh_constant)))) -> TOP(cons_flat(block(x0), down(cons(x1, fresh_constant)))) 186.57/64.48 186.57/64.48 The TRS R consists of the following rules: 186.57/64.48 186.57/64.48 down(cons(x, cons(y, cons(z, xs)))) -> up(big) 186.57/64.48 down(inf(x)) -> up(cons(x, inf(s(x)))) 186.57/64.48 top(up(x)) -> top(down(x)) 186.57/64.48 down(s(y3)) -> s_flat(down(y3)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(down(y32), block(big)) 186.57/64.48 down(cons(y32, big)) -> cons_flat(block(y32), down(big)) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(down(y37), block(inf(y38))) 186.57/64.48 down(cons(y37, inf(y38))) -> cons_flat(block(y37), down(inf(y38))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(down(y48), block(s(y49))) 186.57/64.48 down(cons(y48, s(y49))) -> cons_flat(block(y48), down(s(y49))) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(down(y59), block(fresh_constant)) 186.57/64.48 down(cons(y59, fresh_constant)) -> cons_flat(block(y59), down(fresh_constant)) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(down(y15), block(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y162, big))) -> cons_flat(block(y15), down(cons(y162, big))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(down(y15), block(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y167, inf(y168)))) -> cons_flat(block(y15), down(cons(y167, inf(y168)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(down(y15), block(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y178, s(y179)))) -> cons_flat(block(y15), down(cons(y178, s(y179)))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(down(y15), block(cons(y189, fresh_constant))) 186.57/64.48 down(cons(y15, cons(y189, fresh_constant))) -> cons_flat(block(y15), down(cons(y189, fresh_constant))) 186.57/64.48 cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2)) 186.57/64.48 inf_flat(up(x_1)) -> up(inf(x_1)) 186.57/64.48 s_flat(up(x_1)) -> up(s(x_1)) 186.57/64.48 186.57/64.48 Q is empty. 186.57/64.48 We have to consider all minimal (P,Q,R)-chains. 187.33/65.04 EOF