2.73/1.34 NO 2.73/1.34 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 2.73/1.34 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 2.73/1.34 2.73/1.34 2.73/1.34 Outermost Termination of the given OTRS could be disproven: 2.73/1.34 2.73/1.34 (0) OTRS 2.73/1.34 (1) OutermostNonTerminationProof [COMPLETE, 0 ms] 2.73/1.34 (2) NO 2.73/1.34 2.73/1.34 2.73/1.34 ---------------------------------------- 2.73/1.34 2.73/1.34 (0) 2.73/1.34 Obligation: 2.73/1.34 Term rewrite system R: 2.73/1.34 The TRS R consists of the following rules: 2.73/1.34 2.73/1.34 U12(tt) -> snd(splitAt(N, XS)) 2.73/1.34 U161(tt) -> cons(N) 2.73/1.34 U172(tt) -> head(afterNth(N, XS)) 2.73/1.34 U182(tt) -> Y 2.73/1.34 U191(tt) -> pair(nil, XS) 2.73/1.34 U203(tt) -> U204(splitAt(N, XS)) 2.73/1.34 U204(pair(YS, ZS)) -> pair(cons(X), ZS) 2.73/1.34 U212(tt) -> XS 2.73/1.34 U22(tt) -> X 2.73/1.34 U222(tt) -> fst(splitAt(N, XS)) 2.73/1.34 U32(tt) -> N 2.73/1.34 U101(tt) -> U102(isLNat) 2.73/1.34 U102(tt) -> tt 2.73/1.34 U11(tt) -> U12(isLNat) 2.73/1.34 U111(tt) -> tt 2.73/1.34 U121(tt) -> tt 2.73/1.34 U131(tt) -> U132(isLNat) 2.73/1.34 U132(tt) -> tt 2.73/1.34 U141(tt) -> U142(isLNat) 2.73/1.34 U142(tt) -> tt 2.73/1.34 U151(tt) -> U152(isLNat) 2.73/1.34 U152(tt) -> tt 2.73/1.34 U171(tt) -> U172(isLNat) 2.73/1.34 U181(tt) -> U182(isLNat) 2.73/1.34 U201(tt) -> U202(isNatural) 2.73/1.34 U202(tt) -> U203(isLNat) 2.73/1.34 U21(tt) -> U22(isLNat) 2.73/1.34 U211(tt) -> U212(isLNat) 2.73/1.34 U221(tt) -> U222(isLNat) 2.73/1.34 U31(tt) -> U32(isLNat) 2.73/1.34 U41(tt) -> U42(isLNat) 2.73/1.34 U42(tt) -> tt 2.73/1.34 U51(tt) -> U52(isLNat) 2.73/1.34 U52(tt) -> tt 2.73/1.34 U61(tt) -> tt 2.73/1.34 U71(tt) -> tt 2.73/1.34 U81(tt) -> tt 2.73/1.34 U91(tt) -> tt 2.73/1.34 afterNth(N, XS) -> U11(isNatural) 2.73/1.34 fst(pair(X, Y)) -> U21(isLNat) 2.73/1.34 head(cons(N)) -> U31(isNatural) 2.73/1.34 isLNat -> tt 2.73/1.34 isLNat -> U41(isNatural) 2.73/1.34 isLNat -> U51(isNatural) 2.73/1.34 isLNat -> U61(isPLNat) 2.73/1.34 isLNat -> U71(isNatural) 2.73/1.34 isLNat -> U81(isPLNat) 2.73/1.34 isLNat -> U91(isLNat) 2.73/1.34 isLNat -> U101(isNatural) 2.73/1.34 isNatural -> tt 2.73/1.34 isNatural -> U111(isLNat) 2.73/1.34 isNatural -> U121(isNatural) 2.73/1.34 isNatural -> U131(isNatural) 2.73/1.34 isPLNat -> U141(isLNat) 2.73/1.34 isPLNat -> U151(isNatural) 2.73/1.34 natsFrom(N) -> U161(isNatural) 2.73/1.34 sel(N, XS) -> U171(isNatural) 2.73/1.34 snd(pair(X, Y)) -> U181(isLNat) 2.73/1.34 splitAt(0, XS) -> U191(isLNat) 2.73/1.34 splitAt(s(N), cons(X)) -> U201(isNatural) 2.73/1.34 tail(cons(N)) -> U211(isNatural) 2.73/1.34 take(N, XS) -> U221(isNatural) 2.73/1.34 2.73/1.34 2.73/1.34 2.73/1.34 Outermost Strategy. 2.73/1.34 2.73/1.34 ---------------------------------------- 2.73/1.34 2.73/1.34 (1) OutermostNonTerminationProof (COMPLETE) 2.73/1.34 Term rewrite system R: 2.73/1.34 The TRS R consists of the following rules: 2.73/1.34 2.73/1.34 U12(tt) -> snd(splitAt(N, XS)) 2.73/1.34 U161(tt) -> cons(N) 2.73/1.34 U172(tt) -> head(afterNth(N, XS)) 2.73/1.34 U182(tt) -> Y 2.73/1.34 U191(tt) -> pair(nil, XS) 2.73/1.34 U203(tt) -> U204(splitAt(N, XS)) 2.73/1.34 U204(pair(YS, ZS)) -> pair(cons(X), ZS) 2.73/1.34 U212(tt) -> XS 2.73/1.34 U22(tt) -> X 2.73/1.34 U222(tt) -> fst(splitAt(N, XS)) 2.73/1.34 U32(tt) -> N 2.73/1.34 U101(tt) -> U102(isLNat) 2.73/1.34 U102(tt) -> tt 2.73/1.34 U11(tt) -> U12(isLNat) 2.73/1.34 U111(tt) -> tt 2.73/1.34 U121(tt) -> tt 2.73/1.34 U131(tt) -> U132(isLNat) 2.73/1.34 U132(tt) -> tt 2.73/1.34 U141(tt) -> U142(isLNat) 2.73/1.34 U142(tt) -> tt 2.73/1.34 U151(tt) -> U152(isLNat) 2.73/1.34 U152(tt) -> tt 2.73/1.34 U171(tt) -> U172(isLNat) 2.73/1.34 U181(tt) -> U182(isLNat) 2.73/1.34 U201(tt) -> U202(isNatural) 2.73/1.34 U202(tt) -> U203(isLNat) 2.73/1.34 U21(tt) -> U22(isLNat) 2.73/1.34 U211(tt) -> U212(isLNat) 2.73/1.34 U221(tt) -> U222(isLNat) 2.73/1.34 U31(tt) -> U32(isLNat) 2.73/1.34 U41(tt) -> U42(isLNat) 2.73/1.34 U42(tt) -> tt 2.73/1.34 U51(tt) -> U52(isLNat) 2.73/1.34 U52(tt) -> tt 2.73/1.34 U61(tt) -> tt 2.73/1.34 U71(tt) -> tt 2.73/1.34 U81(tt) -> tt 2.73/1.34 U91(tt) -> tt 2.73/1.34 afterNth(N, XS) -> U11(isNatural) 2.73/1.34 fst(pair(X, Y)) -> U21(isLNat) 2.73/1.34 head(cons(N)) -> U31(isNatural) 2.73/1.34 isLNat -> tt 2.73/1.34 isLNat -> U41(isNatural) 2.73/1.34 isLNat -> U51(isNatural) 2.73/1.34 isLNat -> U61(isPLNat) 2.73/1.34 isLNat -> U71(isNatural) 2.73/1.34 isLNat -> U81(isPLNat) 2.73/1.34 isLNat -> U91(isLNat) 2.73/1.34 isLNat -> U101(isNatural) 2.73/1.34 isNatural -> tt 2.73/1.34 isNatural -> U111(isLNat) 2.73/1.34 isNatural -> U121(isNatural) 2.73/1.34 isNatural -> U131(isNatural) 2.73/1.34 isPLNat -> U141(isLNat) 2.73/1.34 isPLNat -> U151(isNatural) 2.73/1.34 natsFrom(N) -> U161(isNatural) 2.73/1.34 sel(N, XS) -> U171(isNatural) 2.73/1.34 snd(pair(X, Y)) -> U181(isLNat) 2.73/1.34 splitAt(0, XS) -> U191(isLNat) 2.73/1.34 splitAt(s(N), cons(X)) -> U201(isNatural) 2.73/1.34 tail(cons(N)) -> U211(isNatural) 2.73/1.34 take(N, XS) -> U221(isNatural) 2.73/1.34 2.73/1.34 2.73/1.34 2.73/1.34 Outermost Strategy. 2.73/1.34 2.73/1.34 ---------- Loop: ---------- 2.73/1.34 2.73/1.34 U12(tt) -> snd(splitAt(U12(tt), U12(tt))) with rule U12(tt) -> snd(splitAt(N, XS)) at position [] and matcher [N / U12(tt), XS / U12(tt)] 2.73/1.34 2.73/1.34 Now an instance of the first term with Matcher [ ] occurs in the last term at position [0,1]. 2.73/1.34 2.73/1.34 Context: snd(splitAt(U12(tt), [])) 2.73/1.34 2.73/1.34 We used [THIEMANN_LOOPS_UNDER_STRATEGIES] to show that this Loop is an Outermost-Loop. 2.73/1.34 ---------------------------------------- 2.73/1.34 2.73/1.34 (2) 2.73/1.34 NO 2.73/1.37 EOF