4.08/1.86 YES 4.08/1.87 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.08/1.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.08/1.87 4.08/1.87 4.08/1.87 Quasi decreasingness of the given CTRS could be proven: 4.08/1.87 4.08/1.87 (0) CTRS 4.08/1.87 (1) CTRSToQTRSProof [SOUND, 0 ms] 4.08/1.87 (2) QTRS 4.08/1.87 (3) QTRSRRRProof [EQUIVALENT, 61 ms] 4.08/1.87 (4) QTRS 4.08/1.87 (5) QTRSRRRProof [EQUIVALENT, 0 ms] 4.08/1.87 (6) QTRS 4.08/1.87 (7) QTRSRRRProof [EQUIVALENT, 9 ms] 4.08/1.87 (8) QTRS 4.08/1.87 (9) QTRSRRRProof [EQUIVALENT, 0 ms] 4.08/1.87 (10) QTRS 4.08/1.87 (11) QTRSRRRProof [EQUIVALENT, 1 ms] 4.08/1.87 (12) QTRS 4.08/1.87 (13) RisEmptyProof [EQUIVALENT, 0 ms] 4.08/1.87 (14) YES 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (0) 4.08/1.87 Obligation: 4.08/1.87 Conditional term rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 a -> c 4.08/1.87 a -> d 4.08/1.87 b -> c 4.08/1.87 b -> d 4.08/1.87 c -> e 4.08/1.87 d -> e 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 s(e) -> t(e) 4.08/1.87 g(x, x) -> h(x, x) 4.08/1.87 4.08/1.87 The conditional TRS C consists of the following conditional rules: 4.08/1.87 4.08/1.87 f(x) -> pair(x, y) <= s(x) -> t(y) 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (1) CTRSToQTRSProof (SOUND) 4.08/1.87 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (2) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 f(x) -> U1(s(x), x) 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 a -> c 4.08/1.87 a -> d 4.08/1.87 b -> c 4.08/1.87 b -> d 4.08/1.87 c -> e 4.08/1.87 d -> e 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 s(e) -> t(e) 4.08/1.87 g(x, x) -> h(x, x) 4.08/1.87 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (3) QTRSRRRProof (EQUIVALENT) 4.08/1.87 Used ordering: 4.08/1.87 Polynomial interpretation [POLO]: 4.08/1.87 4.08/1.87 POL(U1(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(a) = 2 4.08/1.87 POL(b) = 1 4.08/1.87 POL(c) = 0 4.08/1.87 POL(d) = 1 4.08/1.87 POL(e) = 0 4.08/1.87 POL(f(x_1)) = 2 + 2*x_1 4.08/1.87 POL(g(x_1, x_2)) = 1 + x_1 + 2*x_2 4.08/1.87 POL(h(x_1, x_2)) = 1 + x_1 + x_2 4.08/1.87 POL(k) = 0 4.08/1.87 POL(l) = 0 4.08/1.87 POL(pair(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(s(x_1)) = x_1 4.08/1.87 POL(t(x_1)) = x_1 4.08/1.87 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.08/1.87 4.08/1.87 a -> c 4.08/1.87 a -> d 4.08/1.87 b -> c 4.08/1.87 d -> e 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (4) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 f(x) -> U1(s(x), x) 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 b -> d 4.08/1.87 c -> e 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 s(e) -> t(e) 4.08/1.87 g(x, x) -> h(x, x) 4.08/1.87 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (5) QTRSRRRProof (EQUIVALENT) 4.08/1.87 Used ordering: 4.08/1.87 Polynomial interpretation [POLO]: 4.08/1.87 4.08/1.87 POL(U1(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(b) = 1 4.08/1.87 POL(c) = 0 4.08/1.87 POL(d) = 0 4.08/1.87 POL(e) = 0 4.08/1.87 POL(f(x_1)) = 2 + 2*x_1 4.08/1.87 POL(g(x_1, x_2)) = 2 + x_1 + 2*x_2 4.08/1.87 POL(h(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(k) = 0 4.08/1.87 POL(l) = 0 4.08/1.87 POL(pair(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(s(x_1)) = x_1 4.08/1.87 POL(t(x_1)) = x_1 4.08/1.87 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.08/1.87 4.08/1.87 b -> d 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (6) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 f(x) -> U1(s(x), x) 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 c -> e 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 s(e) -> t(e) 4.08/1.87 g(x, x) -> h(x, x) 4.08/1.87 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (7) QTRSRRRProof (EQUIVALENT) 4.08/1.87 Used ordering: 4.08/1.87 Polynomial interpretation [POLO]: 4.08/1.87 4.08/1.87 POL(U1(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(c) = 0 4.08/1.87 POL(e) = 0 4.08/1.87 POL(f(x_1)) = 2 + 2*x_1 4.08/1.87 POL(g(x_1, x_2)) = 1 + x_1 + 2*x_2 4.08/1.87 POL(h(x_1, x_2)) = x_1 + x_2 4.08/1.87 POL(k) = 0 4.08/1.87 POL(l) = 0 4.08/1.87 POL(pair(x_1, x_2)) = 2 + x_1 + x_2 4.08/1.87 POL(s(x_1)) = x_1 4.08/1.87 POL(t(x_1)) = x_1 4.08/1.87 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.08/1.87 4.08/1.87 g(x, x) -> h(x, x) 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (8) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 f(x) -> U1(s(x), x) 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 c -> e 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 s(e) -> t(e) 4.08/1.87 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (9) QTRSRRRProof (EQUIVALENT) 4.08/1.87 Used ordering: 4.08/1.87 Polynomial interpretation [POLO]: 4.08/1.87 4.08/1.87 POL(U1(x_1, x_2)) = x_1 + x_2 4.08/1.87 POL(c) = 2 4.08/1.87 POL(e) = 0 4.08/1.87 POL(f(x_1)) = 2 + 2*x_1 4.08/1.87 POL(k) = 0 4.08/1.87 POL(l) = 0 4.08/1.87 POL(pair(x_1, x_2)) = x_1 + 2*x_2 4.08/1.87 POL(s(x_1)) = x_1 4.08/1.87 POL(t(x_1)) = 2*x_1 4.08/1.87 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.08/1.87 4.08/1.87 f(x) -> U1(s(x), x) 4.08/1.87 c -> e 4.08/1.87 s(c) -> t(k) 4.08/1.87 s(c) -> t(l) 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (10) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 The TRS R consists of the following rules: 4.08/1.87 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(e) -> t(e) 4.08/1.87 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (11) QTRSRRRProof (EQUIVALENT) 4.08/1.87 Used ordering: 4.08/1.87 Knuth-Bendix order [KBO] with precedence:s_1 > l > k > e > t_1 > U1_2 > pair_2 4.08/1.87 4.08/1.87 and weight map: 4.08/1.87 4.08/1.87 k=1 4.08/1.87 e=1 4.08/1.87 l=1 4.08/1.87 t_1=1 4.08/1.87 s_1=1 4.08/1.87 U1_2=0 4.08/1.87 pair_2=1 4.08/1.87 4.08/1.87 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.08/1.87 4.08/1.87 U1(t(y), x) -> pair(x, y) 4.08/1.87 k -> e 4.08/1.87 l -> e 4.08/1.87 s(e) -> t(e) 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (12) 4.08/1.87 Obligation: 4.08/1.87 Q restricted rewrite system: 4.08/1.87 R is empty. 4.08/1.87 Q is empty. 4.08/1.87 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (13) RisEmptyProof (EQUIVALENT) 4.08/1.87 The TRS R is empty. Hence, termination is trivially proven. 4.08/1.87 ---------------------------------------- 4.08/1.87 4.08/1.87 (14) 4.08/1.87 YES 4.08/1.91 EOF