YES Problem 1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR vNonEmpty x y) (REPLACEMENT-MAP (+ 1, 2) (- 1, 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(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: CSR Converter From Canonical u-Replacement Map Procedure [CSUR20]: Original Replacement Map: (+ 1 2) (- 1 2) (p 1) (s 1) (0) (fSNonEmpty) New Replacement Map: (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) New problem: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR vNonEmpty x y) (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(x,y)) -(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Problem 1: Termination Procedure: Terminating? YES Problem 1: (VAR vu95NonEmpty vNonEmpty x y) (STRATEGY CONTEXTSENSITIVE (u43 2) (u45 2) (p 1) (s 1) (num0) (fSNonEmpty) ) (RULES u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ) Problem 1: Dependency Pairs Processor: -> Pairs: 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)) U43(x,num0) -> x U45(x,p(y)) -> U45(x,y) U45(x,p(y)) -> S(u45(x,y)) U45(x,s(y)) -> U45(x,y) U45(x,s(y)) -> P(u45(x,y)) U45(x,num0) -> x -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding Rules: Empty Problem 1: SCC Processor: -> Pairs: 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)) U43(x,num0) -> x U45(x,p(y)) -> U45(x,y) U45(x,p(y)) -> S(u45(x,y)) U45(x,s(y)) -> U45(x,y) U45(x,s(y)) -> P(u45(x,y)) U45(x,num0) -> x -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding rules: Empty ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U45(x,p(y)) -> U45(x,y) U45(x,s(y)) -> U45(x,y) ->->-> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->->-> Unhiding rules: Empty ->->Cycle: ->->-> Pairs: U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) ->->-> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x ->->-> Unhiding rules: Empty The problem is decomposed in 2 subproblems. Problem 1.1: SubNColl Processor: -> Pairs: U45(x,p(y)) -> U45(x,y) U45(x,s(y)) -> U45(x,y) -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding rules: Empty ->Projection: pi(U45) = 2 Problem 1.1: Basic Processor: -> Pairs: Empty -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding rules: Empty -> Result: Set P is empty The problem is finite. Problem 1.2: SubNColl Processor: -> Pairs: U43(x,p(y)) -> U43(x,y) U43(x,s(y)) -> U43(x,y) -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding rules: Empty ->Projection: pi(U43) = 2 Problem 1.2: Basic Processor: -> Pairs: Empty -> Rules: u43(x,p(y)) -> p(u43(x,y)) u43(x,s(y)) -> s(u43(x,y)) u43(x,num0) -> x u45(x,p(y)) -> s(u45(x,y)) u45(x,s(y)) -> p(u45(x,y)) u45(x,num0) -> x p(s(x)) -> x s(p(x)) -> x -> Unhiding rules: Empty -> Result: Set P is empty The problem is finite. Problem 1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR vNonEmpty x y) (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(x,y)) -(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Levy NW Procedure: -> Rules: +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(x,y)) -(x,0) -> x p(s(x)) -> x s(p(x)) -> x -> Vars: x, y, x, y, x, x, y, x, y, x, x, x -> UVars: (UV-RuleId: 1, UV-LActive: [x, y], UV-RActive: [x, y], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 2, UV-LActive: [x, y], UV-RActive: [x, y], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 3, UV-LActive: [x], UV-RActive: [x], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 4, UV-LActive: [x, y], UV-RActive: [x, y], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 5, UV-LActive: [x, y], UV-RActive: [x, y], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 6, UV-LActive: [x], UV-RActive: [x], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 7, UV-LActive: [x], UV-RActive: [x], UV-LFrozen: [], UV-RFrozen: []) (UV-RuleId: 8, UV-LActive: [x], UV-RActive: [x], UV-LFrozen: [], UV-RFrozen: []) -> Rlps: (rule: +(x,p(y)) -> p(+(x,y)), id: 1, possubterms: +(x,p(y))->[], p(y)->[2]) (rule: +(x,s(y)) -> s(+(x,y)), id: 2, possubterms: +(x,s(y))->[], s(y)->[2]) (rule: +(x,0) -> x, id: 3, possubterms: +(x,0)->[], 0->[2]) (rule: -(x,p(y)) -> s(-(x,y)), id: 4, possubterms: -(x,p(y))->[], p(y)->[2]) (rule: -(x,s(y)) -> p(-(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: [2], l: +(x,p(y)), lp: p(y), sig: {y -> s(x')}, l': p(s(x')), r: p(+(x,y)), r': x') (R2 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') (R4 unifies with R7 at p: [2], l: -(x,p(y)), lp: p(y), sig: {y -> s(x')}, l': p(s(x')), r: s(-(x,y)), r': x') (R5 unifies with R8 at p: [2], l: -(x,s(y)), lp: s(y), sig: {y -> p(x')}, l': s(p(x')), r: p(-(x,y)), r': x') (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: <+(x,x'),p(+(x,s(x')))> => Not trivial, Not overlay, Proper, NW0, N1 <-(x,x'),s(-(x,s(x')))> => Not trivial, Not overlay, Proper, NW0, N2 => Trivial, Not overlay, Proper, NW0, N3 => Trivial, Not overlay, Proper, NW0, N4 <+(x,x'),s(+(x,p(x')))> => Not trivial, Not overlay, Proper, NW0, N5 <-(x,x'),p(-(x,p(x')))> => Not trivial, Not overlay, Proper, NW0, N6 -> 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 CS-TRS, Left-homogeneous u-replacing variables The problem is decomposed in 4 subproblems. Problem 1.1: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(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, N1 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, R2, P[1], S{x7 -> x, x8 -> 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.2: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(x,y)) -(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <-(x,x'),s(-(x,s(x')))> => Not trivial, Not overlay, Proper, NW0, N2 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: -(x,x') Nodes: [0] Edges: [] ID: 0 => ('-(x,x')', D0) t: s(-(x,s(x'))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('s(-(x,s(x')))', D0) ID: 1 => ('s(p(-(x,x')))', D1, R5, P[1], S{x12 -> x, x13 -> 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,s(x'))) -> s(p(-(x,x'))) -> -(x,x') -(x,x') ->* -(x,x') *<- s(-(x,s(x'))) "Joinable" The problem is confluent. Problem 1.3: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(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, R1, P[1], S{x5 -> x, x6 -> 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.4: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Confluence Problem: (VAR x y x') (REPLACEMENT-MAP (+ 2) (- 2) (p 1) (s 1) (0) (fSNonEmpty) ) (RULES +(x,p(y)) -> p(+(x,y)) +(x,s(y)) -> s(+(x,y)) +(x,0) -> x -(x,p(y)) -> s(-(x,y)) -(x,s(y)) -> p(-(x,y)) -(x,0) -> x p(s(x)) -> x s(p(x)) -> x ) Critical Pairs: <-(x,x'),p(-(x,p(x')))> => Not trivial, Not overlay, Proper, NW0, N6 Terminating:"YES" ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Huet Brute Force Joinability Procedure: -> Rewritings: s: -(x,x') Nodes: [0] Edges: [] ID: 0 => ('-(x,x')', D0) t: p(-(x,p(x'))) Nodes: [0,1,2] Edges: [(0,1),(1,2)] ID: 0 => ('p(-(x,p(x')))', D0) ID: 1 => ('p(s(-(x,x')))', D1, R4, P[1], S{x10 -> x, x11 -> 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,p(x'))) -> p(s(-(x,x'))) -> -(x,x') -(x,x') ->* -(x,x') *<- p(-(x,p(x'))) "Joinable" The problem is confluent.