3.47/1.70 YES 3.67/1.71 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.67/1.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.67/1.71 3.67/1.71 3.67/1.71 Quasi decreasingness of the given CTRS could be proven: 3.67/1.71 3.67/1.71 (0) CTRS 3.67/1.71 (1) CTRSToQTRSProof [SOUND, 0 ms] 3.67/1.71 (2) QTRS 3.67/1.71 (3) QTRSRRRProof [EQUIVALENT, 52 ms] 3.67/1.71 (4) QTRS 3.67/1.71 (5) AAECC Innermost [EQUIVALENT, 0 ms] 3.67/1.71 (6) QTRS 3.67/1.71 (7) DependencyPairsProof [EQUIVALENT, 0 ms] 3.67/1.71 (8) QDP 3.67/1.71 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 3.67/1.71 (10) TRUE 3.67/1.71 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (0) 3.67/1.71 Obligation: 3.67/1.71 Conditional term rewrite system: 3.67/1.71 The TRS R consists of the following rules: 3.67/1.71 3.67/1.71 f(g(a)) -> g(b) 3.67/1.71 g(a) -> b 3.67/1.71 3.67/1.71 The conditional TRS C consists of the following conditional rules: 3.67/1.71 3.67/1.71 h(x) -> h(g(x)) <= f(x) -> g(x) 3.67/1.71 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (1) CTRSToQTRSProof (SOUND) 3.67/1.71 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (2) 3.67/1.71 Obligation: 3.67/1.71 Q restricted rewrite system: 3.67/1.71 The TRS R consists of the following rules: 3.67/1.71 3.67/1.71 h(x) -> U1(f(x), x) 3.67/1.71 U1(g(x), x) -> h(g(x)) 3.67/1.71 f(g(a)) -> g(b) 3.67/1.71 g(a) -> b 3.67/1.71 3.67/1.71 Q is empty. 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (3) QTRSRRRProof (EQUIVALENT) 3.67/1.71 Used ordering: 3.67/1.71 Polynomial interpretation [POLO]: 3.67/1.71 3.67/1.71 POL(U1(x_1, x_2)) = x_1 + x_2 3.67/1.71 POL(a) = 1 3.67/1.71 POL(b) = 0 3.67/1.71 POL(f(x_1)) = x_1 3.67/1.71 POL(g(x_1)) = x_1 3.67/1.71 POL(h(x_1)) = 2*x_1 3.67/1.71 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.67/1.71 3.67/1.71 f(g(a)) -> g(b) 3.67/1.71 g(a) -> b 3.67/1.71 3.67/1.71 3.67/1.71 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (4) 3.67/1.71 Obligation: 3.67/1.71 Q restricted rewrite system: 3.67/1.71 The TRS R consists of the following rules: 3.67/1.71 3.67/1.71 h(x) -> U1(f(x), x) 3.67/1.71 U1(g(x), x) -> h(g(x)) 3.67/1.71 3.67/1.71 Q is empty. 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (5) AAECC Innermost (EQUIVALENT) 3.67/1.71 We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is none 3.67/1.71 3.67/1.71 The TRS R 2 is 3.67/1.71 h(x) -> U1(f(x), x) 3.67/1.71 U1(g(x), x) -> h(g(x)) 3.67/1.71 3.67/1.71 The signature Sigma is {h_1, U1_2} 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (6) 3.67/1.71 Obligation: 3.67/1.71 Q restricted rewrite system: 3.67/1.71 The TRS R consists of the following rules: 3.67/1.71 3.67/1.71 h(x) -> U1(f(x), x) 3.67/1.71 U1(g(x), x) -> h(g(x)) 3.67/1.71 3.67/1.71 The set Q consists of the following terms: 3.67/1.71 3.67/1.71 h(x0) 3.67/1.71 U1(g(x0), x0) 3.67/1.71 3.67/1.71 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (7) DependencyPairsProof (EQUIVALENT) 3.67/1.71 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (8) 3.67/1.71 Obligation: 3.67/1.71 Q DP problem: 3.67/1.71 The TRS P consists of the following rules: 3.67/1.71 3.67/1.71 H(x) -> U1^1(f(x), x) 3.67/1.71 U1^1(g(x), x) -> H(g(x)) 3.67/1.71 3.67/1.71 The TRS R consists of the following rules: 3.67/1.71 3.67/1.71 h(x) -> U1(f(x), x) 3.67/1.71 U1(g(x), x) -> h(g(x)) 3.67/1.71 3.67/1.71 The set Q consists of the following terms: 3.67/1.71 3.67/1.71 h(x0) 3.67/1.71 U1(g(x0), x0) 3.67/1.71 3.67/1.71 We have to consider all minimal (P,Q,R)-chains. 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (9) DependencyGraphProof (EQUIVALENT) 3.67/1.71 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 3.67/1.71 ---------------------------------------- 3.67/1.71 3.67/1.71 (10) 3.67/1.71 TRUE 3.67/1.74 EOF