5.86/2.30 YES 5.86/2.31 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.86/2.31 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.86/2.31 5.86/2.31 5.86/2.31 Termination w.r.t. Q of the given QTRS could be proven: 5.86/2.31 5.86/2.31 (0) QTRS 5.86/2.31 (1) QTRSRRRProof [EQUIVALENT, 132 ms] 5.86/2.31 (2) QTRS 5.86/2.31 (3) QTRSRRRProof [EQUIVALENT, 42 ms] 5.86/2.31 (4) QTRS 5.86/2.31 (5) QTRSRRRProof [EQUIVALENT, 36 ms] 5.86/2.31 (6) QTRS 5.86/2.31 (7) QTRSRRRProof [EQUIVALENT, 21 ms] 5.86/2.31 (8) QTRS 5.86/2.31 (9) QTRSRRRProof [EQUIVALENT, 26 ms] 5.86/2.31 (10) QTRS 5.86/2.31 (11) QTRSRRRProof [EQUIVALENT, 0 ms] 5.86/2.31 (12) QTRS 5.86/2.31 (13) QTRSRRRProof [EQUIVALENT, 1 ms] 5.86/2.31 (14) QTRS 5.86/2.31 (15) RisEmptyProof [EQUIVALENT, 0 ms] 5.86/2.31 (16) YES 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (0) 5.86/2.31 Obligation: 5.86/2.31 Q restricted rewrite system: 5.86/2.31 The TRS R consists of the following rules: 5.86/2.31 5.86/2.31 a__zeros -> cons(0, zeros) 5.86/2.31 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.31 a__and(tt, X) -> mark(X) 5.86/2.31 a__isNat(0) -> tt 5.86/2.31 a__isNat(length(V1)) -> a__isNatList(V1) 5.86/2.31 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.31 a__isNatIList(V) -> a__isNatList(V) 5.86/2.31 a__isNatIList(zeros) -> tt 5.86/2.31 a__isNatIList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatIList(V2)) 5.86/2.31 a__isNatList(nil) -> tt 5.86/2.31 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.31 a__length(nil) -> 0 5.86/2.31 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.31 mark(zeros) -> a__zeros 5.86/2.31 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.31 mark(length(X)) -> a__length(mark(X)) 5.86/2.31 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.31 mark(isNat(X)) -> a__isNat(X) 5.86/2.31 mark(isNatList(X)) -> a__isNatList(X) 5.86/2.31 mark(isNatIList(X)) -> a__isNatIList(X) 5.86/2.31 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.31 mark(0) -> 0 5.86/2.31 mark(tt) -> tt 5.86/2.31 mark(s(X)) -> s(mark(X)) 5.86/2.31 mark(nil) -> nil 5.86/2.31 a__zeros -> zeros 5.86/2.31 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.31 a__length(X) -> length(X) 5.86/2.31 a__and(X1, X2) -> and(X1, X2) 5.86/2.31 a__isNat(X) -> isNat(X) 5.86/2.31 a__isNatList(X) -> isNatList(X) 5.86/2.31 a__isNatIList(X) -> isNatIList(X) 5.86/2.31 5.86/2.31 The set Q consists of the following terms: 5.86/2.31 5.86/2.31 a__zeros 5.86/2.31 a__isNatIList(x0) 5.86/2.31 mark(zeros) 5.86/2.31 mark(U11(x0, x1)) 5.86/2.31 mark(length(x0)) 5.86/2.31 mark(and(x0, x1)) 5.86/2.31 mark(isNat(x0)) 5.86/2.31 mark(isNatList(x0)) 5.86/2.31 mark(isNatIList(x0)) 5.86/2.31 mark(cons(x0, x1)) 5.86/2.31 mark(0) 5.86/2.31 mark(tt) 5.86/2.31 mark(s(x0)) 5.86/2.31 mark(nil) 5.86/2.31 a__U11(x0, x1) 5.86/2.31 a__length(x0) 5.86/2.31 a__and(x0, x1) 5.86/2.31 a__isNat(x0) 5.86/2.31 a__isNatList(x0) 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (1) QTRSRRRProof (EQUIVALENT) 5.86/2.31 Used ordering: 5.86/2.31 Polynomial interpretation [POLO]: 5.86/2.31 5.86/2.31 POL(0) = 0 5.86/2.31 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 5.86/2.31 POL(a__isNat(x_1)) = x_1 5.86/2.31 POL(a__isNatIList(x_1)) = 2*x_1 5.86/2.31 POL(a__isNatList(x_1)) = x_1 5.86/2.31 POL(a__length(x_1)) = 2*x_1 5.86/2.31 POL(a__zeros) = 0 5.86/2.31 POL(and(x_1, x_2)) = x_1 + 2*x_2 5.86/2.31 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(isNat(x_1)) = x_1 5.86/2.31 POL(isNatIList(x_1)) = 2*x_1 5.86/2.31 POL(isNatList(x_1)) = x_1 5.86/2.31 POL(length(x_1)) = 2*x_1 5.86/2.31 POL(mark(x_1)) = x_1 5.86/2.31 POL(nil) = 1 5.86/2.31 POL(s(x_1)) = x_1 5.86/2.31 POL(tt) = 0 5.86/2.31 POL(zeros) = 0 5.86/2.31 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.31 5.86/2.31 a__isNatList(nil) -> tt 5.86/2.31 a__length(nil) -> 0 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (2) 5.86/2.31 Obligation: 5.86/2.31 Q restricted rewrite system: 5.86/2.31 The TRS R consists of the following rules: 5.86/2.31 5.86/2.31 a__zeros -> cons(0, zeros) 5.86/2.31 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.31 a__and(tt, X) -> mark(X) 5.86/2.31 a__isNat(0) -> tt 5.86/2.31 a__isNat(length(V1)) -> a__isNatList(V1) 5.86/2.31 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.31 a__isNatIList(V) -> a__isNatList(V) 5.86/2.31 a__isNatIList(zeros) -> tt 5.86/2.31 a__isNatIList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatIList(V2)) 5.86/2.31 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.31 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.31 mark(zeros) -> a__zeros 5.86/2.31 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.31 mark(length(X)) -> a__length(mark(X)) 5.86/2.31 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.31 mark(isNat(X)) -> a__isNat(X) 5.86/2.31 mark(isNatList(X)) -> a__isNatList(X) 5.86/2.31 mark(isNatIList(X)) -> a__isNatIList(X) 5.86/2.31 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.31 mark(0) -> 0 5.86/2.31 mark(tt) -> tt 5.86/2.31 mark(s(X)) -> s(mark(X)) 5.86/2.31 mark(nil) -> nil 5.86/2.31 a__zeros -> zeros 5.86/2.31 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.31 a__length(X) -> length(X) 5.86/2.31 a__and(X1, X2) -> and(X1, X2) 5.86/2.31 a__isNat(X) -> isNat(X) 5.86/2.31 a__isNatList(X) -> isNatList(X) 5.86/2.31 a__isNatIList(X) -> isNatIList(X) 5.86/2.31 5.86/2.31 The set Q consists of the following terms: 5.86/2.31 5.86/2.31 a__zeros 5.86/2.31 a__isNatIList(x0) 5.86/2.31 mark(zeros) 5.86/2.31 mark(U11(x0, x1)) 5.86/2.31 mark(length(x0)) 5.86/2.31 mark(and(x0, x1)) 5.86/2.31 mark(isNat(x0)) 5.86/2.31 mark(isNatList(x0)) 5.86/2.31 mark(isNatIList(x0)) 5.86/2.31 mark(cons(x0, x1)) 5.86/2.31 mark(0) 5.86/2.31 mark(tt) 5.86/2.31 mark(s(x0)) 5.86/2.31 mark(nil) 5.86/2.31 a__U11(x0, x1) 5.86/2.31 a__length(x0) 5.86/2.31 a__and(x0, x1) 5.86/2.31 a__isNat(x0) 5.86/2.31 a__isNatList(x0) 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (3) QTRSRRRProof (EQUIVALENT) 5.86/2.31 Used ordering: 5.86/2.31 Polynomial interpretation [POLO]: 5.86/2.31 5.86/2.31 POL(0) = 0 5.86/2.31 POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2 5.86/2.31 POL(a__U11(x_1, x_2)) = 1 + x_1 + 2*x_2 5.86/2.31 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(a__isNat(x_1)) = x_1 5.86/2.31 POL(a__isNatIList(x_1)) = 2*x_1 5.86/2.31 POL(a__isNatList(x_1)) = x_1 5.86/2.31 POL(a__length(x_1)) = 1 + 2*x_1 5.86/2.31 POL(a__zeros) = 0 5.86/2.31 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(isNat(x_1)) = x_1 5.86/2.31 POL(isNatIList(x_1)) = 2*x_1 5.86/2.31 POL(isNatList(x_1)) = x_1 5.86/2.31 POL(length(x_1)) = 1 + 2*x_1 5.86/2.31 POL(mark(x_1)) = x_1 5.86/2.31 POL(nil) = 0 5.86/2.31 POL(s(x_1)) = x_1 5.86/2.31 POL(tt) = 0 5.86/2.31 POL(zeros) = 0 5.86/2.31 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.31 5.86/2.31 a__isNat(length(V1)) -> a__isNatList(V1) 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (4) 5.86/2.31 Obligation: 5.86/2.31 Q restricted rewrite system: 5.86/2.31 The TRS R consists of the following rules: 5.86/2.31 5.86/2.31 a__zeros -> cons(0, zeros) 5.86/2.31 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.31 a__and(tt, X) -> mark(X) 5.86/2.31 a__isNat(0) -> tt 5.86/2.31 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.31 a__isNatIList(V) -> a__isNatList(V) 5.86/2.31 a__isNatIList(zeros) -> tt 5.86/2.31 a__isNatIList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatIList(V2)) 5.86/2.31 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.31 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.31 mark(zeros) -> a__zeros 5.86/2.31 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.31 mark(length(X)) -> a__length(mark(X)) 5.86/2.31 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.31 mark(isNat(X)) -> a__isNat(X) 5.86/2.31 mark(isNatList(X)) -> a__isNatList(X) 5.86/2.31 mark(isNatIList(X)) -> a__isNatIList(X) 5.86/2.31 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.31 mark(0) -> 0 5.86/2.31 mark(tt) -> tt 5.86/2.31 mark(s(X)) -> s(mark(X)) 5.86/2.31 mark(nil) -> nil 5.86/2.31 a__zeros -> zeros 5.86/2.31 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.31 a__length(X) -> length(X) 5.86/2.31 a__and(X1, X2) -> and(X1, X2) 5.86/2.31 a__isNat(X) -> isNat(X) 5.86/2.31 a__isNatList(X) -> isNatList(X) 5.86/2.31 a__isNatIList(X) -> isNatIList(X) 5.86/2.31 5.86/2.31 The set Q consists of the following terms: 5.86/2.31 5.86/2.31 a__zeros 5.86/2.31 a__isNatIList(x0) 5.86/2.31 mark(zeros) 5.86/2.31 mark(U11(x0, x1)) 5.86/2.31 mark(length(x0)) 5.86/2.31 mark(and(x0, x1)) 5.86/2.31 mark(isNat(x0)) 5.86/2.31 mark(isNatList(x0)) 5.86/2.31 mark(isNatIList(x0)) 5.86/2.31 mark(cons(x0, x1)) 5.86/2.31 mark(0) 5.86/2.31 mark(tt) 5.86/2.31 mark(s(x0)) 5.86/2.31 mark(nil) 5.86/2.31 a__U11(x0, x1) 5.86/2.31 a__length(x0) 5.86/2.31 a__and(x0, x1) 5.86/2.31 a__isNat(x0) 5.86/2.31 a__isNatList(x0) 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (5) QTRSRRRProof (EQUIVALENT) 5.86/2.31 Used ordering: 5.86/2.31 Polynomial interpretation [POLO]: 5.86/2.31 5.86/2.31 POL(0) = 0 5.86/2.31 POL(U11(x_1, x_2)) = x_1 + 2*x_2 5.86/2.31 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 5.86/2.31 POL(a__and(x_1, x_2)) = 2*x_1 + x_2 5.86/2.31 POL(a__isNat(x_1)) = x_1 5.86/2.31 POL(a__isNatIList(x_1)) = 1 + x_1 5.86/2.31 POL(a__isNatList(x_1)) = x_1 5.86/2.31 POL(a__length(x_1)) = 2*x_1 5.86/2.31 POL(a__zeros) = 0 5.86/2.31 POL(and(x_1, x_2)) = 2*x_1 + x_2 5.86/2.31 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.31 POL(isNat(x_1)) = x_1 5.86/2.31 POL(isNatIList(x_1)) = 1 + x_1 5.86/2.31 POL(isNatList(x_1)) = x_1 5.86/2.31 POL(length(x_1)) = 2*x_1 5.86/2.31 POL(mark(x_1)) = x_1 5.86/2.31 POL(nil) = 0 5.86/2.31 POL(s(x_1)) = x_1 5.86/2.31 POL(tt) = 0 5.86/2.31 POL(zeros) = 0 5.86/2.31 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.31 5.86/2.31 a__isNatIList(V) -> a__isNatList(V) 5.86/2.31 a__isNatIList(zeros) -> tt 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 5.86/2.31 ---------------------------------------- 5.86/2.31 5.86/2.31 (6) 5.86/2.31 Obligation: 5.86/2.31 Q restricted rewrite system: 5.86/2.31 The TRS R consists of the following rules: 5.86/2.31 5.86/2.31 a__zeros -> cons(0, zeros) 5.86/2.31 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.31 a__and(tt, X) -> mark(X) 5.86/2.31 a__isNat(0) -> tt 5.86/2.31 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.31 a__isNatIList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatIList(V2)) 5.86/2.31 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.31 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.31 mark(zeros) -> a__zeros 5.86/2.31 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.31 mark(length(X)) -> a__length(mark(X)) 5.86/2.31 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.31 mark(isNat(X)) -> a__isNat(X) 5.86/2.31 mark(isNatList(X)) -> a__isNatList(X) 5.86/2.31 mark(isNatIList(X)) -> a__isNatIList(X) 5.86/2.31 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.31 mark(0) -> 0 5.86/2.31 mark(tt) -> tt 5.86/2.31 mark(s(X)) -> s(mark(X)) 5.86/2.31 mark(nil) -> nil 5.86/2.31 a__zeros -> zeros 5.86/2.31 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.31 a__length(X) -> length(X) 5.86/2.31 a__and(X1, X2) -> and(X1, X2) 5.86/2.31 a__isNat(X) -> isNat(X) 5.86/2.31 a__isNatList(X) -> isNatList(X) 5.86/2.31 a__isNatIList(X) -> isNatIList(X) 5.86/2.31 5.86/2.31 The set Q consists of the following terms: 5.86/2.32 5.86/2.32 a__zeros 5.86/2.32 a__isNatIList(x0) 5.86/2.32 mark(zeros) 5.86/2.32 mark(U11(x0, x1)) 5.86/2.32 mark(length(x0)) 5.86/2.32 mark(and(x0, x1)) 5.86/2.32 mark(isNat(x0)) 5.86/2.32 mark(isNatList(x0)) 5.86/2.32 mark(isNatIList(x0)) 5.86/2.32 mark(cons(x0, x1)) 5.86/2.32 mark(0) 5.86/2.32 mark(tt) 5.86/2.32 mark(s(x0)) 5.86/2.32 mark(nil) 5.86/2.32 a__U11(x0, x1) 5.86/2.32 a__length(x0) 5.86/2.32 a__and(x0, x1) 5.86/2.32 a__isNat(x0) 5.86/2.32 a__isNatList(x0) 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (7) QTRSRRRProof (EQUIVALENT) 5.86/2.32 Used ordering: 5.86/2.32 Polynomial interpretation [POLO]: 5.86/2.32 5.86/2.32 POL(0) = 2 5.86/2.32 POL(U11(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(a__U11(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(a__and(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(a__isNat(x_1)) = x_1 5.86/2.32 POL(a__isNatIList(x_1)) = 2 + x_1 5.86/2.32 POL(a__isNatList(x_1)) = x_1 5.86/2.32 POL(a__length(x_1)) = x_1 5.86/2.32 POL(a__zeros) = 2 5.86/2.32 POL(and(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(cons(x_1, x_2)) = x_1 + 2*x_2 5.86/2.32 POL(isNat(x_1)) = x_1 5.86/2.32 POL(isNatIList(x_1)) = 1 + x_1 5.86/2.32 POL(isNatList(x_1)) = x_1 5.86/2.32 POL(length(x_1)) = x_1 5.86/2.32 POL(mark(x_1)) = 2 + x_1 5.86/2.32 POL(nil) = 0 5.86/2.32 POL(s(x_1)) = x_1 5.86/2.32 POL(tt) = 2 5.86/2.32 POL(zeros) = 0 5.86/2.32 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.32 5.86/2.32 a__isNatIList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatIList(V2)) 5.86/2.32 mark(isNat(X)) -> a__isNat(X) 5.86/2.32 mark(isNatList(X)) -> a__isNatList(X) 5.86/2.32 mark(isNatIList(X)) -> a__isNatIList(X) 5.86/2.32 mark(0) -> 0 5.86/2.32 mark(tt) -> tt 5.86/2.32 mark(nil) -> nil 5.86/2.32 a__zeros -> zeros 5.86/2.32 a__isNatIList(X) -> isNatIList(X) 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (8) 5.86/2.32 Obligation: 5.86/2.32 Q restricted rewrite system: 5.86/2.32 The TRS R consists of the following rules: 5.86/2.32 5.86/2.32 a__zeros -> cons(0, zeros) 5.86/2.32 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.32 a__and(tt, X) -> mark(X) 5.86/2.32 a__isNat(0) -> tt 5.86/2.32 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.32 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.32 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.32 mark(zeros) -> a__zeros 5.86/2.32 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.32 mark(length(X)) -> a__length(mark(X)) 5.86/2.32 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.32 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.32 mark(s(X)) -> s(mark(X)) 5.86/2.32 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.32 a__length(X) -> length(X) 5.86/2.32 a__and(X1, X2) -> and(X1, X2) 5.86/2.32 a__isNat(X) -> isNat(X) 5.86/2.32 a__isNatList(X) -> isNatList(X) 5.86/2.32 5.86/2.32 The set Q consists of the following terms: 5.86/2.32 5.86/2.32 a__zeros 5.86/2.32 a__isNatIList(x0) 5.86/2.32 mark(zeros) 5.86/2.32 mark(U11(x0, x1)) 5.86/2.32 mark(length(x0)) 5.86/2.32 mark(and(x0, x1)) 5.86/2.32 mark(isNat(x0)) 5.86/2.32 mark(isNatList(x0)) 5.86/2.32 mark(isNatIList(x0)) 5.86/2.32 mark(cons(x0, x1)) 5.86/2.32 mark(0) 5.86/2.32 mark(tt) 5.86/2.32 mark(s(x0)) 5.86/2.32 mark(nil) 5.86/2.32 a__U11(x0, x1) 5.86/2.32 a__length(x0) 5.86/2.32 a__and(x0, x1) 5.86/2.32 a__isNat(x0) 5.86/2.32 a__isNatList(x0) 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (9) QTRSRRRProof (EQUIVALENT) 5.86/2.32 Used ordering: 5.86/2.32 Polynomial interpretation [POLO]: 5.86/2.32 5.86/2.32 POL(0) = 0 5.86/2.32 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.32 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.32 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 5.86/2.32 POL(a__isNat(x_1)) = 1 + x_1 5.86/2.32 POL(a__isNatList(x_1)) = 1 + x_1 5.86/2.32 POL(a__length(x_1)) = 2 + 2*x_1 5.86/2.32 POL(a__zeros) = 0 5.86/2.32 POL(and(x_1, x_2)) = x_1 + 2*x_2 5.86/2.32 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 5.86/2.32 POL(isNat(x_1)) = x_1 5.86/2.32 POL(isNatList(x_1)) = x_1 5.86/2.32 POL(length(x_1)) = 2 + 2*x_1 5.86/2.32 POL(mark(x_1)) = x_1 5.86/2.32 POL(s(x_1)) = x_1 5.86/2.32 POL(tt) = 1 5.86/2.32 POL(zeros) = 0 5.86/2.32 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.32 5.86/2.32 a__and(tt, X) -> mark(X) 5.86/2.32 a__isNat(X) -> isNat(X) 5.86/2.32 a__isNatList(X) -> isNatList(X) 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (10) 5.86/2.32 Obligation: 5.86/2.32 Q restricted rewrite system: 5.86/2.32 The TRS R consists of the following rules: 5.86/2.32 5.86/2.32 a__zeros -> cons(0, zeros) 5.86/2.32 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.32 a__isNat(0) -> tt 5.86/2.32 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.32 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.32 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.32 mark(zeros) -> a__zeros 5.86/2.32 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.32 mark(length(X)) -> a__length(mark(X)) 5.86/2.32 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.32 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.32 mark(s(X)) -> s(mark(X)) 5.86/2.32 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.32 a__length(X) -> length(X) 5.86/2.32 a__and(X1, X2) -> and(X1, X2) 5.86/2.32 5.86/2.32 The set Q consists of the following terms: 5.86/2.32 5.86/2.32 a__zeros 5.86/2.32 a__isNatIList(x0) 5.86/2.32 mark(zeros) 5.86/2.32 mark(U11(x0, x1)) 5.86/2.32 mark(length(x0)) 5.86/2.32 mark(and(x0, x1)) 5.86/2.32 mark(isNat(x0)) 5.86/2.32 mark(isNatList(x0)) 5.86/2.32 mark(isNatIList(x0)) 5.86/2.32 mark(cons(x0, x1)) 5.86/2.32 mark(0) 5.86/2.32 mark(tt) 5.86/2.32 mark(s(x0)) 5.86/2.32 mark(nil) 5.86/2.32 a__U11(x0, x1) 5.86/2.32 a__length(x0) 5.86/2.32 a__and(x0, x1) 5.86/2.32 a__isNat(x0) 5.86/2.32 a__isNatList(x0) 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (11) QTRSRRRProof (EQUIVALENT) 5.86/2.32 Used ordering: 5.86/2.32 Polynomial interpretation [POLO]: 5.86/2.32 5.86/2.32 POL(0) = 0 5.86/2.32 POL(U11(x_1, x_2)) = 1 + x_1 + x_2 5.86/2.32 POL(a__U11(x_1, x_2)) = 1 + x_1 + x_2 5.86/2.32 POL(a__and(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(a__isNat(x_1)) = 1 + x_1 5.86/2.32 POL(a__isNatList(x_1)) = x_1 5.86/2.32 POL(a__length(x_1)) = x_1 5.86/2.32 POL(a__zeros) = 2 5.86/2.32 POL(and(x_1, x_2)) = x_1 + x_2 5.86/2.32 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 5.86/2.32 POL(isNat(x_1)) = x_1 5.86/2.32 POL(isNatList(x_1)) = x_1 5.86/2.32 POL(length(x_1)) = x_1 5.86/2.32 POL(mark(x_1)) = 2 + x_1 5.86/2.32 POL(s(x_1)) = x_1 5.86/2.32 POL(tt) = 1 5.86/2.32 POL(zeros) = 0 5.86/2.32 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.32 5.86/2.32 a__isNatList(cons(V1, V2)) -> a__and(a__isNat(V1), isNatList(V2)) 5.86/2.32 a__length(cons(N, L)) -> a__U11(a__and(a__isNatList(L), isNat(N)), L) 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (12) 5.86/2.32 Obligation: 5.86/2.32 Q restricted rewrite system: 5.86/2.32 The TRS R consists of the following rules: 5.86/2.32 5.86/2.32 a__zeros -> cons(0, zeros) 5.86/2.32 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.32 a__isNat(0) -> tt 5.86/2.32 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.32 mark(zeros) -> a__zeros 5.86/2.32 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.32 mark(length(X)) -> a__length(mark(X)) 5.86/2.32 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.32 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.32 mark(s(X)) -> s(mark(X)) 5.86/2.32 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.32 a__length(X) -> length(X) 5.86/2.32 a__and(X1, X2) -> and(X1, X2) 5.86/2.32 5.86/2.32 The set Q consists of the following terms: 5.86/2.32 5.86/2.32 a__zeros 5.86/2.32 a__isNatIList(x0) 5.86/2.32 mark(zeros) 5.86/2.32 mark(U11(x0, x1)) 5.86/2.32 mark(length(x0)) 5.86/2.32 mark(and(x0, x1)) 5.86/2.32 mark(isNat(x0)) 5.86/2.32 mark(isNatList(x0)) 5.86/2.32 mark(isNatIList(x0)) 5.86/2.32 mark(cons(x0, x1)) 5.86/2.32 mark(0) 5.86/2.32 mark(tt) 5.86/2.32 mark(s(x0)) 5.86/2.32 mark(nil) 5.86/2.32 a__U11(x0, x1) 5.86/2.32 a__length(x0) 5.86/2.32 a__and(x0, x1) 5.86/2.32 a__isNat(x0) 5.86/2.32 a__isNatList(x0) 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (13) QTRSRRRProof (EQUIVALENT) 5.86/2.32 Used ordering: 5.86/2.32 Knuth-Bendix order [KBO] with precedence:mark_1 > a__zeros > cons_2 > a__length_1 > 0 > a__and_2 > and_2 > a__U11_2 > length_1 > U11_2 > a__isNat_1 > tt > zeros > s_1 5.86/2.32 5.86/2.32 and weight map: 5.86/2.32 5.86/2.32 a__zeros=3 5.86/2.32 0=1 5.86/2.32 zeros=1 5.86/2.32 tt=5 5.86/2.32 s_1=1 5.86/2.32 a__length_1=1 5.86/2.32 mark_1=2 5.86/2.32 a__isNat_1=4 5.86/2.32 length_1=1 5.86/2.32 cons_2=0 5.86/2.32 a__U11_2=0 5.86/2.32 U11_2=0 5.86/2.32 and_2=0 5.86/2.32 a__and_2=0 5.86/2.32 5.86/2.32 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.86/2.32 5.86/2.32 a__zeros -> cons(0, zeros) 5.86/2.32 a__U11(tt, L) -> s(a__length(mark(L))) 5.86/2.32 a__isNat(0) -> tt 5.86/2.32 a__isNat(s(V1)) -> a__isNat(V1) 5.86/2.32 mark(zeros) -> a__zeros 5.86/2.32 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 5.86/2.32 mark(length(X)) -> a__length(mark(X)) 5.86/2.32 mark(and(X1, X2)) -> a__and(mark(X1), X2) 5.86/2.32 mark(cons(X1, X2)) -> cons(mark(X1), X2) 5.86/2.32 mark(s(X)) -> s(mark(X)) 5.86/2.32 a__U11(X1, X2) -> U11(X1, X2) 5.86/2.32 a__length(X) -> length(X) 5.86/2.32 a__and(X1, X2) -> and(X1, X2) 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (14) 5.86/2.32 Obligation: 5.86/2.32 Q restricted rewrite system: 5.86/2.32 R is empty. 5.86/2.32 The set Q consists of the following terms: 5.86/2.32 5.86/2.32 a__zeros 5.86/2.32 a__isNatIList(x0) 5.86/2.32 mark(zeros) 5.86/2.32 mark(U11(x0, x1)) 5.86/2.32 mark(length(x0)) 5.86/2.32 mark(and(x0, x1)) 5.86/2.32 mark(isNat(x0)) 5.86/2.32 mark(isNatList(x0)) 5.86/2.32 mark(isNatIList(x0)) 5.86/2.32 mark(cons(x0, x1)) 5.86/2.32 mark(0) 5.86/2.32 mark(tt) 5.86/2.32 mark(s(x0)) 5.86/2.32 mark(nil) 5.86/2.32 a__U11(x0, x1) 5.86/2.32 a__length(x0) 5.86/2.32 a__and(x0, x1) 5.86/2.32 a__isNat(x0) 5.86/2.32 a__isNatList(x0) 5.86/2.32 5.86/2.32 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (15) RisEmptyProof (EQUIVALENT) 5.86/2.32 The TRS R is empty. Hence, termination is trivially proven. 5.86/2.32 ---------------------------------------- 5.86/2.32 5.86/2.32 (16) 5.86/2.32 YES 5.99/2.35 EOF