YES Problem 1: (VAR v_NonEmpty:S a:S s:S t:S u:S) (RULES circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ) Problem 1: Dependency Pairs Processor: -> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(s:S,circ(t:S,u:S)) CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S Problem 1: SCC Processor: -> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(s:S,circ(t:S,u:S)) CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(s:S,circ(t:S,u:S)) CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) ->->-> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S Problem 1: Reduction Pair Processor: -> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(s:S,circ(t:S,u:S)) CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S -> Usable rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [circ](X1,X2) = X1.X2 + 2.X1 + 2.X2 + 2 [msubst](X1,X2) = X1.X2 + 2.X1 + 2.X2 + 2 [cons](X1,X2) = X1 + X2 + 2 [id] = 1 [lift] = 0 [CIRC](X1,X2) = X1.X2 + 2.X1 + 1 [MSUBST](X1,X2) = X1.X2 + 2.X1 + 2.X2 Problem 1: SCC Processor: -> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) ->->-> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S Problem 1: Reduction Pair Processor: -> Pairs: CIRC(circ(s:S,t:S),u:S) -> CIRC(t:S,u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S -> Usable rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [circ](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [msubst](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [cons](X1,X2) = 2.X1 + X2 + 2 [id] = 2 [lift] = 0 [CIRC](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2 [MSUBST](X1,X2) = X1.X2 + 2.X1 + X2 + 2 Problem 1: SCC Processor: -> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) ->->-> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S Problem 1: Reduction Pair Processor: -> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(cons(lift,circ(s:S,t:S)),u:S) CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S -> Usable rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [circ](X1,X2) = 2.X1.X2 + 2.X1 + 1 [msubst](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [cons](X1,X2) = 2.X1 + X2 + 2 [id] = 2 [lift] = 0 [CIRC](X1,X2) = 2.X1.X2 + 2.X1 + 1 [MSUBST](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 Problem 1: SCC Processor: -> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) ->->-> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S Problem 1: Subterm Processor: -> Pairs: CIRC(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(lift,t:S)) -> CIRC(s:S,t:S) CIRC(cons(lift,s:S),cons(a:S,t:S)) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> CIRC(s:S,t:S) CIRC(cons(a:S,s:S),t:S) -> MSUBST(a:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> CIRC(s:S,t:S) MSUBST(msubst(a:S,s:S),t:S) -> MSUBST(a:S,circ(s:S,t:S)) -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Projection: pi(CIRC) = 1 pi(MSUBST) = 1 Problem 1: SCC Processor: -> Pairs: Empty -> Rules: circ(circ(s:S,t:S),u:S) -> circ(s:S,circ(t:S,u:S)) circ(cons(lift,s:S),circ(cons(lift,t:S),u:S)) -> circ(cons(lift,circ(s:S,t:S)),u:S) circ(cons(lift,s:S),cons(lift,t:S)) -> cons(lift,circ(s:S,t:S)) circ(cons(lift,s:S),cons(a:S,t:S)) -> cons(a:S,circ(s:S,t:S)) circ(cons(a:S,s:S),t:S) -> cons(msubst(a:S,t:S),circ(s:S,t:S)) circ(id,s:S) -> s:S circ(s:S,id) -> s:S msubst(msubst(a:S,s:S),t:S) -> msubst(a:S,circ(s:S,t:S)) msubst(a:S,id) -> a:S subst(a:S,id) -> a:S ->Strongly Connected Components: There is no strongly connected component The problem is finite.