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