YES Problem 1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR vNonEmpty x y) (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Problem 1: Problem 1: Not CS-TRS Procedure: R is not a CS-TRS Problem 1: Termination Procedure: Terminating? YES Problem 1: (VAR vu95NonEmpty vNonEmpty x y) (RULES u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ) Problem 1: Dependency Pairs Processor: -> Pairs: U43(p(x),y) -> U43(x,y) U43(p(x),y) -> P(u43(x,y)) U43(s(x),y) -> U43(x,y) U43(s(x),y) -> S(u43(x,y)) U43(x,p(y)) -> U43(x,y) U43(x,p(y)) -> P(u43(x,y)) U43(x,s(y)) -> U43(x,y) U43(x,s(y)) -> S(u43(x,y)) -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x Problem 1: SCC Processor: -> Pairs: U43(p(x),y) -> U43(x,y) U43(p(x),y) -> P(u43(x,y)) U43(s(x),y) -> U43(x,y) U43(s(x),y) -> S(u43(x,y)) U43(x,p(y)) -> U43(x,y) U43(x,p(y)) -> P(u43(x,y)) U43(x,s(y)) -> U43(x,y) U43(x,s(y)) -> S(u43(x,y)) -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U43(p(x),y) -> U43(x,y) U43(s(x),y) -> U43(x,y) U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) ->->-> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x Problem 1: Subterm Processor: -> Pairs: U43(p(x),y) -> U43(x,y) U43(s(x),y) -> U43(x,y) U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->Projection: pi(U43) = 1 Problem 1: SCC Processor: -> Pairs: U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) ->->-> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x Problem 1: Subterm Processor: -> Pairs: U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->Projection: pi(U43) = 2 Problem 1: SCC Processor: -> Pairs: Empty -> Rules: u43(p(x),y) -> p(u43(x,y)) u43(s(x),y) -> s(u43(x,y)) u43(num0,y) -> y u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR vNonEmpty x y) (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Levy NW Procedure: -> Rules: +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x -> Vars: x, y, x, y, y, x, y, x, y, x, x, x -> Rlps: (rule: +(p(x),y) -> p(+(x,y)), id: 1, possubterms: +(p(x),y)->[], p(x)->[1]) (rule: +(s(x),y) -> s(+(x,y)), id: 2, possubterms: +(s(x),y)->[], s(x)->[1]) (rule: +(0,y) -> y, id: 3, possubterms: +(0,y)->[], 0->[1]) (rule: +(x,p(y)) -> p(+(x,y)), id: 4, possubterms: +(x,p(y))->[], p(y)->[2]) (rule: +(x,s(y)) -> s(+(x,y)), id: 5, possubterms: +(x,s(y))->[], s(y)->[2]) (rule: +(x,0) -> x, id: 6, possubterms: +(x,0)->[], 0->[2]) (rule: p(s(x)) -> x, id: 7, possubterms: p(s(x))->[], s(x)->[1]) (rule: s(p(x)) -> x, id: 8, possubterms: s(p(x))->[], p(x)->[1]) -> Unifications: (R1 unifies with R7 at p: [1], l: +(p(x),y), lp: p(x), sig: {x -> s(x')}, l': p(s(x')), r: p(+(x,y)), r': x') (R2 unifies with R8 at p: [1], l: +(s(x),y), lp: s(x), sig: {x -> p(x')}, l': s(p(x')), r: s(+(x,y)), r': x') (R4 unifies with R1 at p: [], l: +(x,p(y)), lp: +(x,p(y)), sig: {x -> p(x'),y' -> p(y)}, l': +(p(x'),y'), r: p(+(x,y)), r': p(+(x',y'))) (R4 unifies with R2 at p: [], l: +(x,p(y)), lp: +(x,p(y)), sig: {x -> s(x'),y' -> p(y)}, l': +(s(x'),y'), r: p(+(x,y)), r': s(+(x',y'))) (R4 unifies with R3 at p: [], l: +(x,p(y)), lp: +(x,p(y)), sig: {x -> 0,y' -> p(y)}, l': +(0,y'), r: p(+(x,y)), r': y') (R4 unifies with R7 at p: [2], l: +(x,p(y)), lp: p(y), sig: {y -> s(x')}, l': p(s(x')), r: p(+(x,y)), r': x') (R5 unifies with R1 at p: [], l: +(x,s(y)), lp: +(x,s(y)), sig: {x -> p(x'),y' -> s(y)}, l': +(p(x'),y'), r: s(+(x,y)), r': p(+(x',y'))) (R5 unifies with R2 at p: [], l: +(x,s(y)), lp: +(x,s(y)), sig: {x -> s(x'),y' -> s(y)}, l': +(s(x'),y'), r: s(+(x,y)), r': s(+(x',y'))) (R5 unifies with R3 at p: [], l: +(x,s(y)), lp: +(x,s(y)), sig: {x -> 0,y' -> s(y)}, l': +(0,y'), r: s(+(x,y)), r': y') (R5 unifies with R8 at p: [2], l: +(x,s(y)), lp: s(y), sig: {y -> p(x')}, l': s(p(x')), r: s(+(x,y)), r': x') (R6 unifies with R1 at p: [], l: +(x,0), lp: +(x,0), sig: {x -> p(x'),y -> 0}, l': +(p(x'),y), r: x, r': p(+(x',y))) (R6 unifies with R2 at p: [], l: +(x,0), lp: +(x,0), sig: {x -> s(x'),y -> 0}, l': +(s(x'),y), r: x, r': s(+(x',y))) (R6 unifies with R3 at p: [], l: +(x,0), lp: +(x,0), sig: {x -> 0,y -> 0}, l': +(0,y), r: x, r': y) (R7 unifies with R8 at p: [1], l: p(s(x)), lp: s(x), sig: {x -> p(x')}, l': s(p(x')), r: x, r': x') (R8 unifies with R7 at p: [1], l: s(p(x)), lp: p(x), sig: {x -> s(x')}, l': p(s(x')), r: x, r': x') -> Critical pairs info: <0,0> => Trivial, Overlay, Proper, NW2, N1 <+(x',y),s(+(p(x'),y))> => Not trivial, Not overlay, Proper, NW0, N2 <+(x',y),p(+(s(x'),y))> => Not trivial, Not overlay, Proper, NW0, N3 => Not trivial, Overlay, Proper, NW0, N4 <+(x,x'),s(+(x,p(x')))> => Not trivial, Not overlay, Proper, NW0, N5 => Not trivial, Overlay, Proper, NW0, N6 => Not trivial, Overlay, Proper, NW0, N7 => Not trivial, Overlay, Proper, NW0, N8 => Trivial, Not overlay, Proper, NW0, N9 => Not trivial, Overlay, Proper, NW0, N10 <+(x,x'),p(+(x,s(x')))> => Not trivial, Not overlay, Proper, NW0, N11 => Not trivial, Overlay, Proper, NW0, N12 => Not trivial, Overlay, Proper, NW0, N13 => Trivial, Not overlay, Proper, NW0, N14 => Not trivial, Overlay, Proper, NW0, N15 -> Problem conclusions: Left linear, Right linear, Linear Not weakly orthogonal, Not almost orthogonal, Not orthogonal Not Huet-Levy confluent, Not Newman confluent R is a TRS The problem is decomposed in 12 subproblems. Problem 1.1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <+(x',y),s(+(p(x'),y))> => Not trivial, Not overlay, Proper, NW0, N2 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: +(x',y) Nodes: [0] Edges: [] ID: 0 => ('+(x',y)', D0) t: s(+(p(x'),y)) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('s(+(p(x'),y))', D0) ID: 1 => ('s(p(+(x',y)))', D1, R1, P[1], S{x5 -> x', x6 -> y}), NR: 'p(+(x',y))' ID: 2 => ('+(x',y)', D2, R8, P[], S{x16 -> +(x',y)}), NR: '+(x',y)' SNodesPath: +(x',y) TNodesPath: s(+(p(x'),y)) -> s(p(+(x',y))) -> +(x',y) +(x',y) ->* +(x',y) *<- s(+(p(x'),y)) "Joinable" The problem is confluent. Problem 1.2: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <+(x',y),p(+(s(x'),y))> => Not trivial, Not overlay, Proper, NW0, N3 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: +(x',y) Nodes: [0] Edges: [] ID: 0 => ('+(x',y)', D0) t: p(+(s(x'),y)) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('p(+(s(x'),y))', D0) ID: 1 => ('p(s(+(x',y)))', D1, R2, P[1], S{x7 -> x', x8 -> y}), NR: 's(+(x',y))' ID: 2 => ('+(x',y)', D2, R7, P[], S{x15 -> +(x',y)}), NR: '+(x',y)' SNodesPath: +(x',y) TNodesPath: p(+(s(x'),y)) -> p(s(+(x',y))) -> +(x',y) +(x',y) ->* +(x',y) *<- p(+(s(x'),y)) "Joinable" The problem is confluent. Problem 1.3: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N4 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: p(+(x',0)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('p(+(x',0))', D0) ID: 1 => ('p(x')', D1, R6, P[1], S{x14 -> x'}), NR: 'x'' t: p(x') Nodes: [0] Edges: [] ID: 0 => ('p(x')', D0) SNodesPath: p(+(x',0)) -> p(x') TNodesPath: p(x') p(+(x',0)) ->* p(x') *<- p(x') "Joinable" The problem is confluent. Problem 1.4: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <+(x,x'),s(+(x,p(x')))> => Not trivial, Not overlay, Proper, NW0, N5 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: +(x,x') Nodes: [0] Edges: [] ID: 0 => ('+(x,x')', D0) t: s(+(x,p(x'))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('s(+(x,p(x')))', D0) ID: 1 => ('s(p(+(x,x')))', D1, R4, P[1], S{x10 -> x, x11 -> x'}), NR: 'p(+(x,x'))' ID: 2 => ('+(x,x')', D2, R8, P[], S{x16 -> +(x,x')}), NR: '+(x,x')' SNodesPath: +(x,x') TNodesPath: s(+(x,p(x'))) -> s(p(+(x,x'))) -> +(x,x') +(x,x') ->* +(x,x') *<- s(+(x,p(x'))) "Joinable" The problem is confluent. Problem 1.5: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N6 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: s(+(x',s(y))) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('s(+(x',s(y)))', D0) ID: 1 => ('s(s(+(x',y)))', D1, R5, P[1], S{x12 -> x', x13 -> y}), NR: 's(+(x',y))' t: s(+(s(x'),y)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('s(+(s(x'),y))', D0) ID: 1 => ('s(s(+(x',y)))', D1, R2, P[1], S{x7 -> x', x8 -> y}), NR: 's(+(x',y))' SNodesPath: s(+(x',s(y))) -> s(s(+(x',y))) TNodesPath: s(+(s(x'),y)) -> s(s(+(x',y))) s(+(x',s(y))) ->* s(s(+(x',y))) *<- s(+(s(x'),y)) "Joinable" The problem is confluent. Problem 1.6: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N7 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: s(+(x',p(y))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('s(+(x',p(y)))', D0) ID: 1 => ('s(p(+(x',y)))', D1, R4, P[1], S{x10 -> x', x11 -> y}), NR: 'p(+(x',y))' ID: 2 => ('+(x',y)', D2, R8, P[], S{x16 -> +(x',y)}), NR: '+(x',y)' t: p(+(s(x'),y)) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('p(+(s(x'),y))', D0) ID: 1 => ('p(s(+(x',y)))', D1, R2, P[1], S{x7 -> x', x8 -> y}), NR: 's(+(x',y))' ID: 2 => ('+(x',y)', D2, R7, P[], S{x15 -> +(x',y)}), NR: '+(x',y)' SNodesPath: s(+(x',p(y))) -> s(p(+(x',y))) -> +(x',y) TNodesPath: p(+(s(x'),y)) -> p(s(+(x',y))) -> +(x',y) s(+(x',p(y))) ->* +(x',y) *<- p(+(s(x'),y)) "Joinable" The problem is confluent. Problem 1.7: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N8 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: p(+(x',p(y))) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('p(+(x',p(y)))', D0) ID: 1 => ('p(p(+(x',y)))', D1, R4, P[1], S{x10 -> x', x11 -> y}), NR: 'p(+(x',y))' t: p(+(p(x'),y)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('p(+(p(x'),y))', D0) ID: 1 => ('p(p(+(x',y)))', D1, R1, P[1], S{x5 -> x', x6 -> y}), NR: 'p(+(x',y))' SNodesPath: p(+(x',p(y))) -> p(p(+(x',y))) TNodesPath: p(+(p(x'),y)) -> p(p(+(x',y))) p(+(x',p(y))) ->* p(p(+(x',y))) *<- p(+(p(x'),y)) "Joinable" The problem is confluent. Problem 1.8: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N10 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: s(y) Nodes: [0] Edges: [] ID: 0 => ('s(y)', D0) t: s(+(0,y)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('s(+(0,y))', D0) ID: 1 => ('s(y)', D1, R3, P[1], S{x9 -> y}), NR: 'y' SNodesPath: s(y) TNodesPath: s(+(0,y)) -> s(y) s(y) ->* s(y) *<- s(+(0,y)) "Joinable" The problem is confluent. Problem 1.9: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <+(x,x'),p(+(x,s(x')))> => Not trivial, Not overlay, Proper, NW0, N11 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: +(x,x') Nodes: [0] Edges: [] ID: 0 => ('+(x,x')', D0) t: p(+(x,s(x'))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('p(+(x,s(x')))', D0) ID: 1 => ('p(s(+(x,x')))', D1, R5, P[1], S{x12 -> x, x13 -> x'}), NR: 's(+(x,x'))' ID: 2 => ('+(x,x')', D2, R7, P[], S{x15 -> +(x,x')}), NR: '+(x,x')' SNodesPath: +(x,x') TNodesPath: p(+(x,s(x'))) -> p(s(+(x,x'))) -> +(x,x') +(x,x') ->* +(x,x') *<- p(+(x,s(x'))) "Joinable" The problem is confluent. Problem 1.10: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N12 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: p(+(x',s(y))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('p(+(x',s(y)))', D0) ID: 1 => ('p(s(+(x',y)))', D1, R5, P[1], S{x12 -> x', x13 -> y}), NR: 's(+(x',y))' ID: 2 => ('+(x',y)', D2, R7, P[], S{x15 -> +(x',y)}), NR: '+(x',y)' t: s(+(p(x'),y)) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('s(+(p(x'),y))', D0) ID: 1 => ('s(p(+(x',y)))', D1, R1, P[1], S{x5 -> x', x6 -> y}), NR: 'p(+(x',y))' ID: 2 => ('+(x',y)', D2, R8, P[], S{x16 -> +(x',y)}), NR: '+(x',y)' SNodesPath: p(+(x',s(y))) -> p(s(+(x',y))) -> +(x',y) TNodesPath: s(+(p(x'),y)) -> s(p(+(x',y))) -> +(x',y) p(+(x',s(y))) ->* +(x',y) *<- s(+(p(x'),y)) "Joinable" The problem is confluent. Problem 1.11: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N13 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: s(+(x',0)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('s(+(x',0))', D0) ID: 1 => ('s(x')', D1, R6, P[1], S{x14 -> x'}), NR: 'x'' t: s(x') Nodes: [0] Edges: [] ID: 0 => ('s(x')', D0) SNodesPath: s(+(x',0)) -> s(x') TNodesPath: s(x') s(+(x',0)) ->* s(x') *<- s(x') "Joinable" The problem is confluent. Problem 1.12: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(p(x),y) -> p(+(x,y)) +(s(x),y) -> s(+(x,y)) +(0,y) -> y +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: => Not trivial, Overlay, Proper, NW0, N15 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: p(y) Nodes: [0] Edges: [] ID: 0 => ('p(y)', D0) t: p(+(0,y)) Nodes: [0,1] Edges: [(0,1)] ID: 0 => ('p(+(0,y))', D0) ID: 1 => ('p(y)', D1, R3, P[1], S{x9 -> y}), NR: 'y' SNodesPath: p(y) TNodesPath: p(+(0,y)) -> p(y) p(y) ->* p(y) *<- p(+(0,y)) "Joinable" The problem is confluent.