182.56/116.76 MAYBE 182.56/116.77 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 182.56/116.77 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 182.56/116.77 182.56/116.77 182.56/116.77 Outermost Termination of the given OTRS could not be shown: 182.56/116.77 182.56/116.77 (0) OTRS 182.56/116.77 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 182.56/116.77 (2) QTRS 182.56/116.77 (3) QTRSRRRProof [EQUIVALENT, 63 ms] 182.56/116.77 (4) QTRS 182.56/116.77 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 182.56/116.77 (6) QDP 182.56/116.77 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 182.56/116.77 (8) AND 182.56/116.77 (9) QDP 182.56/116.77 (10) UsableRulesProof [EQUIVALENT, 0 ms] 182.56/116.77 (11) QDP 182.56/116.77 (12) QReductionProof [EQUIVALENT, 0 ms] 182.56/116.77 (13) QDP 182.56/116.77 (14) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 182.56/116.77 (15) QDP 182.56/116.77 (16) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 182.56/116.77 (17) QDP 182.56/116.77 (18) DependencyGraphProof [EQUIVALENT, 0 ms] 182.56/116.77 (19) TRUE 182.56/116.77 (20) QDP 182.56/116.77 (21) UsableRulesProof [EQUIVALENT, 0 ms] 182.56/116.77 (22) QDP 182.56/116.77 (23) QReductionProof [EQUIVALENT, 0 ms] 182.56/116.77 (24) QDP 182.56/116.77 (25) TransformationProof [SOUND, 0 ms] 182.56/116.77 (26) QDP 182.56/116.77 (27) TransformationProof [EQUIVALENT, 0 ms] 182.56/116.77 (28) QDP 182.56/116.77 (29) TransformationProof [EQUIVALENT, 0 ms] 182.56/116.77 (30) QDP 182.56/116.77 (31) QDPOrderProof [EQUIVALENT, 14 ms] 182.56/116.77 (32) QDP 182.56/116.77 (33) UsableRulesProof [EQUIVALENT, 0 ms] 182.56/116.77 (34) QDP 182.56/116.77 (35) QReductionProof [EQUIVALENT, 0 ms] 182.56/116.77 (36) QDP 182.56/116.77 (37) Trivial-Transformation [SOUND, 0 ms] 182.56/116.77 (38) QTRS 182.56/116.77 (39) QTRSRRRProof [EQUIVALENT, 52 ms] 182.56/116.77 (40) QTRS 182.56/116.77 (41) AAECC Innermost [EQUIVALENT, 0 ms] 182.56/116.77 (42) QTRS 182.56/116.77 (43) DependencyPairsProof [EQUIVALENT, 0 ms] 182.56/116.77 (44) QDP 182.56/116.77 (45) DependencyGraphProof [EQUIVALENT, 0 ms] 182.56/116.77 (46) QDP 182.56/116.77 (47) UsableRulesProof [EQUIVALENT, 0 ms] 182.56/116.77 (48) QDP 182.56/116.77 (49) QReductionProof [EQUIVALENT, 0 ms] 182.56/116.77 (50) QDP 182.56/116.77 (51) TransformationProof [EQUIVALENT, 0 ms] 182.56/116.77 (52) QDP 182.56/116.77 (53) UsableRulesProof [EQUIVALENT, 0 ms] 182.56/116.77 (54) QDP 182.56/116.77 (55) QReductionProof [EQUIVALENT, 0 ms] 182.56/116.77 (56) QDP 182.56/116.77 (57) NonTerminationLoopProof [COMPLETE, 0 ms] 182.56/116.77 (58) NO 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (0) 182.56/116.77 Obligation: 182.56/116.77 Term rewrite system R: 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 f(h(x, x)) -> f(i(x)) 182.56/116.77 f(i(x)) -> a 182.56/116.77 i(x) -> h(x, x) 182.56/116.77 182.56/116.77 182.56/116.77 182.56/116.77 Outermost Strategy. 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 182.56/116.77 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (2) 182.56/116.77 Obligation: 182.56/116.77 Q restricted rewrite system: 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 top(go_up(x)) -> top(reduce(x)) 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 redex_f(i(x)) -> result_f(a) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (3) QTRSRRRProof (EQUIVALENT) 182.56/116.77 Used ordering: 182.56/116.77 Polynomial interpretation [POLO]: 182.56/116.77 182.56/116.77 POL(a) = 0 182.56/116.77 POL(check_f(x_1)) = x_1 182.56/116.77 POL(check_i(x_1)) = x_1 182.56/116.77 POL(f(x_1)) = 1 + x_1 182.56/116.77 POL(go_up(x_1)) = x_1 182.56/116.77 POL(h(x_1, x_2)) = x_1 + x_2 182.56/116.77 POL(i(x_1)) = 2*x_1 182.56/116.77 POL(in_f_1(x_1)) = 1 + x_1 182.56/116.77 POL(in_h_1(x_1, x_2)) = x_1 + x_2 182.56/116.77 POL(in_h_2(x_1, x_2)) = x_1 + x_2 182.56/116.77 POL(in_i_1(x_1)) = 2*x_1 182.56/116.77 POL(redex_f(x_1)) = 1 + x_1 182.56/116.77 POL(redex_i(x_1)) = 2*x_1 182.56/116.77 POL(reduce(x_1)) = x_1 182.56/116.77 POL(result_f(x_1)) = x_1 182.56/116.77 POL(result_i(x_1)) = x_1 182.56/116.77 POL(top(x_1)) = 2*x_1 182.56/116.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 182.56/116.77 182.56/116.77 redex_f(i(x)) -> result_f(a) 182.56/116.77 182.56/116.77 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (4) 182.56/116.77 Obligation: 182.56/116.77 Q restricted rewrite system: 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 top(go_up(x)) -> top(reduce(x)) 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (5) DependencyPairsProof (EQUIVALENT) 182.56/116.77 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (6) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.77 TOP(go_up(x)) -> REDUCE(x) 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 REDUCE(f(x_1)) -> REDEX_F(x_1) 182.56/116.77 REDUCE(i(x_1)) -> CHECK_I(redex_i(x_1)) 182.56/116.77 REDUCE(i(x_1)) -> REDEX_I(x_1) 182.56/116.77 CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 CHECK_I(redex_i(x_1)) -> IN_I_1(reduce(x_1)) 182.56/116.77 CHECK_I(redex_i(x_1)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> IN_H_1(reduce(x_1), x_2) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> IN_H_2(x_1, reduce(x_2)) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_2) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 top(go_up(x)) -> top(reduce(x)) 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (7) DependencyGraphProof (EQUIVALENT) 182.56/116.77 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 9 less nodes. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (8) 182.56/116.77 Complex Obligation (AND) 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (9) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_2) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 top(go_up(x)) -> top(reduce(x)) 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (10) UsableRulesProof (EQUIVALENT) 182.56/116.77 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. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (11) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_2) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (12) QReductionProof (EQUIVALENT) 182.56/116.77 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (13) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_2) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (14) UsableRulesReductionPairsProof (EQUIVALENT) 182.56/116.77 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. 182.56/116.77 182.56/116.77 The following dependency pairs can be deleted: 182.56/116.77 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_1) 182.56/116.77 REDUCE(h(x_1, x_2)) -> REDUCE(x_2) 182.56/116.77 The following rules are removed from R: 182.56/116.77 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 Used ordering: POLO with Polynomial interpretation [POLO]: 182.56/116.77 182.56/116.77 POL(CHECK_F(x_1)) = x_1 182.56/116.77 POL(REDUCE(x_1)) = 2*x_1 182.56/116.77 POL(f(x_1)) = 2*x_1 182.56/116.77 POL(h(x_1, x_2)) = 2*x_1 + x_2 182.56/116.77 POL(i(x_1)) = x_1 182.56/116.77 POL(redex_f(x_1)) = 2*x_1 182.56/116.77 POL(result_f(x_1)) = 2*x_1 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (15) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 182.56/116.77 R is empty. 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (16) UsableRulesReductionPairsProof (EQUIVALENT) 182.56/116.77 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. 182.56/116.77 182.56/116.77 The following dependency pairs can be deleted: 182.56/116.77 182.56/116.77 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 182.56/116.77 No rules are removed from R. 182.56/116.77 182.56/116.77 Used ordering: POLO with Polynomial interpretation [POLO]: 182.56/116.77 182.56/116.77 POL(CHECK_F(x_1)) = 2*x_1 182.56/116.77 POL(REDUCE(x_1)) = 2*x_1 182.56/116.77 POL(f(x_1)) = 2*x_1 182.56/116.77 POL(redex_f(x_1)) = x_1 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (17) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 182.56/116.77 182.56/116.77 R is empty. 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (18) DependencyGraphProof (EQUIVALENT) 182.56/116.77 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (19) 182.56/116.77 TRUE 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (20) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 top(go_up(x)) -> top(reduce(x)) 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 check_i(redex_i(x_1)) -> in_i_1(reduce(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_i_1(go_up(x_1)) -> go_up(i(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (21) UsableRulesProof (EQUIVALENT) 182.56/116.77 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. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (22) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (23) QReductionProof (EQUIVALENT) 182.56/116.77 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 182.56/116.77 182.56/116.77 top(go_up(x0)) 182.56/116.77 in_i_1(go_up(x0)) 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (24) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (25) TransformationProof (SOUND) 182.56/116.77 By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: 182.56/116.77 182.56/116.77 (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) 182.56/116.77 (TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))),TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0)))) 182.56/116.77 (TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1)),TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1))) 182.56/116.77 (TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1))),TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1)))) 182.56/116.77 182.56/116.77 182.56/116.77 ---------------------------------------- 182.56/116.77 182.56/116.77 (26) 182.56/116.77 Obligation: 182.56/116.77 Q DP problem: 182.56/116.77 The TRS P consists of the following rules: 182.56/116.77 182.56/116.77 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 182.56/116.77 TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))) 182.56/116.77 TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1)) 182.56/116.77 TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1))) 182.56/116.77 182.56/116.77 The TRS R consists of the following rules: 182.56/116.77 182.56/116.77 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.77 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.77 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.77 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.77 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.77 redex_i(x) -> result_i(h(x, x)) 182.56/116.77 check_i(result_i(x)) -> go_up(x) 182.56/116.77 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.77 check_f(result_f(x)) -> go_up(x) 182.56/116.77 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.77 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.77 182.56/116.77 The set Q consists of the following terms: 182.56/116.77 182.56/116.77 reduce(f(x0)) 182.56/116.77 reduce(i(x0)) 182.56/116.77 redex_f(h(x0, x0)) 182.56/116.77 redex_f(i(x0)) 182.56/116.77 redex_i(x0) 182.56/116.77 check_f(result_f(x0)) 182.56/116.77 check_i(result_i(x0)) 182.56/116.77 check_f(redex_f(x0)) 182.56/116.77 reduce(h(x0, x1)) 182.56/116.77 in_f_1(go_up(x0)) 182.56/116.77 in_h_1(go_up(x0), x1) 182.56/116.77 in_h_2(x0, go_up(x1)) 182.56/116.77 182.56/116.77 We have to consider all minimal (P,Q,R)-chains. 182.56/116.77 ---------------------------------------- 182.56/116.78 182.56/116.78 (27) TransformationProof (EQUIVALENT) 182.56/116.78 By rewriting [LPAR04] the rule TOP(go_up(i(x0))) -> TOP(check_i(redex_i(x0))) at position [0,0] we obtained the following new rules [LPAR04]: 182.56/116.78 182.56/116.78 (TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0, x0)))),TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0, x0))))) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (28) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1)) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1))) 182.56/116.78 TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0, x0)))) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 redex_i(x) -> result_i(h(x, x)) 182.56/116.78 check_i(result_i(x)) -> go_up(x) 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 reduce(f(x0)) 182.56/116.78 reduce(i(x0)) 182.56/116.78 redex_f(h(x0, x0)) 182.56/116.78 redex_f(i(x0)) 182.56/116.78 redex_i(x0) 182.56/116.78 check_f(result_f(x0)) 182.56/116.78 check_i(result_i(x0)) 182.56/116.78 check_f(redex_f(x0)) 182.56/116.78 reduce(h(x0, x1)) 182.56/116.78 in_f_1(go_up(x0)) 182.56/116.78 in_h_1(go_up(x0), x1) 182.56/116.78 in_h_2(x0, go_up(x1)) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (29) TransformationProof (EQUIVALENT) 182.56/116.78 By rewriting [LPAR04] the rule TOP(go_up(i(x0))) -> TOP(check_i(result_i(h(x0, x0)))) at position [0] we obtained the following new rules [LPAR04]: 182.56/116.78 182.56/116.78 (TOP(go_up(i(x0))) -> TOP(go_up(h(x0, x0))),TOP(go_up(i(x0))) -> TOP(go_up(h(x0, x0)))) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (30) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1)) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1))) 182.56/116.78 TOP(go_up(i(x0))) -> TOP(go_up(h(x0, x0))) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 redex_i(x) -> result_i(h(x, x)) 182.56/116.78 check_i(result_i(x)) -> go_up(x) 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 reduce(f(x0)) 182.56/116.78 reduce(i(x0)) 182.56/116.78 redex_f(h(x0, x0)) 182.56/116.78 redex_f(i(x0)) 182.56/116.78 redex_i(x0) 182.56/116.78 check_f(result_f(x0)) 182.56/116.78 check_i(result_i(x0)) 182.56/116.78 check_f(redex_f(x0)) 182.56/116.78 reduce(h(x0, x1)) 182.56/116.78 in_f_1(go_up(x0)) 182.56/116.78 in_h_1(go_up(x0), x1) 182.56/116.78 in_h_2(x0, go_up(x1)) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (31) QDPOrderProof (EQUIVALENT) 182.56/116.78 We use the reduction pair processor [LPAR04,JAR06]. 182.56/116.78 182.56/116.78 182.56/116.78 The following pairs can be oriented strictly and are deleted. 182.56/116.78 182.56/116.78 TOP(go_up(i(x0))) -> TOP(go_up(h(x0, x0))) 182.56/116.78 The remaining pairs can at least be oriented weakly. 182.56/116.78 Used ordering: Polynomial interpretation [POLO]: 182.56/116.78 182.56/116.78 POL(TOP(x_1)) = x_1 182.56/116.78 POL(check_f(x_1)) = x_1 182.56/116.78 POL(check_i(x_1)) = 1 182.56/116.78 POL(f(x_1)) = 0 182.56/116.78 POL(go_up(x_1)) = x_1 182.56/116.78 POL(h(x_1, x_2)) = 0 182.56/116.78 POL(i(x_1)) = 1 + x_1 182.56/116.78 POL(in_f_1(x_1)) = 0 182.56/116.78 POL(in_h_1(x_1, x_2)) = 0 182.56/116.78 POL(in_h_2(x_1, x_2)) = 0 182.56/116.78 POL(redex_f(x_1)) = 0 182.56/116.78 POL(redex_i(x_1)) = 1 + x_1 182.56/116.78 POL(reduce(x_1)) = 0 182.56/116.78 POL(result_f(x_1)) = x_1 182.56/116.78 POL(result_i(x_1)) = 1 + x_1 182.56/116.78 182.56/116.78 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 182.56/116.78 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (32) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_1(reduce(x0), x1)) 182.56/116.78 TOP(go_up(h(x0, x1))) -> TOP(in_h_2(x0, reduce(x1))) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 redex_i(x) -> result_i(h(x, x)) 182.56/116.78 check_i(result_i(x)) -> go_up(x) 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 reduce(f(x0)) 182.56/116.78 reduce(i(x0)) 182.56/116.78 redex_f(h(x0, x0)) 182.56/116.78 redex_f(i(x0)) 182.56/116.78 redex_i(x0) 182.56/116.78 check_f(result_f(x0)) 182.56/116.78 check_i(result_i(x0)) 182.56/116.78 check_f(redex_f(x0)) 182.56/116.78 reduce(h(x0, x1)) 182.56/116.78 in_f_1(go_up(x0)) 182.56/116.78 in_h_1(go_up(x0), x1) 182.56/116.78 in_h_2(x0, go_up(x1)) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (33) UsableRulesProof (EQUIVALENT) 182.56/116.78 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. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (34) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 redex_i(x) -> result_i(h(x, x)) 182.56/116.78 check_i(result_i(x)) -> go_up(x) 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 top(go_up(x0)) 182.56/116.78 reduce(f(x0)) 182.56/116.78 reduce(i(x0)) 182.56/116.78 redex_f(h(x0, x0)) 182.56/116.78 redex_f(i(x0)) 182.56/116.78 redex_i(x0) 182.56/116.78 check_f(result_f(x0)) 182.56/116.78 check_i(result_i(x0)) 182.56/116.78 check_f(redex_f(x0)) 182.56/116.78 reduce(h(x0, x1)) 182.56/116.78 in_f_1(go_up(x0)) 182.56/116.78 in_h_1(go_up(x0), x1) 182.56/116.78 in_h_2(x0, go_up(x1)) 182.56/116.78 in_i_1(go_up(x0)) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (35) QReductionProof (EQUIVALENT) 182.56/116.78 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 182.56/116.78 182.56/116.78 top(go_up(x0)) 182.56/116.78 in_i_1(go_up(x0)) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (36) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 TOP(go_up(x)) -> TOP(reduce(x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 reduce(f(x_1)) -> check_f(redex_f(x_1)) 182.56/116.78 reduce(i(x_1)) -> check_i(redex_i(x_1)) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_1(reduce(x_1), x_2) 182.56/116.78 reduce(h(x_1, x_2)) -> in_h_2(x_1, reduce(x_2)) 182.56/116.78 in_h_2(x_1, go_up(x_2)) -> go_up(h(x_1, x_2)) 182.56/116.78 in_h_1(go_up(x_1), x_2) -> go_up(h(x_1, x_2)) 182.56/116.78 redex_i(x) -> result_i(h(x, x)) 182.56/116.78 check_i(result_i(x)) -> go_up(x) 182.56/116.78 redex_f(h(x, x)) -> result_f(f(i(x))) 182.56/116.78 check_f(result_f(x)) -> go_up(x) 182.56/116.78 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 182.56/116.78 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 reduce(f(x0)) 182.56/116.78 reduce(i(x0)) 182.56/116.78 redex_f(h(x0, x0)) 182.56/116.78 redex_f(i(x0)) 182.56/116.78 redex_i(x0) 182.56/116.78 check_f(result_f(x0)) 182.56/116.78 check_i(result_i(x0)) 182.56/116.78 check_f(redex_f(x0)) 182.56/116.78 reduce(h(x0, x1)) 182.56/116.78 in_f_1(go_up(x0)) 182.56/116.78 in_h_1(go_up(x0), x1) 182.56/116.78 in_h_2(x0, go_up(x1)) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (37) Trivial-Transformation (SOUND) 182.56/116.78 We applied the Trivial transformation to transform the outermost TRS to a standard TRS. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (38) 182.56/116.78 Obligation: 182.56/116.78 Q restricted rewrite system: 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 f(i(x)) -> a 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 Q is empty. 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (39) QTRSRRRProof (EQUIVALENT) 182.56/116.78 Used ordering: 182.56/116.78 Polynomial interpretation [POLO]: 182.56/116.78 182.56/116.78 POL(a) = 2 182.56/116.78 POL(f(x_1)) = 1 + 2*x_1 182.56/116.78 POL(h(x_1, x_2)) = 1 + x_1 + x_2 182.56/116.78 POL(i(x_1)) = 1 + 2*x_1 182.56/116.78 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 182.56/116.78 182.56/116.78 f(i(x)) -> a 182.56/116.78 182.56/116.78 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (40) 182.56/116.78 Obligation: 182.56/116.78 Q restricted rewrite system: 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 Q is empty. 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (41) AAECC Innermost (EQUIVALENT) 182.56/116.78 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The TRS R 2 is 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 182.56/116.78 The signature Sigma is {f_1} 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (42) 182.56/116.78 Obligation: 182.56/116.78 Q restricted rewrite system: 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 f(h(x0, x0)) 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (43) DependencyPairsProof (EQUIVALENT) 182.56/116.78 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (44) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(i(x)) 182.56/116.78 F(h(x, x)) -> I(x) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 f(h(x0, x0)) 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (45) DependencyGraphProof (EQUIVALENT) 182.56/116.78 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (46) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(i(x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 f(h(x, x)) -> f(i(x)) 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 f(h(x0, x0)) 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (47) UsableRulesProof (EQUIVALENT) 182.56/116.78 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. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (48) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(i(x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 f(h(x0, x0)) 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (49) QReductionProof (EQUIVALENT) 182.56/116.78 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 182.56/116.78 182.56/116.78 f(h(x0, x0)) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (50) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(i(x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (51) TransformationProof (EQUIVALENT) 182.56/116.78 By rewriting [LPAR04] the rule F(h(x, x)) -> F(i(x)) at position [0] we obtained the following new rules [LPAR04]: 182.56/116.78 182.56/116.78 (F(h(x, x)) -> F(h(x, x)),F(h(x, x)) -> F(h(x, x))) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (52) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(h(x, x)) 182.56/116.78 182.56/116.78 The TRS R consists of the following rules: 182.56/116.78 182.56/116.78 i(x) -> h(x, x) 182.56/116.78 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (53) UsableRulesProof (EQUIVALENT) 182.56/116.78 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. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (54) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(h(x, x)) 182.56/116.78 182.56/116.78 R is empty. 182.56/116.78 The set Q consists of the following terms: 182.56/116.78 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (55) QReductionProof (EQUIVALENT) 182.56/116.78 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 182.56/116.78 182.56/116.78 i(x0) 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (56) 182.56/116.78 Obligation: 182.56/116.78 Q DP problem: 182.56/116.78 The TRS P consists of the following rules: 182.56/116.78 182.56/116.78 F(h(x, x)) -> F(h(x, x)) 182.56/116.78 182.56/116.78 R is empty. 182.56/116.78 Q is empty. 182.56/116.78 We have to consider all minimal (P,Q,R)-chains. 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (57) NonTerminationLoopProof (COMPLETE) 182.56/116.78 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 182.56/116.78 Found a loop by semiunifying a rule from P directly. 182.56/116.78 182.56/116.78 s = F(h(x, x)) evaluates to t =F(h(x, x)) 182.56/116.78 182.56/116.78 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 182.56/116.78 * Matcher: [ ] 182.56/116.78 * Semiunifier: [ ] 182.56/116.78 182.56/116.78 -------------------------------------------------------------------------------- 182.56/116.78 Rewriting sequence 182.56/116.78 182.56/116.78 The DP semiunifies directly so there is only one rewrite step from F(h(x, x)) to F(h(x, x)). 182.56/116.78 182.56/116.78 182.56/116.78 182.56/116.78 182.56/116.78 ---------------------------------------- 182.56/116.78 182.56/116.78 (58) 182.56/116.78 NO 182.66/116.84 EOF