3.26/1.51 YES 3.26/1.52 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.26/1.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.26/1.52 3.26/1.52 3.26/1.52 Termination of the given CSR could be proven: 3.26/1.52 3.26/1.52 (0) CSR 3.26/1.52 (1) CSRRRRProof [EQUIVALENT, 80 ms] 3.26/1.52 (2) CSR 3.26/1.52 (3) CSRRRRProof [EQUIVALENT, 11 ms] 3.26/1.52 (4) CSR 3.26/1.52 (5) CSRRRRProof [EQUIVALENT, 0 ms] 3.26/1.52 (6) CSR 3.26/1.52 (7) RisEmptyProof [EQUIVALENT, 0 ms] 3.26/1.52 (8) YES 3.26/1.52 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (0) 3.26/1.52 Obligation: 3.26/1.52 Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 app(cons(X, XS), YS) -> cons(X, app(XS, YS)) 3.26/1.52 from(X) -> cons(X, from(s(X))) 3.26/1.52 zWadr(nil, YS) -> nil 3.26/1.52 zWadr(XS, nil) -> nil 3.26/1.52 zWadr(cons(X, XS), cons(Y, YS)) -> cons(app(Y, cons(X, nil)), zWadr(XS, YS)) 3.26/1.52 prefix(L) -> cons(nil, zWadr(L, prefix(L))) 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 cons: {1} 3.26/1.52 from: {1} 3.26/1.52 s: {1} 3.26/1.52 zWadr: {1, 2} 3.26/1.52 prefix: {1} 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (1) CSRRRRProof (EQUIVALENT) 3.26/1.52 The following CSR is given: Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 app(cons(X, XS), YS) -> cons(X, app(XS, YS)) 3.26/1.52 from(X) -> cons(X, from(s(X))) 3.26/1.52 zWadr(nil, YS) -> nil 3.26/1.52 zWadr(XS, nil) -> nil 3.26/1.52 zWadr(cons(X, XS), cons(Y, YS)) -> cons(app(Y, cons(X, nil)), zWadr(XS, YS)) 3.26/1.52 prefix(L) -> cons(nil, zWadr(L, prefix(L))) 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 cons: {1} 3.26/1.52 from: {1} 3.26/1.52 s: {1} 3.26/1.52 zWadr: {1, 2} 3.26/1.52 prefix: {1} 3.26/1.52 Used ordering: 3.26/1.52 Polynomial interpretation [POLO]: 3.26/1.52 3.26/1.52 POL(app(x_1, x_2)) = 2*x_1 + x_2 3.26/1.52 POL(cons(x_1, x_2)) = 2*x_1 3.26/1.52 POL(from(x_1)) = 1 + 2*x_1 3.26/1.52 POL(nil) = 0 3.26/1.52 POL(prefix(x_1)) = 1 + 2*x_1 3.26/1.52 POL(s(x_1)) = 1 + x_1 3.26/1.52 POL(zWadr(x_1, x_2)) = 2*x_1 + 2*x_2 3.26/1.52 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.52 3.26/1.52 from(X) -> cons(X, from(s(X))) 3.26/1.52 prefix(L) -> cons(nil, zWadr(L, prefix(L))) 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (2) 3.26/1.52 Obligation: 3.26/1.52 Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 app(cons(X, XS), YS) -> cons(X, app(XS, YS)) 3.26/1.52 zWadr(nil, YS) -> nil 3.26/1.52 zWadr(XS, nil) -> nil 3.26/1.52 zWadr(cons(X, XS), cons(Y, YS)) -> cons(app(Y, cons(X, nil)), zWadr(XS, YS)) 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 cons: {1} 3.26/1.52 zWadr: {1, 2} 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (3) CSRRRRProof (EQUIVALENT) 3.26/1.52 The following CSR is given: Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 app(cons(X, XS), YS) -> cons(X, app(XS, YS)) 3.26/1.52 zWadr(nil, YS) -> nil 3.26/1.52 zWadr(XS, nil) -> nil 3.26/1.52 zWadr(cons(X, XS), cons(Y, YS)) -> cons(app(Y, cons(X, nil)), zWadr(XS, YS)) 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 cons: {1} 3.26/1.52 zWadr: {1, 2} 3.26/1.52 Used ordering: 3.26/1.52 Polynomial interpretation [POLO]: 3.26/1.52 3.26/1.52 POL(app(x_1, x_2)) = 2*x_1 + x_2 3.26/1.52 POL(cons(x_1, x_2)) = 1 + x_1 3.26/1.52 POL(nil) = 0 3.26/1.52 POL(zWadr(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 3.26/1.52 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.52 3.26/1.52 app(cons(X, XS), YS) -> cons(X, app(XS, YS)) 3.26/1.52 zWadr(nil, YS) -> nil 3.26/1.52 zWadr(XS, nil) -> nil 3.26/1.52 zWadr(cons(X, XS), cons(Y, YS)) -> cons(app(Y, cons(X, nil)), zWadr(XS, YS)) 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (4) 3.26/1.52 Obligation: 3.26/1.52 Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (5) CSRRRRProof (EQUIVALENT) 3.26/1.52 The following CSR is given: Context-sensitive rewrite system: 3.26/1.52 The TRS R consists of the following rules: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 3.26/1.52 The replacement map contains the following entries: 3.26/1.52 3.26/1.52 app: {1, 2} 3.26/1.52 nil: empty set 3.26/1.52 Used ordering: 3.26/1.52 Polynomial interpretation [POLO]: 3.26/1.52 3.26/1.52 POL(app(x_1, x_2)) = x_1 + x_2 3.26/1.52 POL(nil) = 1 3.26/1.52 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.52 3.26/1.52 app(nil, YS) -> YS 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (6) 3.26/1.52 Obligation: 3.26/1.52 Context-sensitive rewrite system: 3.26/1.52 R is empty. 3.26/1.52 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (7) RisEmptyProof (EQUIVALENT) 3.26/1.52 The CSR R is empty. Hence, termination is trivially proven. 3.26/1.52 ---------------------------------------- 3.26/1.52 3.26/1.52 (8) 3.26/1.52 YES 3.26/1.53 EOF