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