4.90/1.93 YES 4.90/1.95 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.90/1.95 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.90/1.95 4.90/1.95 4.90/1.95 Outermost Termination of the given OTRS could be proven: 4.90/1.95 4.90/1.95 (0) OTRS 4.90/1.95 (1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms] 4.90/1.95 (2) QTRS 4.90/1.95 (3) QTRSRRRProof [EQUIVALENT, 29 ms] 4.90/1.95 (4) QTRS 4.90/1.95 (5) AAECC Innermost [EQUIVALENT, 0 ms] 4.90/1.95 (6) QTRS 4.90/1.95 (7) DependencyPairsProof [EQUIVALENT, 0 ms] 4.90/1.95 (8) QDP 4.90/1.95 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 4.90/1.95 (10) AND 4.90/1.95 (11) QDP 4.90/1.95 (12) UsableRulesProof [EQUIVALENT, 0 ms] 4.90/1.95 (13) QDP 4.90/1.95 (14) QReductionProof [EQUIVALENT, 0 ms] 4.90/1.95 (15) QDP 4.90/1.95 (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.90/1.95 (17) YES 4.90/1.95 (18) QDP 4.90/1.95 (19) UsableRulesProof [EQUIVALENT, 0 ms] 4.90/1.95 (20) QDP 4.90/1.95 (21) QReductionProof [EQUIVALENT, 0 ms] 4.90/1.95 (22) QDP 4.90/1.95 (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.90/1.95 (24) YES 4.90/1.95 (25) QDP 4.90/1.95 (26) UsableRulesProof [EQUIVALENT, 0 ms] 4.90/1.95 (27) QDP 4.90/1.95 (28) QReductionProof [EQUIVALENT, 0 ms] 4.90/1.95 (29) QDP 4.90/1.95 (30) QDPOrderProof [EQUIVALENT, 28 ms] 4.90/1.95 (31) QDP 4.90/1.95 (32) PisEmptyProof [EQUIVALENT, 0 ms] 4.90/1.95 (33) YES 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (0) 4.90/1.95 Obligation: 4.90/1.95 Term rewrite system R: 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 f(h(x)) -> f(i(x)) 4.90/1.95 f(i(x)) -> a 4.90/1.95 i(x) -> h(x) 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 Outermost Strategy. 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (1) Raffelsieper-Zantema-Transformation (SOUND) 4.90/1.95 We applied the Raffelsieper-Zantema transformation to transform the outermost TRS to a standard TRS. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (2) 4.90/1.95 Obligation: 4.90/1.95 Q restricted rewrite system: 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(f(i(x))) -> up(a) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 i_flat(up(x_1)) -> up(i(x_1)) 4.90/1.95 4.90/1.95 Q is empty. 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (3) QTRSRRRProof (EQUIVALENT) 4.90/1.95 Used ordering: 4.90/1.95 Polynomial interpretation [POLO]: 4.90/1.95 4.90/1.95 POL(a) = 0 4.90/1.95 POL(down(x_1)) = 2 + 2*x_1 4.90/1.95 POL(f(x_1)) = 2 + 2*x_1 4.90/1.95 POL(f_flat(x_1)) = 2 + 2*x_1 4.90/1.95 POL(fresh_constant) = 1 4.90/1.95 POL(h(x_1)) = x_1 4.90/1.95 POL(h_flat(x_1)) = x_1 4.90/1.95 POL(i(x_1)) = x_1 4.90/1.95 POL(i_flat(x_1)) = 1 + 2*x_1 4.90/1.95 POL(top(x_1)) = x_1 4.90/1.95 POL(up(x_1)) = 2 + 2*x_1 4.90/1.95 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.90/1.95 4.90/1.95 down(f(i(x))) -> up(a) 4.90/1.95 i_flat(up(x_1)) -> up(i(x_1)) 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (4) 4.90/1.95 Obligation: 4.90/1.95 Q restricted rewrite system: 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 Q is empty. 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (5) AAECC Innermost (EQUIVALENT) 4.90/1.95 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 4.90/1.95 The TRS R 2 is 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 4.90/1.95 The signature Sigma is {top_1} 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (6) 4.90/1.95 Obligation: 4.90/1.95 Q restricted rewrite system: 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (7) DependencyPairsProof (EQUIVALENT) 4.90/1.95 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (8) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 TOP(up(x)) -> TOP(down(x)) 4.90/1.95 TOP(up(x)) -> DOWN(x) 4.90/1.95 DOWN(h(y1)) -> H_FLAT(down(y1)) 4.90/1.95 DOWN(h(y1)) -> DOWN(y1) 4.90/1.95 DOWN(f(f(y4))) -> F_FLAT(down(f(y4))) 4.90/1.95 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.90/1.95 DOWN(f(a)) -> F_FLAT(down(a)) 4.90/1.95 DOWN(f(a)) -> DOWN(a) 4.90/1.95 DOWN(f(fresh_constant)) -> F_FLAT(down(fresh_constant)) 4.90/1.95 DOWN(f(fresh_constant)) -> DOWN(fresh_constant) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (9) DependencyGraphProof (EQUIVALENT) 4.90/1.95 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (10) 4.90/1.95 Complex Obligation (AND) 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (11) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (12) UsableRulesProof (EQUIVALENT) 4.90/1.95 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.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (13) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.90/1.95 4.90/1.95 R is empty. 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (14) QReductionProof (EQUIVALENT) 4.90/1.95 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (15) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(f(f(y4))) -> DOWN(f(y4)) 4.90/1.95 4.90/1.95 R is empty. 4.90/1.95 Q is empty. 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (16) QDPSizeChangeProof (EQUIVALENT) 4.90/1.95 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.90/1.95 4.90/1.95 From the DPs we obtained the following set of size-change graphs: 4.90/1.95 *DOWN(f(f(y4))) -> DOWN(f(y4)) 4.90/1.95 The graph contains the following edges 1 > 1 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (17) 4.90/1.95 YES 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (18) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(h(y1)) -> DOWN(y1) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (19) UsableRulesProof (EQUIVALENT) 4.90/1.95 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.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (20) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(h(y1)) -> DOWN(y1) 4.90/1.95 4.90/1.95 R is empty. 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (21) QReductionProof (EQUIVALENT) 4.90/1.95 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (22) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 DOWN(h(y1)) -> DOWN(y1) 4.90/1.95 4.90/1.95 R is empty. 4.90/1.95 Q is empty. 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (23) QDPSizeChangeProof (EQUIVALENT) 4.90/1.95 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.90/1.95 4.90/1.95 From the DPs we obtained the following set of size-change graphs: 4.90/1.95 *DOWN(h(y1)) -> DOWN(y1) 4.90/1.95 The graph contains the following edges 1 > 1 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (24) 4.90/1.95 YES 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (25) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 TOP(up(x)) -> TOP(down(x)) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 top(up(x)) -> top(down(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (26) UsableRulesProof (EQUIVALENT) 4.90/1.95 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.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (27) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 TOP(up(x)) -> TOP(down(x)) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 top(up(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (28) QReductionProof (EQUIVALENT) 4.90/1.95 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.90/1.95 4.90/1.95 top(up(x0)) 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (29) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 The TRS P consists of the following rules: 4.90/1.95 4.90/1.95 TOP(up(x)) -> TOP(down(x)) 4.90/1.95 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (30) QDPOrderProof (EQUIVALENT) 4.90/1.95 We use the reduction pair processor [LPAR04,JAR06]. 4.90/1.95 4.90/1.95 4.90/1.95 The following pairs can be oriented strictly and are deleted. 4.90/1.95 4.90/1.95 TOP(up(x)) -> TOP(down(x)) 4.90/1.95 The remaining pairs can at least be oriented weakly. 4.90/1.95 Used ordering: Matrix interpretation [MATRO]: 4.90/1.95 4.90/1.95 Non-tuple symbols: 4.90/1.95 <<< 4.90/1.95 M( h_flat_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( a ) = [[1], [0]] 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( down_1(x_1) ) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( f_1(x_1) ) = [[1], [0]] + [[1, 0], [1, 0]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( i_1(x_1) ) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( fresh_constant ) = [[1], [0]] 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( h_1(x_1) ) = [[1], [0]] + [[0, 0], [0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( up_1(x_1) ) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 <<< 4.90/1.95 M( f_flat_1(x_1) ) = [[1], [1]] + [[1, 0], [1, 0]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 Tuple symbols: 4.90/1.95 <<< 4.90/1.95 M( TOP_1(x_1) ) = [[0]] + [[0, 1]] * x_1 4.90/1.95 >>> 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 Matrix type: 4.90/1.95 4.90/1.95 We used a basic matrix type which is not further parametrizeable. 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 4.90/1.95 As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order. 4.90/1.95 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 4.90/1.95 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (31) 4.90/1.95 Obligation: 4.90/1.95 Q DP problem: 4.90/1.95 P is empty. 4.90/1.95 The TRS R consists of the following rules: 4.90/1.95 4.90/1.95 down(f(h(x))) -> up(f(i(x))) 4.90/1.95 down(i(x)) -> up(h(x)) 4.90/1.95 down(h(y1)) -> h_flat(down(y1)) 4.90/1.95 down(f(f(y4))) -> f_flat(down(f(y4))) 4.90/1.95 down(f(a)) -> f_flat(down(a)) 4.90/1.95 down(f(fresh_constant)) -> f_flat(down(fresh_constant)) 4.90/1.95 f_flat(up(x_1)) -> up(f(x_1)) 4.90/1.95 h_flat(up(x_1)) -> up(h(x_1)) 4.90/1.95 4.90/1.95 The set Q consists of the following terms: 4.90/1.95 4.90/1.95 down(f(h(x0))) 4.90/1.95 down(i(x0)) 4.90/1.95 down(h(x0)) 4.90/1.95 down(f(f(x0))) 4.90/1.95 down(f(a)) 4.90/1.95 down(f(fresh_constant)) 4.90/1.95 f_flat(up(x0)) 4.90/1.95 h_flat(up(x0)) 4.90/1.95 4.90/1.95 We have to consider all minimal (P,Q,R)-chains. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (32) PisEmptyProof (EQUIVALENT) 4.90/1.95 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.90/1.95 ---------------------------------------- 4.90/1.95 4.90/1.95 (33) 4.90/1.95 YES 5.11/2.00 EOF