12.52/3.81 NO 12.52/3.81 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 12.52/3.81 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.52/3.81 12.52/3.81 12.52/3.81 Outermost Termination of the given OTRS could be disproven: 12.52/3.81 12.52/3.81 (0) OTRS 12.52/3.81 (1) OutermostNonTerminationProof [COMPLETE, 1244 ms] 12.52/3.81 (2) NO 12.52/3.81 12.52/3.81 12.52/3.81 ---------------------------------------- 12.52/3.81 12.52/3.81 (0) 12.52/3.81 Obligation: 12.52/3.81 Term rewrite system R: 12.52/3.81 The TRS R consists of the following rules: 12.52/3.81 12.52/3.81 and(tt, T) -> T 12.52/3.81 isNatIList(IL) -> isNatList(activate(IL)) 12.52/3.81 isNat(n__0) -> tt 12.52/3.81 isNat(n__s(N)) -> isNat(activate(N)) 12.52/3.81 isNat(n__length(L)) -> isNatList(activate(L)) 12.52/3.81 isNatIList(n__zeros) -> tt 12.52/3.81 isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL))) 12.52/3.81 isNatList(n__nil) -> tt 12.52/3.81 isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L))) 12.52/3.81 isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL))) 12.52/3.81 zeros -> cons(0, n__zeros) 12.52/3.81 take(0, IL) -> uTake1(isNatIList(IL)) 12.52/3.81 uTake1(tt) -> nil 12.52/3.81 take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL)) 12.52/3.81 uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL))) 12.52/3.81 length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L)) 12.52/3.81 uLength(tt, L) -> s(length(activate(L))) 12.52/3.81 0 -> n__0 12.52/3.81 s(X) -> n__s(X) 12.52/3.81 length(X) -> n__length(X) 12.52/3.81 zeros -> n__zeros 12.52/3.81 cons(X1, X2) -> n__cons(X1, X2) 12.52/3.81 nil -> n__nil 12.52/3.81 take(X1, X2) -> n__take(X1, X2) 12.52/3.81 activate(n__0) -> 0 12.52/3.81 activate(n__s(X)) -> s(X) 12.52/3.81 activate(n__length(X)) -> length(X) 12.52/3.81 activate(n__zeros) -> zeros 12.52/3.81 activate(n__cons(X1, X2)) -> cons(X1, X2) 12.52/3.81 activate(n__nil) -> nil 12.52/3.81 activate(n__take(X1, X2)) -> take(X1, X2) 12.52/3.81 activate(X) -> X 12.52/3.81 12.52/3.81 12.52/3.81 12.52/3.81 Outermost Strategy. 12.52/3.81 12.52/3.81 ---------------------------------------- 12.52/3.81 12.52/3.81 (1) OutermostNonTerminationProof (COMPLETE) 12.52/3.81 Term rewrite system R: 12.52/3.81 The TRS R consists of the following rules: 12.52/3.81 12.52/3.81 and(tt, T) -> T 12.52/3.81 isNatIList(IL) -> isNatList(activate(IL)) 12.52/3.81 isNat(n__0) -> tt 12.52/3.81 isNat(n__s(N)) -> isNat(activate(N)) 12.52/3.81 isNat(n__length(L)) -> isNatList(activate(L)) 12.52/3.81 isNatIList(n__zeros) -> tt 12.52/3.81 isNatIList(n__cons(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL))) 12.52/3.81 isNatList(n__nil) -> tt 12.52/3.81 isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L))) 12.52/3.81 isNatList(n__take(N, IL)) -> and(isNat(activate(N)), isNatIList(activate(IL))) 12.52/3.81 zeros -> cons(0, n__zeros) 12.52/3.81 take(0, IL) -> uTake1(isNatIList(IL)) 12.52/3.81 uTake1(tt) -> nil 12.52/3.81 take(s(M), cons(N, IL)) -> uTake2(and(isNat(M), and(isNat(N), isNatIList(activate(IL)))), M, N, activate(IL)) 12.52/3.81 uTake2(tt, M, N, IL) -> cons(activate(N), n__take(activate(M), activate(IL))) 12.52/3.81 length(cons(N, L)) -> uLength(and(isNat(N), isNatList(activate(L))), activate(L)) 12.52/3.81 uLength(tt, L) -> s(length(activate(L))) 12.52/3.81 0 -> n__0 12.52/3.81 s(X) -> n__s(X) 12.52/3.81 length(X) -> n__length(X) 12.52/3.81 zeros -> n__zeros 12.52/3.81 cons(X1, X2) -> n__cons(X1, X2) 12.52/3.81 nil -> n__nil 12.52/3.81 take(X1, X2) -> n__take(X1, X2) 12.52/3.81 activate(n__0) -> 0 12.52/3.81 activate(n__s(X)) -> s(X) 12.52/3.81 activate(n__length(X)) -> length(X) 12.52/3.81 activate(n__zeros) -> zeros 12.52/3.81 activate(n__cons(X1, X2)) -> cons(X1, X2) 12.52/3.81 activate(n__nil) -> nil 12.52/3.81 activate(n__take(X1, X2)) -> take(X1, X2) 12.52/3.81 activate(X) -> X 12.52/3.81 12.52/3.81 12.52/3.81 12.52/3.81 Outermost Strategy. 12.52/3.81 12.52/3.81 ---------- Loop: ---------- 12.52/3.81 12.52/3.81 isNatList(activate(n__zeros)) -> isNatList(zeros) with rule activate(n__zeros) -> zeros at position [0] and matcher [ ] 12.52/3.81 12.52/3.81 isNatList(zeros) -> isNatList(cons(0, n__zeros)) with rule zeros -> cons(0, n__zeros) at position [0] and matcher [ ] 12.52/3.81 12.52/3.81 isNatList(cons(0, n__zeros)) -> isNatList(n__cons(0, n__zeros)) with rule cons(X1, X2) -> n__cons(X1, X2) at position [0] and matcher [X1 / 0, X2 / n__zeros] 12.52/3.81 12.52/3.81 isNatList(n__cons(0, n__zeros)) -> and(isNat(activate(0)), isNatList(activate(n__zeros))) with rule isNatList(n__cons(N, L)) -> and(isNat(activate(N)), isNatList(activate(L))) at position [] and matcher [N / 0, L / n__zeros] 12.52/3.81 12.52/3.81 Now an instance of the first term with Matcher [ ] occurs in the last term at position [1]. 12.52/3.81 12.52/3.81 Context: and(isNat(activate(0)), []) 12.52/3.81 12.52/3.81 We used [THIEMANN_LOOPS_UNDER_STRATEGIES] to show that this Loop is an Outermost-Loop. 12.52/3.81 ---------------------------------------- 12.52/3.81 12.52/3.81 (2) 12.52/3.81 NO 12.85/3.87 EOF