YES Problem 1: (VAR v_NonEmpty:S @l:S @l1:S @l2:S @ls:S @x:S @xs:S) (RULES append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ) (STRATEGY INNERMOST) Problem 1: Dependency Pairs Processor: -> Pairs: APPEND(@l1:S,@l2:S) -> APPEND#1(@l1:S,@l2:S) APPEND#1(::(@x:S,@xs:S),@l2:S) -> APPEND(@xs:S,@l2:S) APPENDALL(@l:S) -> APPENDALL#1(@l:S) APPENDALL#1(::(@l1:S,@ls:S)) -> APPEND(@l1:S,appendAll(@ls:S)) APPENDALL#1(::(@l1:S,@ls:S)) -> APPENDALL(@ls:S) APPENDALL2(@l:S) -> APPENDALL2#1(@l:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPEND(appendAll(@l1:S),appendAll2(@ls:S)) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL(@l1:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL2(@ls:S) APPENDALL3(@l:S) -> APPENDALL3#1(@l:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPEND(appendAll2(@l1:S),appendAll3(@ls:S)) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL2(@l1:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL3(@ls:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil Problem 1: SCC Processor: -> Pairs: APPEND(@l1:S,@l2:S) -> APPEND#1(@l1:S,@l2:S) APPEND#1(::(@x:S,@xs:S),@l2:S) -> APPEND(@xs:S,@l2:S) APPENDALL(@l:S) -> APPENDALL#1(@l:S) APPENDALL#1(::(@l1:S,@ls:S)) -> APPEND(@l1:S,appendAll(@ls:S)) APPENDALL#1(::(@l1:S,@ls:S)) -> APPENDALL(@ls:S) APPENDALL2(@l:S) -> APPENDALL2#1(@l:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPEND(appendAll(@l1:S),appendAll2(@ls:S)) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL(@l1:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL2(@ls:S) APPENDALL3(@l:S) -> APPENDALL3#1(@l:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPEND(appendAll2(@l1:S),appendAll3(@ls:S)) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL2(@l1:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL3(@ls:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: APPEND(@l1:S,@l2:S) -> APPEND#1(@l1:S,@l2:S) APPEND#1(::(@x:S,@xs:S),@l2:S) -> APPEND(@xs:S,@l2:S) ->->-> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->->Cycle: ->->-> Pairs: APPENDALL(@l:S) -> APPENDALL#1(@l:S) APPENDALL#1(::(@l1:S,@ls:S)) -> APPENDALL(@ls:S) ->->-> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->->Cycle: ->->-> Pairs: APPENDALL2(@l:S) -> APPENDALL2#1(@l:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL2(@ls:S) ->->-> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->->Cycle: ->->-> Pairs: APPENDALL3(@l:S) -> APPENDALL3#1(@l:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL3(@ls:S) ->->-> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil The problem is decomposed in 4 subproblems. Problem 1.1: Subterm Processor: -> Pairs: APPEND(@l1:S,@l2:S) -> APPEND#1(@l1:S,@l2:S) APPEND#1(::(@x:S,@xs:S),@l2:S) -> APPEND(@xs:S,@l2:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Projection: pi(APPEND) = 1 pi(APPEND#1) = 1 Problem 1.1: SCC Processor: -> Pairs: APPEND(@l1:S,@l2:S) -> APPEND#1(@l1:S,@l2:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: APPENDALL(@l:S) -> APPENDALL#1(@l:S) APPENDALL#1(::(@l1:S,@ls:S)) -> APPENDALL(@ls:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Projection: pi(APPENDALL) = 1 pi(APPENDALL#1) = 1 Problem 1.2: SCC Processor: -> Pairs: APPENDALL(@l:S) -> APPENDALL#1(@l:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: APPENDALL2(@l:S) -> APPENDALL2#1(@l:S) APPENDALL2#1(::(@l1:S,@ls:S)) -> APPENDALL2(@ls:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Projection: pi(APPENDALL2) = 1 pi(APPENDALL2#1) = 1 Problem 1.3: SCC Processor: -> Pairs: APPENDALL2(@l:S) -> APPENDALL2#1(@l:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Subterm Processor: -> Pairs: APPENDALL3(@l:S) -> APPENDALL3#1(@l:S) APPENDALL3#1(::(@l1:S,@ls:S)) -> APPENDALL3(@ls:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Projection: pi(APPENDALL3) = 1 pi(APPENDALL3#1) = 1 Problem 1.4: SCC Processor: -> Pairs: APPENDALL3(@l:S) -> APPENDALL3#1(@l:S) -> Rules: append(@l1:S,@l2:S) -> append#1(@l1:S,@l2:S) append#1(::(@x:S,@xs:S),@l2:S) -> ::(@x:S,append(@xs:S,@l2:S)) append#1(nil,@l2:S) -> @l2:S appendAll(@l:S) -> appendAll#1(@l:S) appendAll#1(::(@l1:S,@ls:S)) -> append(@l1:S,appendAll(@ls:S)) appendAll#1(nil) -> nil appendAll2(@l:S) -> appendAll2#1(@l:S) appendAll2#1(::(@l1:S,@ls:S)) -> append(appendAll(@l1:S),appendAll2(@ls:S)) appendAll2#1(nil) -> nil appendAll3(@l:S) -> appendAll3#1(@l:S) appendAll3#1(::(@l1:S,@ls:S)) -> append(appendAll2(@l1:S),appendAll3(@ls:S)) appendAll3#1(nil) -> nil ->Strongly Connected Components: There is no strongly connected component The problem is finite.