4.17/1.68 YES 4.17/1.70 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.17/1.70 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.17/1.70 4.17/1.70 4.17/1.70 Outermost Termination of the given OTRS could be proven: 4.17/1.70 4.17/1.70 (0) OTRS 4.17/1.70 (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 4.17/1.70 (2) QTRS 4.17/1.70 (3) QTRSRRRProof [EQUIVALENT, 20 ms] 4.17/1.70 (4) QTRS 4.17/1.70 (5) QTRSRRRProof [EQUIVALENT, 11 ms] 4.17/1.70 (6) QTRS 4.17/1.70 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 4.17/1.70 (8) QTRS 4.17/1.70 (9) AAECC Innermost [EQUIVALENT, 0 ms] 4.17/1.70 (10) QTRS 4.17/1.70 (11) DependencyPairsProof [EQUIVALENT, 0 ms] 4.17/1.70 (12) QDP 4.17/1.70 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 4.17/1.70 (14) AND 4.17/1.70 (15) QDP 4.17/1.70 (16) UsableRulesProof [EQUIVALENT, 0 ms] 4.17/1.70 (17) QDP 4.17/1.70 (18) QReductionProof [EQUIVALENT, 0 ms] 4.17/1.70 (19) QDP 4.17/1.70 (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.17/1.70 (21) YES 4.17/1.70 (22) QDP 4.17/1.70 (23) UsableRulesProof [EQUIVALENT, 0 ms] 4.17/1.70 (24) QDP 4.17/1.70 (25) QReductionProof [EQUIVALENT, 0 ms] 4.17/1.70 (26) QDP 4.17/1.70 (27) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms] 4.17/1.70 (28) YES 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (0) 4.17/1.70 Obligation: 4.17/1.70 Term rewrite system R: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 f(h(x)) -> f(i(x)) 4.17/1.70 h(x) -> f(h(x)) 4.17/1.70 i(x) -> h(x) 4.17/1.70 f(i(x)) -> a 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 Outermost Strategy. 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (1) Raffelsieper-Zantema-Transformation (SOUND) 4.17/1.70 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (2) 4.17/1.70 Obligation: 4.17/1.70 Q restricted rewrite system: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(i(x))) -> up(a) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 h_flat(up(x_1)) -> up(h(x_1)) 4.17/1.70 i_flat(up(x_1)) -> up(i(x_1)) 4.17/1.70 4.17/1.70 Q is empty. 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (3) QTRSRRRProof (EQUIVALENT) 4.17/1.70 Used ordering: 4.17/1.70 Polynomial interpretation [POLO]: 4.17/1.70 4.17/1.70 POL(a) = 0 4.17/1.70 POL(down(x_1)) = 2*x_1 4.17/1.70 POL(f(x_1)) = x_1 4.17/1.70 POL(f_flat(x_1)) = x_1 4.17/1.70 POL(fresh_constant) = 0 4.17/1.70 POL(h(x_1)) = x_1 4.17/1.70 POL(h_flat(x_1)) = 1 + 2*x_1 4.17/1.70 POL(i(x_1)) = x_1 4.17/1.70 POL(i_flat(x_1)) = x_1 4.17/1.70 POL(top(x_1)) = x_1 4.17/1.70 POL(up(x_1)) = 2*x_1 4.17/1.70 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.17/1.70 4.17/1.70 h_flat(up(x_1)) -> up(h(x_1)) 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (4) 4.17/1.70 Obligation: 4.17/1.70 Q restricted rewrite system: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(i(x))) -> up(a) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 i_flat(up(x_1)) -> up(i(x_1)) 4.17/1.70 4.17/1.70 Q is empty. 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (5) QTRSRRRProof (EQUIVALENT) 4.17/1.70 Used ordering: 4.17/1.70 Polynomial interpretation [POLO]: 4.17/1.70 4.17/1.70 POL(a) = 0 4.17/1.70 POL(down(x_1)) = 2*x_1 4.17/1.70 POL(f(x_1)) = x_1 4.17/1.70 POL(f_flat(x_1)) = x_1 4.17/1.70 POL(fresh_constant) = 0 4.17/1.70 POL(h(x_1)) = x_1 4.17/1.70 POL(i(x_1)) = x_1 4.17/1.70 POL(i_flat(x_1)) = 2 + x_1 4.17/1.70 POL(top(x_1)) = 2*x_1 4.17/1.70 POL(up(x_1)) = 2*x_1 4.17/1.70 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.17/1.70 4.17/1.70 i_flat(up(x_1)) -> up(i(x_1)) 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (6) 4.17/1.70 Obligation: 4.17/1.70 Q restricted rewrite system: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(i(x))) -> up(a) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 Q is empty. 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (7) QTRSRRRProof (EQUIVALENT) 4.17/1.70 Used ordering: 4.17/1.70 Polynomial interpretation [POLO]: 4.17/1.70 4.17/1.70 POL(a) = 0 4.17/1.70 POL(down(x_1)) = 2*x_1 4.17/1.70 POL(f(x_1)) = x_1 4.17/1.70 POL(f_flat(x_1)) = x_1 4.17/1.70 POL(fresh_constant) = 0 4.17/1.70 POL(h(x_1)) = 2 + x_1 4.17/1.70 POL(i(x_1)) = 2 + x_1 4.17/1.70 POL(top(x_1)) = x_1 4.17/1.70 POL(up(x_1)) = 2*x_1 4.17/1.70 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.17/1.70 4.17/1.70 down(f(i(x))) -> up(a) 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (8) 4.17/1.70 Obligation: 4.17/1.70 Q restricted rewrite system: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 Q is empty. 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (9) AAECC Innermost (EQUIVALENT) 4.17/1.70 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 4.17/1.70 The TRS R 2 is 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 4.17/1.70 The signature Sigma is {top_1} 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (10) 4.17/1.70 Obligation: 4.17/1.70 Q restricted rewrite system: 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (11) DependencyPairsProof (EQUIVALENT) 4.17/1.70 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (12) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 TOP(up(x)) -> DOWN(x) 4.17/1.70 DOWN(f(f(y4))) -> F_FLAT(down(f(y4))) 4.17/1.70 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.17/1.70 DOWN(f(a)) -> F_FLAT(down(a)) 4.17/1.70 DOWN(f(a)) -> DOWN(a) 4.17/1.70 DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) 4.17/1.70 DOWN(f(fresh_constant)) -> DOWN(fresh_constant) 4.17/1.70 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (13) DependencyGraphProof (EQUIVALENT) 4.17/1.70 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (14) 4.17/1.70 Complex Obligation (AND) 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (15) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.17/1.70 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (16) UsableRulesProof (EQUIVALENT) 4.17/1.70 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. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (17) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.17/1.70 4.17/1.70 R is empty. 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (18) QReductionProof (EQUIVALENT) 4.17/1.70 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (19) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.17/1.70 4.17/1.70 R is empty. 4.17/1.70 Q is empty. 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (20) QDPSizeChangeProof (EQUIVALENT) 4.17/1.70 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. 4.17/1.70 4.17/1.70 From the DPs we obtained the following set of size-change graphs: 4.17/1.70 *DOWN(f(f(y4))) -> DOWN(f(y4)) 4.17/1.70 The graph contains the following edges 1 > 1 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (21) 4.17/1.70 YES 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (22) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 top(up(x)) -> top(down(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (23) UsableRulesProof (EQUIVALENT) 4.17/1.70 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. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (24) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 top(up(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (25) QReductionProof (EQUIVALENT) 4.17/1.70 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.17/1.70 4.17/1.70 top(up(x0)) 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (26) 4.17/1.70 Obligation: 4.17/1.70 Q DP problem: 4.17/1.70 The TRS P consists of the following rules: 4.17/1.70 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 4.17/1.70 The TRS R consists of the following rules: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 4.17/1.70 The set Q consists of the following terms: 4.17/1.70 4.17/1.70 down(f(h(x0))) 4.17/1.70 down(h(x0)) 4.17/1.70 down(i(x0)) 4.17/1.70 down(f(f(x0))) 4.17/1.70 down(f(a)) 4.17/1.70 down(f(fresh_constant)) 4.17/1.70 f_flat(up(x0)) 4.17/1.70 4.17/1.70 We have to consider all minimal (P,Q,R)-chains. 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (27) RFCMatchBoundsDPProof (EQUIVALENT) 4.17/1.70 Finiteness of the DP problem can be shown by a matchbound of 9. 4.17/1.70 As the DP problem is minimal we only have to initialize the certificate graph by the rules of P: 4.17/1.70 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 4.17/1.70 To find matches we regarded all rules of R and P: 4.17/1.70 4.17/1.70 down(f(h(x))) -> up(f(i(x))) 4.17/1.70 down(h(x)) -> up(f(h(x))) 4.17/1.70 down(i(x)) -> up(h(x)) 4.17/1.70 down(f(f(y4))) -> f_flat(down(f(y4))) 4.17/1.70 down(f(a)) -> f_flat(down(a)) 4.17/1.70 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.17/1.70 f_flat(up(x_1)) -> up(f(x_1)) 4.17/1.70 TOP(up(x)) -> TOP(down(x)) 4.17/1.70 4.17/1.70 The certificate found is represented by the following graph. 4.17/1.70 The certificate consists of the following enumerated nodes: 4.17/1.70 316, 317, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 371, 372, 373, 374 4.17/1.70 4.17/1.70 Node 316 is start node and node 317 is final node. 4.17/1.70 4.17/1.70 Those nodes are connected through the following edges: 4.17/1.70 4.17/1.70 * 316 to 319 labelled TOP_1(0)* 316 to 324 labelled TOP_1(1)* 316 to 329 labelled TOP_1(2)* 316 to 334 labelled TOP_1(3)* 316 to 340 labelled TOP_1(4)* 317 to 317 labelled #_1(0)* 319 to 317 labelled down_1(0)* 319 to 320 labelled up_1(1)* 319 to 321 labelled up_1(1)* 319 to 322 labelled f_flat_1(1)* 319 to 325 labelled up_1(2)* 320 to 321 labelled f_1(1)* 321 to 317 labelled i_1(1), h_1(1)* 322 to 323 labelled down_1(1)* 322 to 320 labelled up_1(1)* 322 to 322 labelled f_flat_1(1)* 322 to 325 labelled up_1(2)* 323 to 317 labelled f_1(1), a(1), fresh_constant(1)* 324 to 320 labelled down_1(1)* 324 to 321 labelled down_1(1)* 324 to 326 labelled up_1(2)* 324 to 327 labelled up_1(2)* 324 to 325 labelled down_1(1)* 324 to 332 labelled f_flat_1(2)* 324 to 337 labelled up_1(3)* 325 to 320 labelled f_1(2)* 325 to 325 labelled f_1(2)* 326 to 317 labelled h_1(2)* 327 to 328 labelled f_1(2)* 328 to 317 labelled h_1(2), i_1(2)* 329 to 326 labelled down_1(2)* 329 to 327 labelled down_1(2)* 329 to 330 labelled up_1(3)* 329 to 337 labelled down_1(2)* 329 to 342 labelled f_flat_1(3)* 329 to 346 labelled up_1(4)* 330 to 331 labelled f_1(3)* 331 to 317 labelled h_1(3), i_1(3)* 332 to 333 labelled down_1(2)* 332 to 327 labelled up_1(2)* 332 to 332 labelled f_flat_1(2)* 332 to 335 labelled f_flat_1(3)* 332 to 337 labelled up_1(3)* 332 to 341 labelled up_1(4)* 333 to 321 labelled f_1(2)* 333 to 320 labelled f_1(2)* 333 to 325 labelled f_1(2)* 334 to 330 labelled down_1(3)* 334 to 338 labelled up_1(4)* 334 to 346 labelled down_1(3)* 334 to 350 labelled f_flat_1(4)* 334 to 354 labelled up_1(5)* 335 to 336 labelled down_1(3)* 335 to 332 labelled f_flat_1(2)* 335 to 335 labelled f_flat_1(3)* 335 to 337 labelled up_1(3)* 335 to 341 labelled up_1(4)* 336 to 320 labelled f_1(3)* 336 to 325 labelled f_1(3)* 337 to 327 labelled f_1(3)* 337 to 337 labelled f_1(3)* 337 to 341 labelled f_1(3)* 338 to 339 labelled f_1(4)* 339 to 317 labelled i_1(4)* 340 to 338 labelled down_1(4)* 340 to 354 labelled down_1(4)* 340 to 360 labelled f_flat_1(5)* 341 to 337 labelled f_1(4)* 341 to 341 labelled f_1(4)* 342 to 343 labelled down_1(3)* 342 to 330 labelled up_1(3)* 342 to 342 labelled f_flat_1(3)* 342 to 344 labelled f_flat_1(4)* 342 to 346 labelled up_1(4)* 342 to 349 labelled up_1(5)* 343 to 328 labelled f_1(3)* 343 to 327 labelled f_1(3)* 343 to 337 labelled f_1(3)* 343 to 341 labelled f_1(3)* 344 to 345 labelled down_1(4)* 344 to 342 labelled f_flat_1(3)* 344 to 344 labelled f_flat_1(4)* 344 to 346 labelled up_1(4)* 344 to 347 labelled f_flat_1(5)* 344 to 349 labelled up_1(5)* 344 to 355 labelled up_1(6)* 345 to 327 labelled f_1(4)* 345 to 337 labelled f_1(4)* 345 to 341 labelled f_1(4)* 346 to 330 labelled f_1(4)* 346 to 346 labelled f_1(4)* 346 to 349 labelled f_1(4)* 347 to 348 labelled down_1(5)* 347 to 344 labelled f_flat_1(4)* 347 to 347 labelled f_flat_1(5)* 347 to 349 labelled up_1(5)* 347 to 355 labelled up_1(6)* 348 to 337 labelled f_1(5)* 348 to 341 labelled f_1(5)* 349 to 346 labelled f_1(5)* 349 to 349 labelled f_1(5)* 349 to 355 labelled f_1(5)* 350 to 351 labelled down_1(4)* 350 to 338 labelled up_1(4)* 350 to 350 labelled f_flat_1(4)* 350 to 352 labelled f_flat_1(5)* 350 to 354 labelled up_1(5)* 350 to 359 labelled up_1(6)* 351 to 331 labelled f_1(4)* 351 to 330 labelled f_1(4)* 351 to 346 labelled f_1(4)* 351 to 349 labelled f_1(4)* 351 to 355 labelled f_1(4)* 352 to 353 labelled down_1(5)* 352 to 350 labelled f_flat_1(4)* 352 to 352 labelled f_flat_1(5)* 352 to 354 labelled up_1(5)* 352 to 357 labelled f_flat_1(6)* 352 to 359 labelled up_1(6)* 352 to 366 labelled up_1(7)* 353 to 330 labelled f_1(5)* 353 to 346 labelled f_1(5)* 353 to 349 labelled f_1(5)* 353 to 355 labelled f_1(5)* 354 to 338 labelled f_1(5)* 354 to 354 labelled f_1(5)* 354 to 359 labelled f_1(5)* 355 to 349 labelled f_1(6)* 355 to 355 labelled f_1(6)* 357 to 358 labelled down_1(6)* 357 to 352 labelled f_flat_1(5)* 357 to 357 labelled f_flat_1(6)* 357 to 359 labelled up_1(6)* 357 to 364 labelled f_flat_1(7)* 357 to 366 labelled up_1(7)* 357 to 369 labelled up_1(8)* 358 to 346 labelled f_1(6)* 358 to 349 labelled f_1(6)* 358 to 355 labelled f_1(6)* 359 to 354 labelled f_1(6)* 359 to 359 labelled f_1(6)* 359 to 366 labelled f_1(6)* 360 to 361 labelled down_1(5)* 360 to 360 labelled f_flat_1(5)* 360 to 362 labelled f_flat_1(6)* 361 to 339 labelled f_1(5)* 361 to 338 labelled f_1(5)* 361 to 354 labelled f_1(5)* 361 to 359 labelled f_1(5)* 361 to 366 labelled f_1(5)* 362 to 363 labelled down_1(6)* 362 to 360 labelled f_flat_1(5)* 362 to 362 labelled f_flat_1(6)* 362 to 367 labelled f_flat_1(7)* 363 to 338 labelled f_1(6)* 363 to 354 labelled f_1(6)* 363 to 359 labelled f_1(6)* 363 to 366 labelled f_1(6)* 363 to 369 labelled f_1(6)* 364 to 365 labelled down_1(7)* 364 to 357 labelled f_flat_1(6)* 364 to 364 labelled f_flat_1(7)* 364 to 366 labelled up_1(7)* 364 to 369 labelled up_1(8)* 365 to 349 labelled f_1(7)* 365 to 355 labelled f_1(7)* 366 to 359 labelled f_1(7)* 366 to 366 labelled f_1(7)* 366 to 369 labelled f_1(7)* 367 to 368 labelled down_1(7)* 367 to 362 labelled f_flat_1(6)* 367 to 367 labelled f_flat_1(7)* 367 to 371 labelled f_flat_1(8)* 368 to 354 labelled f_1(7)* 368 to 359 labelled f_1(7)* 368 to 366 labelled f_1(7)* 368 to 369 labelled f_1(7)* 369 to 366 labelled f_1(8)* 369 to 369 labelled f_1(8)* 371 to 372 labelled down_1(8)* 371 to 367 labelled f_flat_1(7)* 371 to 371 labelled f_flat_1(8)* 371 to 373 labelled f_flat_1(9)* 372 to 359 labelled f_1(8)* 372 to 366 labelled f_1(8)* 372 to 369 labelled f_1(8)* 373 to 374 labelled down_1(9)* 373 to 371 labelled f_flat_1(8)* 373 to 373 labelled f_flat_1(9)* 374 to 366 labelled f_1(9)* 374 to 369 labelled f_1(9) 4.17/1.70 4.17/1.70 4.17/1.70 ---------------------------------------- 4.17/1.70 4.17/1.70 (28) 4.17/1.70 YES 4.17/1.74 EOF