135.78/87.50 MAYBE 135.78/87.52 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 135.78/87.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 135.78/87.52 135.78/87.52 135.78/87.52 Outermost Termination of the given OTRS could not be shown: 135.78/87.52 135.78/87.52 (0) OTRS 135.78/87.52 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 135.78/87.52 (2) QTRS 135.78/87.52 (3) QTRSRRRProof [EQUIVALENT, 55 ms] 135.78/87.52 (4) QTRS 135.78/87.52 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 135.78/87.52 (6) QDP 135.78/87.52 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 135.78/87.52 (8) AND 135.78/87.52 (9) QDP 135.78/87.52 (10) UsableRulesProof [EQUIVALENT, 0 ms] 135.78/87.52 (11) QDP 135.78/87.52 (12) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (13) QDP 135.78/87.52 (14) UsableRulesReductionPairsProof [EQUIVALENT, 2 ms] 135.78/87.52 (15) QDP 135.78/87.52 (16) MRRProof [EQUIVALENT, 0 ms] 135.78/87.52 (17) QDP 135.78/87.52 (18) MRRProof [EQUIVALENT, 0 ms] 135.78/87.52 (19) QDP 135.78/87.52 (20) DependencyGraphProof [EQUIVALENT, 0 ms] 135.78/87.52 (21) QDP 135.78/87.52 (22) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (23) QDP 135.78/87.52 (24) MRRProof [EQUIVALENT, 7 ms] 135.78/87.52 (25) QDP 135.78/87.52 (26) PisEmptyProof [EQUIVALENT, 0 ms] 135.78/87.52 (27) YES 135.78/87.52 (28) QDP 135.78/87.52 (29) UsableRulesProof [EQUIVALENT, 0 ms] 135.78/87.52 (30) QDP 135.78/87.52 (31) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (32) QDP 135.78/87.52 (33) TransformationProof [SOUND, 0 ms] 135.78/87.52 (34) QDP 135.78/87.52 (35) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (36) QDP 135.78/87.52 (37) UsableRulesProof [EQUIVALENT, 0 ms] 135.78/87.52 (38) QDP 135.78/87.52 (39) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (40) QDP 135.78/87.52 (41) QReductionProof [EQUIVALENT, 0 ms] 135.78/87.52 (42) QDP 135.78/87.52 (43) Trivial-Transformation [SOUND, 0 ms] 135.78/87.52 (44) QTRS 135.78/87.52 (45) QTRSRRRProof [EQUIVALENT, 58 ms] 135.78/87.52 (46) QTRS 135.78/87.52 (47) DependencyPairsProof [EQUIVALENT, 0 ms] 135.78/87.52 (48) QDP 135.78/87.52 (49) DependencyGraphProof [EQUIVALENT, 0 ms] 135.78/87.52 (50) QDP 135.78/87.52 (51) UsableRulesProof [EQUIVALENT, 0 ms] 135.78/87.52 (52) QDP 135.78/87.52 (53) NonTerminationLoopProof [COMPLETE, 0 ms] 135.78/87.52 (54) NO 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (0) 135.78/87.52 Obligation: 135.78/87.52 Term rewrite system R: 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 f(g(a, a)) -> f(s(g(b, b))) 135.78/87.52 f(f(x)) -> b 135.78/87.52 g(x, x) -> f(g(x, x)) 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 Outermost Strategy. 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 135.78/87.52 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (2) 135.78/87.52 Obligation: 135.78/87.52 Q restricted rewrite system: 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 top(go_up(x)) -> top(reduce(x)) 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 redex_f(g(a, a)) -> result_f(f(s(g(b, b)))) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (3) QTRSRRRProof (EQUIVALENT) 135.78/87.52 Used ordering: 135.78/87.52 Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(a) = 2 135.78/87.52 POL(b) = 0 135.78/87.52 POL(check_f(x_1)) = x_1 135.78/87.52 POL(check_g(x_1)) = x_1 135.78/87.52 POL(f(x_1)) = x_1 135.78/87.52 POL(g(x_1, x_2)) = 2*x_1 + x_2 135.78/87.52 POL(go_up(x_1)) = x_1 135.78/87.52 POL(in_f_1(x_1)) = x_1 135.78/87.52 POL(in_g_1(x_1, x_2)) = 2*x_1 + x_2 135.78/87.52 POL(in_g_2(x_1, x_2)) = 2*x_1 + x_2 135.78/87.52 POL(in_s_1(x_1)) = 2*x_1 135.78/87.52 POL(redex_f(x_1)) = x_1 135.78/87.52 POL(redex_g(x_1, x_2)) = 2*x_1 + x_2 135.78/87.52 POL(reduce(x_1)) = x_1 135.78/87.52 POL(result_f(x_1)) = 2*x_1 135.78/87.52 POL(result_g(x_1)) = x_1 135.78/87.52 POL(s(x_1)) = 2*x_1 135.78/87.52 POL(top(x_1)) = 2*x_1 135.78/87.52 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) -> result_f(f(s(g(b, b)))) 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (4) 135.78/87.52 Obligation: 135.78/87.52 Q restricted rewrite system: 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 top(go_up(x)) -> top(reduce(x)) 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (5) DependencyPairsProof (EQUIVALENT) 135.78/87.52 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (6) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 TOP(go_up(x)) -> REDUCE(x) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 REDUCE(f(x_1)) -> REDEX_F(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 REDUCE(g(x_1, x_2)) -> REDEX_G(x_1, x_2) 135.78/87.52 CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> IN_G_1(reduce(x_1), x_2) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> IN_G_2(x_1, reduce(x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) 135.78/87.52 REDUCE(s(x_1)) -> REDUCE(x_1) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 top(go_up(x)) -> top(reduce(x)) 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (7) DependencyGraphProof (EQUIVALENT) 135.78/87.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (8) 135.78/87.52 Complex Obligation (AND) 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (9) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 REDUCE(s(x_1)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 top(go_up(x)) -> top(reduce(x)) 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (10) UsableRulesProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (11) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 REDUCE(s(x_1)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (12) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (13) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 REDUCE(s(x_1)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (14) UsableRulesReductionPairsProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 135.78/87.52 The following dependency pairs can be deleted: 135.78/87.52 135.78/87.52 REDUCE(s(x_1)) -> REDUCE(x_1) 135.78/87.52 No rules are removed from R. 135.78/87.52 135.78/87.52 Used ordering: POLO with Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(CHECK_F(x_1)) = 2*x_1 135.78/87.52 POL(CHECK_G(x_1)) = x_1 135.78/87.52 POL(REDUCE(x_1)) = 2*x_1 135.78/87.52 POL(b) = 0 135.78/87.52 POL(f(x_1)) = 2*x_1 135.78/87.52 POL(g(x_1, x_2)) = x_1 + x_2 135.78/87.52 POL(redex_f(x_1)) = x_1 135.78/87.52 POL(redex_g(x_1, x_2)) = 2*x_1 + 2*x_2 135.78/87.52 POL(result_f(x_1)) = x_1 135.78/87.52 POL(result_g(x_1)) = x_1 135.78/87.52 POL(s(x_1)) = 2*x_1 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (15) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (16) MRRProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 135.78/87.52 135.78/87.52 Strictly oriented rules of the TRS R: 135.78/87.52 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 135.78/87.52 Used ordering: Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(CHECK_F(x_1)) = x_1 135.78/87.52 POL(CHECK_G(x_1)) = 1 + x_1 135.78/87.52 POL(REDUCE(x_1)) = 1 + 2*x_1 135.78/87.52 POL(b) = 0 135.78/87.52 POL(f(x_1)) = x_1 135.78/87.52 POL(g(x_1, x_2)) = x_1 + x_2 135.78/87.52 POL(redex_f(x_1)) = 1 + 2*x_1 135.78/87.52 POL(redex_g(x_1, x_2)) = 2*x_1 + 2*x_2 135.78/87.52 POL(result_f(x_1)) = x_1 135.78/87.52 POL(result_g(x_1)) = 2*x_1 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (17) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (18) MRRProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 135.78/87.52 Strictly oriented dependency pairs: 135.78/87.52 135.78/87.52 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 135.78/87.52 135.78/87.52 135.78/87.52 Used ordering: Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(CHECK_F(x_1)) = x_1 135.78/87.52 POL(CHECK_G(x_1)) = x_1 135.78/87.52 POL(REDUCE(x_1)) = 2 + 2*x_1 135.78/87.52 POL(f(x_1)) = 1 + x_1 135.78/87.52 POL(g(x_1, x_2)) = x_1 + x_2 135.78/87.52 POL(redex_f(x_1)) = 2 + 2*x_1 135.78/87.52 POL(redex_g(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 135.78/87.52 POL(result_g(x_1)) = 2*x_1 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (19) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (20) DependencyGraphProof (EQUIVALENT) 135.78/87.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (21) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (22) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (23) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (24) MRRProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 135.78/87.52 Strictly oriented dependency pairs: 135.78/87.52 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) 135.78/87.52 REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) 135.78/87.52 CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) 135.78/87.52 135.78/87.52 135.78/87.52 Used ordering: Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(CHECK_G(x_1)) = 1 + x_1 135.78/87.52 POL(REDUCE(x_1)) = 2*x_1 135.78/87.52 POL(f(x_1)) = x_1 135.78/87.52 POL(g(x_1, x_2)) = 2 + x_1 + 2*x_2 135.78/87.52 POL(redex_g(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 135.78/87.52 POL(result_g(x_1)) = x_1 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (25) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 P is empty. 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 redex_g(x0, x0) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (26) PisEmptyProof (EQUIVALENT) 135.78/87.52 The TRS P is empty. Hence, there is no (P,Q,R) chain. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (27) 135.78/87.52 YES 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (28) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 top(go_up(x)) -> top(reduce(x)) 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (29) UsableRulesProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (30) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (31) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (32) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (33) TransformationProof (SOUND) 135.78/87.52 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 135.78/87.52 135.78/87.52 (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) 135.78/87.52 (TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))),TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1)))) 135.78/87.52 (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (34) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 135.78/87.52 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 135.78/87.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (35) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (36) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 135.78/87.52 TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) 135.78/87.52 TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (37) UsableRulesProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (38) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (39) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 top(go_up(x0)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (40) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (41) QReductionProof (EQUIVALENT) 135.78/87.52 We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. 135.78/87.52 135.78/87.52 redex_f(g(a, a)) 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (42) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 TOP(go_up(x)) -> TOP(reduce(x)) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 reduce(f(x_1)) -> check_f(redex_f(x_1)) 135.78/87.52 reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) 135.78/87.52 reduce(s(x_1)) -> in_s_1(reduce(x_1)) 135.78/87.52 in_s_1(go_up(x_1)) -> go_up(s(x_1)) 135.78/87.52 redex_g(x, x) -> result_g(f(g(x, x))) 135.78/87.52 check_g(result_g(x)) -> go_up(x) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) 135.78/87.52 check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) 135.78/87.52 in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) 135.78/87.52 in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) 135.78/87.52 redex_f(f(x)) -> result_f(b) 135.78/87.52 check_f(result_f(x)) -> go_up(x) 135.78/87.52 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 135.78/87.52 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 135.78/87.52 135.78/87.52 The set Q consists of the following terms: 135.78/87.52 135.78/87.52 reduce(f(x0)) 135.78/87.52 reduce(g(x0, x1)) 135.78/87.52 redex_f(f(x0)) 135.78/87.52 redex_g(x0, x0) 135.78/87.52 check_f(result_f(x0)) 135.78/87.52 check_g(result_g(x0)) 135.78/87.52 check_f(redex_f(x0)) 135.78/87.52 check_g(redex_g(x0, x1)) 135.78/87.52 reduce(s(x0)) 135.78/87.52 in_f_1(go_up(x0)) 135.78/87.52 in_g_1(go_up(x0), x1) 135.78/87.52 in_g_2(x0, go_up(x1)) 135.78/87.52 in_s_1(go_up(x0)) 135.78/87.52 135.78/87.52 We have to consider all (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (43) Trivial-Transformation (SOUND) 135.78/87.52 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (44) 135.78/87.52 Obligation: 135.78/87.52 Q restricted rewrite system: 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 f(g(a, a)) -> f(s(g(b, b))) 135.78/87.52 f(f(x)) -> b 135.78/87.52 g(x, x) -> f(g(x, x)) 135.78/87.52 135.78/87.52 Q is empty. 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (45) QTRSRRRProof (EQUIVALENT) 135.78/87.52 Used ordering: 135.78/87.52 Polynomial interpretation [POLO]: 135.78/87.52 135.78/87.52 POL(a) = 2 135.78/87.52 POL(b) = 0 135.78/87.52 POL(f(x_1)) = x_1 135.78/87.52 POL(g(x_1, x_2)) = x_1 + 2*x_2 135.78/87.52 POL(s(x_1)) = 1 + x_1 135.78/87.52 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 135.78/87.52 135.78/87.52 f(g(a, a)) -> f(s(g(b, b))) 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (46) 135.78/87.52 Obligation: 135.78/87.52 Q restricted rewrite system: 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 f(f(x)) -> b 135.78/87.52 g(x, x) -> f(g(x, x)) 135.78/87.52 135.78/87.52 Q is empty. 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (47) DependencyPairsProof (EQUIVALENT) 135.78/87.52 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (48) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 G(x, x) -> F(g(x, x)) 135.78/87.52 G(x, x) -> G(x, x) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 f(f(x)) -> b 135.78/87.52 g(x, x) -> f(g(x, x)) 135.78/87.52 135.78/87.52 Q is empty. 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (49) DependencyGraphProof (EQUIVALENT) 135.78/87.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (50) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 G(x, x) -> G(x, x) 135.78/87.52 135.78/87.52 The TRS R consists of the following rules: 135.78/87.52 135.78/87.52 f(f(x)) -> b 135.78/87.52 g(x, x) -> f(g(x, x)) 135.78/87.52 135.78/87.52 Q is empty. 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (51) UsableRulesProof (EQUIVALENT) 135.78/87.52 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. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (52) 135.78/87.52 Obligation: 135.78/87.52 Q DP problem: 135.78/87.52 The TRS P consists of the following rules: 135.78/87.52 135.78/87.52 G(x, x) -> G(x, x) 135.78/87.52 135.78/87.52 R is empty. 135.78/87.52 Q is empty. 135.78/87.52 We have to consider all minimal (P,Q,R)-chains. 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (53) NonTerminationLoopProof (COMPLETE) 135.78/87.52 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 135.78/87.52 Found a loop by semiunifying a rule from P directly. 135.78/87.52 135.78/87.52 s = G(x, x) evaluates to t =G(x, x) 135.78/87.52 135.78/87.52 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 135.78/87.52 * Matcher: [ ] 135.78/87.52 * Semiunifier: [ ] 135.78/87.52 135.78/87.52 -------------------------------------------------------------------------------- 135.78/87.52 Rewriting sequence 135.78/87.52 135.78/87.52 The DP semiunifies directly so there is only one rewrite step from G(x, x) to G(x, x). 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 135.78/87.52 ---------------------------------------- 135.78/87.52 135.78/87.52 (54) 135.78/87.52 NO 135.88/87.57 EOF