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