87.55/63.39 MAYBE 87.55/63.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 87.55/63.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 87.55/63.41 87.55/63.41 87.55/63.41 Outermost Termination of the given OTRS could not be shown: 87.55/63.41 87.55/63.41 (0) OTRS 87.55/63.41 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 87.55/63.41 (2) QTRS 87.55/63.41 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 87.55/63.41 (4) QDP 87.55/63.41 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 87.55/63.41 (6) AND 87.55/63.41 (7) QDP 87.55/63.41 (8) UsableRulesProof [EQUIVALENT, 0 ms] 87.55/63.41 (9) QDP 87.55/63.41 (10) QReductionProof [EQUIVALENT, 0 ms] 87.55/63.41 (11) QDP 87.55/63.41 (12) MRRProof [EQUIVALENT, 11 ms] 87.55/63.41 (13) QDP 87.55/63.41 (14) MRRProof [EQUIVALENT, 0 ms] 87.55/63.41 (15) QDP 87.55/63.41 (16) QReductionProof [EQUIVALENT, 0 ms] 87.55/63.41 (17) QDP 87.55/63.41 (18) MRRProof [EQUIVALENT, 10 ms] 87.55/63.41 (19) QDP 87.55/63.41 (20) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 87.55/63.41 (21) QDP 87.55/63.41 (22) DependencyGraphProof [EQUIVALENT, 0 ms] 87.55/63.41 (23) TRUE 87.55/63.41 (24) QDP 87.55/63.41 (25) UsableRulesProof [EQUIVALENT, 0 ms] 87.55/63.41 (26) QDP 87.55/63.41 (27) QReductionProof [EQUIVALENT, 0 ms] 87.55/63.41 (28) QDP 87.55/63.41 (29) TransformationProof [EQUIVALENT, 0 ms] 87.55/63.41 (30) QDP 87.55/63.41 (31) UsableRulesProof [EQUIVALENT, 0 ms] 87.55/63.41 (32) QDP 87.55/63.41 (33) QReductionProof [EQUIVALENT, 0 ms] 87.55/63.41 (34) QDP 87.55/63.41 (35) Trivial-Transformation [SOUND, 0 ms] 87.55/63.41 (36) QTRS 87.55/63.41 (37) DependencyPairsProof [EQUIVALENT, 0 ms] 87.55/63.41 (38) QDP 87.55/63.41 (39) DependencyGraphProof [EQUIVALENT, 0 ms] 87.55/63.41 (40) QDP 87.55/63.41 (41) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 87.55/63.41 (42) QDP 87.55/63.41 (43) NonTerminationLoopProof [COMPLETE, 0 ms] 87.55/63.41 (44) NO 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (0) 87.55/63.41 Obligation: 87.55/63.41 Term rewrite system R: 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 p(x, y, x) -> q(p(y, x, y)) 87.55/63.41 q(q(x)) -> c 87.55/63.41 87.55/63.41 87.55/63.41 87.55/63.41 Outermost Strategy. 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 87.55/63.41 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (2) 87.55/63.41 Obligation: 87.55/63.41 Q restricted rewrite system: 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 top(go_up(x)) -> top(reduce(x)) 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (3) DependencyPairsProof (EQUIVALENT) 87.55/63.41 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (4) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 TOP(go_up(x)) -> REDUCE(x) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> REDEX_P(x_1, x_2, x_3) 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 REDUCE(q(x_1)) -> REDEX_Q(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> IN_P_1(reduce(x_1), x_2, x_3) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> IN_P_2(x_1, reduce(x_2), x_3) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> IN_P_3(x_1, x_2, reduce(x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> IN_Q_1(reduce(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 top(go_up(x)) -> top(reduce(x)) 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (5) DependencyGraphProof (EQUIVALENT) 87.55/63.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (6) 87.55/63.41 Complex Obligation (AND) 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (7) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 top(go_up(x)) -> top(reduce(x)) 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (8) UsableRulesProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (9) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (10) QReductionProof (EQUIVALENT) 87.55/63.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (11) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (12) MRRProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 87.55/63.41 87.55/63.41 Strictly oriented rules of the TRS R: 87.55/63.41 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 87.55/63.41 Used ordering: Polynomial interpretation [POLO]: 87.55/63.41 87.55/63.41 POL(CHECK_P(x_1)) = 1 + 2*x_1 87.55/63.41 POL(CHECK_Q(x_1)) = x_1 87.55/63.41 POL(REDUCE(x_1)) = 1 + 2*x_1 87.55/63.41 POL(c) = 0 87.55/63.41 POL(p(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 87.55/63.41 POL(q(x_1)) = x_1 87.55/63.41 POL(redex_p(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 87.55/63.41 POL(redex_q(x_1)) = 1 + 2*x_1 87.55/63.41 POL(result_p(x_1)) = x_1 87.55/63.41 POL(result_q(x_1)) = x_1 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (13) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (14) MRRProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 87.55/63.41 Strictly oriented dependency pairs: 87.55/63.41 87.55/63.41 REDUCE(q(x_1)) -> CHECK_Q(redex_q(x_1)) 87.55/63.41 CHECK_Q(redex_q(x_1)) -> REDUCE(x_1) 87.55/63.41 87.55/63.41 87.55/63.41 Used ordering: Polynomial interpretation [POLO]: 87.55/63.41 87.55/63.41 POL(CHECK_P(x_1)) = 2*x_1 87.55/63.41 POL(CHECK_Q(x_1)) = 1 + 2*x_1 87.55/63.41 POL(REDUCE(x_1)) = 2 + 2*x_1 87.55/63.41 POL(p(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 87.55/63.41 POL(q(x_1)) = 1 + x_1 87.55/63.41 POL(redex_p(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 87.55/63.41 POL(redex_q(x_1)) = 1 + x_1 87.55/63.41 POL(result_p(x_1)) = x_1 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (15) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (16) QReductionProof (EQUIVALENT) 87.55/63.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 87.55/63.41 87.55/63.41 redex_q(q(x0)) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (17) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (18) MRRProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 87.55/63.41 87.55/63.41 Strictly oriented rules of the TRS R: 87.55/63.41 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 87.55/63.41 Used ordering: Polynomial interpretation [POLO]: 87.55/63.41 87.55/63.41 POL(CHECK_P(x_1)) = 2*x_1 87.55/63.41 POL(REDUCE(x_1)) = 2 + 2*x_1 87.55/63.41 POL(p(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 87.55/63.41 POL(q(x_1)) = x_1 87.55/63.41 POL(redex_p(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 87.55/63.41 POL(result_p(x_1)) = x_1 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (19) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 R is empty. 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (20) UsableRulesReductionPairsProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 87.55/63.41 The following dependency pairs can be deleted: 87.55/63.41 87.55/63.41 REDUCE(p(x_1, x_2, x_3)) -> CHECK_P(redex_p(x_1, x_2, x_3)) 87.55/63.41 No rules are removed from R. 87.55/63.41 87.55/63.41 Used ordering: POLO with Polynomial interpretation [POLO]: 87.55/63.41 87.55/63.41 POL(CHECK_P(x_1)) = x_1 87.55/63.41 POL(REDUCE(x_1)) = 2*x_1 87.55/63.41 POL(p(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 87.55/63.41 POL(redex_p(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (21) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_1) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_2) 87.55/63.41 CHECK_P(redex_p(x_1, x_2, x_3)) -> REDUCE(x_3) 87.55/63.41 87.55/63.41 R is empty. 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (22) DependencyGraphProof (EQUIVALENT) 87.55/63.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (23) 87.55/63.41 TRUE 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (24) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 top(go_up(x)) -> top(reduce(x)) 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (25) UsableRulesProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (26) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (27) QReductionProof (EQUIVALENT) 87.55/63.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (28) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (29) TransformationProof (EQUIVALENT) 87.55/63.41 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 87.55/63.41 87.55/63.41 (TOP(go_up(p(x0, x1, x2))) -> TOP(check_p(redex_p(x0, x1, x2))),TOP(go_up(p(x0, x1, x2))) -> TOP(check_p(redex_p(x0, x1, x2)))) 87.55/63.41 (TOP(go_up(q(x0))) -> TOP(check_q(redex_q(x0))),TOP(go_up(q(x0))) -> TOP(check_q(redex_q(x0)))) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (30) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(p(x0, x1, x2))) -> TOP(check_p(redex_p(x0, x1, x2))) 87.55/63.41 TOP(go_up(q(x0))) -> TOP(check_q(redex_q(x0))) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (31) UsableRulesProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (32) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (33) QReductionProof (EQUIVALENT) 87.55/63.41 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 87.55/63.41 87.55/63.41 top(go_up(x0)) 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (34) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 TOP(go_up(x)) -> TOP(reduce(x)) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 reduce(p(x_1, x_2, x_3)) -> check_p(redex_p(x_1, x_2, x_3)) 87.55/63.41 reduce(q(x_1)) -> check_q(redex_q(x_1)) 87.55/63.41 redex_q(q(x)) -> result_q(c) 87.55/63.41 check_q(result_q(x)) -> go_up(x) 87.55/63.41 check_q(redex_q(x_1)) -> in_q_1(reduce(x_1)) 87.55/63.41 in_q_1(go_up(x_1)) -> go_up(q(x_1)) 87.55/63.41 redex_p(x, y, x) -> result_p(q(p(y, x, y))) 87.55/63.41 check_p(result_p(x)) -> go_up(x) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_1(reduce(x_1), x_2, x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_2(x_1, reduce(x_2), x_3) 87.55/63.41 check_p(redex_p(x_1, x_2, x_3)) -> in_p_3(x_1, x_2, reduce(x_3)) 87.55/63.41 in_p_3(x_1, x_2, go_up(x_3)) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_2(x_1, go_up(x_2), x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 in_p_1(go_up(x_1), x_2, x_3) -> go_up(p(x_1, x_2, x_3)) 87.55/63.41 87.55/63.41 The set Q consists of the following terms: 87.55/63.41 87.55/63.41 reduce(p(x0, x1, x2)) 87.55/63.41 reduce(q(x0)) 87.55/63.41 redex_p(x0, x1, x0) 87.55/63.41 redex_q(q(x0)) 87.55/63.41 check_p(result_p(x0)) 87.55/63.41 check_q(result_q(x0)) 87.55/63.41 check_p(redex_p(x0, x1, x2)) 87.55/63.41 check_q(redex_q(x0)) 87.55/63.41 in_p_1(go_up(x0), x1, x2) 87.55/63.41 in_p_2(x0, go_up(x1), x2) 87.55/63.41 in_p_3(x0, x1, go_up(x2)) 87.55/63.41 in_q_1(go_up(x0)) 87.55/63.41 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (35) Trivial-Transformation (SOUND) 87.55/63.41 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (36) 87.55/63.41 Obligation: 87.55/63.41 Q restricted rewrite system: 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 p(x, y, x) -> q(p(y, x, y)) 87.55/63.41 q(q(x)) -> c 87.55/63.41 87.55/63.41 Q is empty. 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (37) DependencyPairsProof (EQUIVALENT) 87.55/63.41 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (38) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 P(x, y, x) -> Q(p(y, x, y)) 87.55/63.41 P(x, y, x) -> P(y, x, y) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 p(x, y, x) -> q(p(y, x, y)) 87.55/63.41 q(q(x)) -> c 87.55/63.41 87.55/63.41 Q is empty. 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (39) DependencyGraphProof (EQUIVALENT) 87.55/63.41 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (40) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 P(x, y, x) -> P(y, x, y) 87.55/63.41 87.55/63.41 The TRS R consists of the following rules: 87.55/63.41 87.55/63.41 p(x, y, x) -> q(p(y, x, y)) 87.55/63.41 q(q(x)) -> c 87.55/63.41 87.55/63.41 Q is empty. 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (41) UsableRulesReductionPairsProof (EQUIVALENT) 87.55/63.41 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. 87.55/63.41 87.55/63.41 No dependency pairs are removed. 87.55/63.41 87.55/63.41 The following rules are removed from R: 87.55/63.41 87.55/63.41 p(x, y, x) -> q(p(y, x, y)) 87.55/63.41 q(q(x)) -> c 87.55/63.41 Used ordering: POLO with Polynomial interpretation [POLO]: 87.55/63.41 87.55/63.41 POL(P(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (42) 87.55/63.41 Obligation: 87.55/63.41 Q DP problem: 87.55/63.41 The TRS P consists of the following rules: 87.55/63.41 87.55/63.41 P(x, y, x) -> P(y, x, y) 87.55/63.41 87.55/63.41 R is empty. 87.55/63.41 Q is empty. 87.55/63.41 We have to consider all minimal (P,Q,R)-chains. 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (43) NonTerminationLoopProof (COMPLETE) 87.55/63.41 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 87.55/63.41 Found a loop by semiunifying a rule from P directly. 87.55/63.41 87.55/63.41 s = P(x, y, x) evaluates to t =P(y, x, y) 87.55/63.41 87.55/63.41 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 87.55/63.41 * Matcher: [x / y, y / x] 87.55/63.41 * Semiunifier: [ ] 87.55/63.41 87.55/63.41 -------------------------------------------------------------------------------- 87.55/63.41 Rewriting sequence 87.55/63.41 87.55/63.41 The DP semiunifies directly so there is only one rewrite step from P(x, y, x) to P(y, x, y). 87.55/63.41 87.55/63.41 87.55/63.41 87.55/63.41 87.55/63.41 ---------------------------------------- 87.55/63.41 87.55/63.41 (44) 87.55/63.41 NO 87.71/63.47 EOF