3.21/1.67 YES 3.44/1.68 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.44/1.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.44/1.68 3.44/1.68 3.44/1.68 Quasi decreasingness of the given CTRS could be proven: 3.44/1.68 3.44/1.68 (0) CTRS 3.44/1.68 (1) CTRSToQTRSProof [SOUND, 0 ms] 3.44/1.68 (2) QTRS 3.44/1.68 (3) QTRSRRRProof [EQUIVALENT, 26 ms] 3.44/1.68 (4) QTRS 3.44/1.68 (5) RisEmptyProof [EQUIVALENT, 0 ms] 3.44/1.68 (6) YES 3.44/1.68 3.44/1.68 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (0) 3.44/1.68 Obligation: 3.44/1.68 Conditional term rewrite system: 3.44/1.68 The TRS R is empty. 3.44/1.68 The conditional TRS C consists of the following conditional rules: 3.44/1.68 3.44/1.68 f(x', x'') -> g(x) <= x' -> x, x'' -> x 3.44/1.68 f(y', h(y'')) -> g(y) <= y' -> y, y'' -> y 3.44/1.68 3.44/1.68 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (1) CTRSToQTRSProof (SOUND) 3.44/1.68 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (2) 3.44/1.68 Obligation: 3.44/1.68 Q restricted rewrite system: 3.44/1.68 The TRS R consists of the following rules: 3.44/1.68 3.44/1.68 f(x', x'') -> U1(x', x'') 3.44/1.68 U1(x, x'') -> U2(x'', x) 3.44/1.68 U2(x, x) -> g(x) 3.44/1.68 f(y', h(y'')) -> U3(y', y'') 3.44/1.68 U3(y, y'') -> U4(y'', y) 3.44/1.68 U4(y, y) -> g(y) 3.44/1.68 3.44/1.68 Q is empty. 3.44/1.68 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (3) QTRSRRRProof (EQUIVALENT) 3.44/1.68 Used ordering: 3.44/1.68 Knuth-Bendix order [KBO] with precedence:U4_2 > U2_2 > f_2 > U3_2 > U1_2 > h_1 > g_1 3.44/1.68 3.44/1.68 and weight map: 3.44/1.68 3.44/1.68 g_1=1 3.44/1.68 h_1=1 3.44/1.68 f_2=2 3.44/1.68 U1_2=1 3.44/1.68 U2_2=0 3.44/1.68 U3_2=3 3.44/1.68 U4_2=0 3.44/1.68 3.44/1.68 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.44/1.68 3.44/1.68 f(x', x'') -> U1(x', x'') 3.44/1.68 U1(x, x'') -> U2(x'', x) 3.44/1.68 U2(x, x) -> g(x) 3.44/1.68 f(y', h(y'')) -> U3(y', y'') 3.44/1.68 U3(y, y'') -> U4(y'', y) 3.44/1.68 U4(y, y) -> g(y) 3.44/1.68 3.44/1.68 3.44/1.68 3.44/1.68 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (4) 3.44/1.68 Obligation: 3.44/1.68 Q restricted rewrite system: 3.44/1.68 R is empty. 3.44/1.68 Q is empty. 3.44/1.68 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (5) RisEmptyProof (EQUIVALENT) 3.44/1.68 The TRS R is empty. Hence, termination is trivially proven. 3.44/1.68 ---------------------------------------- 3.44/1.68 3.44/1.68 (6) 3.44/1.68 YES 3.44/1.70 EOF