7.21/2.46 YES 7.21/2.48 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 7.21/2.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.21/2.48 7.21/2.48 7.21/2.48 Outermost Termination of the given OTRS could be proven: 7.21/2.48 7.21/2.48 (0) OTRS 7.21/2.48 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 7.21/2.48 (2) QTRS 7.21/2.48 (3) QTRSRRRProof [EQUIVALENT, 77 ms] 7.21/2.48 (4) QTRS 7.21/2.48 (5) QTRSRRRProof [EQUIVALENT, 32 ms] 7.21/2.48 (6) QTRS 7.21/2.48 (7) QTRSRRRProof [EQUIVALENT, 23 ms] 7.21/2.48 (8) QTRS 7.21/2.48 (9) DependencyPairsProof [EQUIVALENT, 0 ms] 7.21/2.48 (10) QDP 7.21/2.48 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 7.21/2.48 (12) AND 7.21/2.48 (13) QDP 7.21/2.48 (14) UsableRulesProof [EQUIVALENT, 0 ms] 7.21/2.48 (15) QDP 7.21/2.48 (16) QReductionProof [EQUIVALENT, 0 ms] 7.21/2.48 (17) QDP 7.21/2.48 (18) UsableRulesReductionPairsProof [EQUIVALENT, 4 ms] 7.21/2.48 (19) QDP 7.21/2.48 (20) DependencyGraphProof [EQUIVALENT, 0 ms] 7.21/2.48 (21) TRUE 7.21/2.48 (22) QDP 7.21/2.48 (23) UsableRulesProof [EQUIVALENT, 0 ms] 7.21/2.48 (24) QDP 7.21/2.48 (25) QReductionProof [EQUIVALENT, 0 ms] 7.21/2.48 (26) QDP 7.21/2.48 (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.21/2.48 (28) YES 7.21/2.48 (29) QDP 7.21/2.48 (30) UsableRulesProof [EQUIVALENT, 0 ms] 7.21/2.48 (31) QDP 7.21/2.48 (32) QReductionProof [EQUIVALENT, 0 ms] 7.21/2.48 (33) QDP 7.21/2.48 (34) QDPOrderProof [EQUIVALENT, 45 ms] 7.21/2.48 (35) QDP 7.21/2.48 (36) PisEmptyProof [EQUIVALENT, 0 ms] 7.21/2.48 (37) YES 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (0) 7.21/2.48 Obligation: 7.21/2.48 Term rewrite system R: 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 a__f(b, X, c) -> a__f(X, a__c, X) 7.21/2.48 a__c -> b 7.21/2.48 mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3) 7.21/2.48 mark(c) -> a__c 7.21/2.48 mark(b) -> b 7.21/2.48 a__f(X1, X2, X3) -> f(X1, X2, X3) 7.21/2.48 a__c -> c 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 Outermost Strategy. 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 7.21/2.48 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (2) 7.21/2.48 Obligation: 7.21/2.48 Q restricted rewrite system: 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 redex_mark(f(X1, X2, X3)) -> result_mark(a__f(X1, mark(X2), X3)) 7.21/2.48 redex_mark(c) -> result_mark(a__c) 7.21/2.48 redex_mark(b) -> result_mark(b) 7.21/2.48 redex_a__f(X1, X2, X3) -> result_a__f(f(X1, X2, X3)) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_mark(result_mark(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (3) QTRSRRRProof (EQUIVALENT) 7.21/2.48 Used ordering: 7.21/2.48 Polynomial interpretation [POLO]: 7.21/2.48 7.21/2.48 POL(a__c) = 1 7.21/2.48 POL(a__f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(b) = 1 7.21/2.48 POL(c) = 1 7.21/2.48 POL(check_a__f(x_1)) = x_1 7.21/2.48 POL(check_mark(x_1)) = x_1 7.21/2.48 POL(f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(go_up(x_1)) = x_1 7.21/2.48 POL(in_a__f_1(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_2(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_3(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_1(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_2(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_3(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_mark_1(x_1)) = 2*x_1 7.21/2.48 POL(mark(x_1)) = 2*x_1 7.21/2.48 POL(redex_a__f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(redex_mark(x_1)) = 2*x_1 7.21/2.48 POL(reduce(x_1)) = x_1 7.21/2.48 POL(result_a__f(x_1)) = x_1 7.21/2.48 POL(result_mark(x_1)) = x_1 7.21/2.48 POL(top(x_1)) = x_1 7.21/2.48 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.21/2.48 7.21/2.48 redex_mark(f(X1, X2, X3)) -> result_mark(a__f(X1, mark(X2), X3)) 7.21/2.48 redex_mark(c) -> result_mark(a__c) 7.21/2.48 redex_mark(b) -> result_mark(b) 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (4) 7.21/2.48 Obligation: 7.21/2.48 Q restricted rewrite system: 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 redex_a__f(X1, X2, X3) -> result_a__f(f(X1, X2, X3)) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_mark(result_mark(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (5) QTRSRRRProof (EQUIVALENT) 7.21/2.48 Used ordering: 7.21/2.48 Polynomial interpretation [POLO]: 7.21/2.48 7.21/2.48 POL(a__c) = 0 7.21/2.48 POL(a__f(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(b) = 0 7.21/2.48 POL(c) = 0 7.21/2.48 POL(check_a__f(x_1)) = x_1 7.21/2.48 POL(check_mark(x_1)) = 2*x_1 7.21/2.48 POL(f(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(go_up(x_1)) = x_1 7.21/2.48 POL(in_a__f_1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_2(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_3(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_2(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_3(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_mark_1(x_1)) = 2*x_1 7.21/2.48 POL(mark(x_1)) = 2*x_1 7.21/2.48 POL(redex_a__f(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(redex_mark(x_1)) = x_1 7.21/2.48 POL(reduce(x_1)) = x_1 7.21/2.48 POL(result_a__f(x_1)) = x_1 7.21/2.48 POL(result_mark(x_1)) = 1 + 2*x_1 7.21/2.48 POL(top(x_1)) = x_1 7.21/2.48 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.21/2.48 7.21/2.48 check_mark(result_mark(x)) -> go_up(x) 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (6) 7.21/2.48 Obligation: 7.21/2.48 Q restricted rewrite system: 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 redex_a__f(X1, X2, X3) -> result_a__f(f(X1, X2, X3)) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (7) QTRSRRRProof (EQUIVALENT) 7.21/2.48 Used ordering: 7.21/2.48 Polynomial interpretation [POLO]: 7.21/2.48 7.21/2.48 POL(a__c) = 1 7.21/2.48 POL(a__f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(b) = 1 7.21/2.48 POL(c) = 1 7.21/2.48 POL(check_a__f(x_1)) = x_1 7.21/2.48 POL(check_mark(x_1)) = 2*x_1 7.21/2.48 POL(f(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(go_up(x_1)) = x_1 7.21/2.48 POL(in_a__f_1(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_2(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_a__f_3(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_2(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_f_3(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 7.21/2.48 POL(in_mark_1(x_1)) = 2*x_1 7.21/2.48 POL(mark(x_1)) = 2*x_1 7.21/2.48 POL(redex_a__f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.21/2.48 POL(redex_mark(x_1)) = x_1 7.21/2.48 POL(reduce(x_1)) = x_1 7.21/2.48 POL(result_a__f(x_1)) = x_1 7.21/2.48 POL(top(x_1)) = x_1 7.21/2.48 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.21/2.48 7.21/2.48 redex_a__f(X1, X2, X3) -> result_a__f(f(X1, X2, X3)) 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (8) 7.21/2.48 Obligation: 7.21/2.48 Q restricted rewrite system: 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (9) DependencyPairsProof (EQUIVALENT) 7.21/2.48 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (10) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 TOP(go_up(x)) -> TOP(reduce(x)) 7.21/2.48 TOP(go_up(x)) -> REDUCE(x) 7.21/2.48 REDUCE(a__f(x_1, x_2, x_3)) -> CHECK_A__F(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 REDUCE(a__f(x_1, x_2, x_3)) -> REDEX_A__F(x_1, x_2, x_3) 7.21/2.48 REDUCE(mark(x_1)) -> CHECK_MARK(redex_mark(x_1)) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> IN_A__F_1(reduce(x_1), x_2, x_3) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> IN_A__F_2(x_1, reduce(x_2), x_3) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> IN_A__F_3(x_1, x_2, reduce(x_3)) 7.21/2.48 CHECK_A__F(redex_a__f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> IN_MARK_1(reduce(x_1)) 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> REDUCE(x_1) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> IN_F_1(reduce(x_1), x_2, x_3) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> IN_F_2(x_1, reduce(x_2), x_3) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> IN_F_3(x_1, x_2, reduce(x_3)) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (11) DependencyGraphProof (EQUIVALENT) 7.21/2.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 13 less nodes. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (12) 7.21/2.48 Complex Obligation (AND) 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (13) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(mark(x_1)) -> CHECK_MARK(redex_mark(x_1)) 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> REDUCE(x_1) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (14) UsableRulesProof (EQUIVALENT) 7.21/2.48 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (15) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(mark(x_1)) -> CHECK_MARK(redex_mark(x_1)) 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> REDUCE(x_1) 7.21/2.48 7.21/2.48 R is empty. 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (16) QReductionProof (EQUIVALENT) 7.21/2.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (17) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(mark(x_1)) -> CHECK_MARK(redex_mark(x_1)) 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> REDUCE(x_1) 7.21/2.48 7.21/2.48 R is empty. 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (18) UsableRulesReductionPairsProof (EQUIVALENT) 7.21/2.48 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 7.21/2.48 7.21/2.48 The following dependency pairs can be deleted: 7.21/2.48 7.21/2.48 REDUCE(mark(x_1)) -> CHECK_MARK(redex_mark(x_1)) 7.21/2.48 No rules are removed from R. 7.21/2.48 7.21/2.48 Used ordering: POLO with Polynomial interpretation [POLO]: 7.21/2.48 7.21/2.48 POL(CHECK_MARK(x_1)) = 2*x_1 7.21/2.48 POL(REDUCE(x_1)) = 2*x_1 7.21/2.48 POL(mark(x_1)) = 2*x_1 7.21/2.48 POL(redex_mark(x_1)) = x_1 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (19) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 CHECK_MARK(redex_mark(x_1)) -> REDUCE(x_1) 7.21/2.48 7.21/2.48 R is empty. 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (20) DependencyGraphProof (EQUIVALENT) 7.21/2.48 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (21) 7.21/2.48 TRUE 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (22) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (23) UsableRulesProof (EQUIVALENT) 7.21/2.48 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (24) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 7.21/2.48 R is empty. 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (25) QReductionProof (EQUIVALENT) 7.21/2.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (26) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 7.21/2.48 R is empty. 7.21/2.48 Q is empty. 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (27) QDPSizeChangeProof (EQUIVALENT) 7.21/2.48 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 7.21/2.48 7.21/2.48 From the DPs we obtained the following set of size-change graphs: 7.21/2.48 *REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_2) 7.21/2.48 The graph contains the following edges 1 > 1 7.21/2.48 7.21/2.48 7.21/2.48 *REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_1) 7.21/2.48 The graph contains the following edges 1 > 1 7.21/2.48 7.21/2.48 7.21/2.48 *REDUCE(f(x_1, x_2, x_3)) -> REDUCE(x_3) 7.21/2.48 The graph contains the following edges 1 > 1 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (28) 7.21/2.48 YES 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (29) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 TOP(go_up(x)) -> TOP(reduce(x)) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 top(go_up(x)) -> top(reduce(x)) 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_1(reduce(x_1), x_2, x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_2(x_1, reduce(x_2), x_3) 7.21/2.48 check_a__f(redex_a__f(x_1, x_2, x_3)) -> in_a__f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_a__f_1(go_up(x_1), x_2, x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_2(x_1, go_up(x_2), x_3) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_a__f_3(x_1, x_2, go_up(x_3)) -> go_up(a__f(x_1, x_2, x_3)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (30) UsableRulesProof (EQUIVALENT) 7.21/2.48 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (31) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 TOP(go_up(x)) -> TOP(reduce(x)) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (32) QReductionProof (EQUIVALENT) 7.21/2.48 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.21/2.48 7.21/2.48 top(go_up(x0)) 7.21/2.48 in_a__f_1(go_up(x0), x1, x2) 7.21/2.48 in_a__f_2(x0, go_up(x1), x2) 7.21/2.48 in_a__f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (33) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 The TRS P consists of the following rules: 7.21/2.48 7.21/2.48 TOP(go_up(x)) -> TOP(reduce(x)) 7.21/2.48 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (34) QDPOrderProof (EQUIVALENT) 7.21/2.48 We use the reduction pair processor [LPAR04,JAR06]. 7.21/2.48 7.21/2.48 7.21/2.48 The following pairs can be oriented strictly and are deleted. 7.21/2.48 7.21/2.48 TOP(go_up(x)) -> TOP(reduce(x)) 7.21/2.48 The remaining pairs can at least be oriented weakly. 7.21/2.48 Used ordering: Matrix interpretation [MATRO]: 7.21/2.48 7.21/2.48 Non-tuple symbols: 7.21/2.48 <<< 7.21/2.48 M( a__f_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 0]] * x_2 + [[0, 0], [1, 0]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( reduce_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( result_a__f_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( c ) = [[1], [0]] 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( in_f_2_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 0], [0, 1]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( check_a__f_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( redex_mark_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( in_f_3_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 0], [0, 1]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( redex_a__f_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 0]] * x_2 + [[0, 0], [1, 0]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( go_up_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( b ) = [[0], [0]] 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( in_f_1_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 0], [0, 1]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( check_mark_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( in_mark_1_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( a__c ) = [[0], [1]] 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( f_3(x_1, ..., x_3) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 0], [0, 1]] * x_3 7.21/2.48 >>> 7.21/2.48 7.21/2.48 <<< 7.21/2.48 M( mark_1(x_1) ) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 Tuple symbols: 7.21/2.48 <<< 7.21/2.48 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 7.21/2.48 >>> 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 Matrix type: 7.21/2.48 7.21/2.48 We used a basic matrix type which is not further parametrizeable. 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 7.21/2.48 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 7.21/2.48 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.21/2.48 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 7.21/2.48 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (35) 7.21/2.48 Obligation: 7.21/2.48 Q DP problem: 7.21/2.48 P is empty. 7.21/2.48 The TRS R consists of the following rules: 7.21/2.48 7.21/2.48 reduce(a__f(x_1, x_2, x_3)) -> check_a__f(redex_a__f(x_1, x_2, x_3)) 7.21/2.48 reduce(mark(x_1)) -> check_mark(redex_mark(x_1)) 7.21/2.48 reduce(a__c) -> go_up(b) 7.21/2.48 reduce(a__c) -> go_up(c) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_1(reduce(x_1), x_2, x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_2(x_1, reduce(x_2), x_3) 7.21/2.48 reduce(f(x_1, x_2, x_3)) -> in_f_3(x_1, x_2, reduce(x_3)) 7.21/2.48 in_f_3(x_1, x_2, go_up(x_3)) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_2(x_1, go_up(x_2), x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 in_f_1(go_up(x_1), x_2, x_3) -> go_up(f(x_1, x_2, x_3)) 7.21/2.48 check_mark(redex_mark(x_1)) -> in_mark_1(reduce(x_1)) 7.21/2.48 in_mark_1(go_up(x_1)) -> go_up(mark(x_1)) 7.21/2.48 redex_a__f(b, X, c) -> result_a__f(a__f(X, a__c, X)) 7.21/2.48 check_a__f(result_a__f(x)) -> go_up(x) 7.21/2.48 7.21/2.48 The set Q consists of the following terms: 7.21/2.48 7.21/2.48 reduce(a__f(x0, x1, x2)) 7.21/2.48 reduce(mark(x0)) 7.21/2.48 reduce(a__c) 7.21/2.48 redex_mark(f(x0, x1, x2)) 7.21/2.48 redex_mark(c) 7.21/2.48 redex_mark(b) 7.21/2.48 redex_a__f(x0, x1, x2) 7.21/2.48 check_a__f(result_a__f(x0)) 7.21/2.48 check_mark(result_mark(x0)) 7.21/2.48 check_mark(redex_mark(x0)) 7.21/2.48 reduce(f(x0, x1, x2)) 7.21/2.48 in_mark_1(go_up(x0)) 7.21/2.48 in_f_1(go_up(x0), x1, x2) 7.21/2.48 in_f_2(x0, go_up(x1), x2) 7.21/2.48 in_f_3(x0, x1, go_up(x2)) 7.21/2.48 7.21/2.48 We have to consider all minimal (P,Q,R)-chains. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (36) PisEmptyProof (EQUIVALENT) 7.21/2.48 The TRS P is empty. Hence, there is no (P,Q,R) chain. 7.21/2.48 ---------------------------------------- 7.21/2.48 7.21/2.48 (37) 7.21/2.48 YES 7.51/2.54 EOF