8.22/2.95 YES 8.27/2.97 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 8.27/2.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.27/2.97 8.27/2.97 8.27/2.97 Left Termination of the query pattern 8.27/2.97 8.27/2.97 rem(g,a,g) 8.27/2.97 8.27/2.97 w.r.t. the given Prolog program could successfully be proven: 8.27/2.97 8.27/2.97 (0) Prolog 8.27/2.97 (1) PrologToDTProblemTransformerProof [SOUND, 31 ms] 8.27/2.97 (2) TRIPLES 8.27/2.97 (3) TriplesToPiDPProof [SOUND, 0 ms] 8.27/2.97 (4) PiDP 8.27/2.97 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.27/2.97 (6) AND 8.27/2.97 (7) PiDP 8.27/2.97 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.27/2.97 (9) PiDP 8.27/2.97 (10) PiDPToQDPProof [SOUND, 0 ms] 8.27/2.97 (11) QDP 8.27/2.97 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.27/2.97 (13) YES 8.27/2.97 (14) PiDP 8.27/2.97 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.27/2.97 (16) PiDP 8.27/2.97 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.27/2.97 (18) QDP 8.27/2.97 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.27/2.97 (20) YES 8.27/2.97 (21) PiDP 8.27/2.97 (22) UsableRulesProof [EQUIVALENT, 0 ms] 8.27/2.97 (23) PiDP 8.27/2.97 (24) PiDPToQDPProof [SOUND, 0 ms] 8.27/2.97 (25) QDP 8.27/2.97 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.27/2.98 (27) YES 8.27/2.98 (28) PiDP 8.27/2.98 (29) UsableRulesProof [EQUIVALENT, 0 ms] 8.27/2.98 (30) PiDP 8.27/2.98 (31) PiDPToQDPProof [SOUND, 0 ms] 8.27/2.98 (32) QDP 8.27/2.98 (33) QDPQMonotonicMRRProof [EQUIVALENT, 22 ms] 8.27/2.98 (34) QDP 8.27/2.98 (35) PisEmptyProof [EQUIVALENT, 0 ms] 8.27/2.98 (36) YES 8.27/2.98 (37) PiDP 8.27/2.98 (38) UsableRulesProof [EQUIVALENT, 0 ms] 8.27/2.98 (39) PiDP 8.27/2.98 (40) PiDPToQDPProof [SOUND, 0 ms] 8.27/2.98 (41) QDP 8.27/2.98 (42) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.27/2.98 (43) YES 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (0) 8.27/2.98 Obligation: 8.27/2.98 Clauses: 8.27/2.98 8.27/2.98 rem(X, Y, R) :- ','(notZero(Y), ','(sub(X, Y, Z), rem(Z, Y, R))). 8.27/2.98 rem(X, Y, X) :- ','(notZero(Y), geq(X, Y)). 8.27/2.98 sub(s(X), s(Y), Z) :- sub(X, Y, Z). 8.27/2.98 sub(X, 0, X). 8.27/2.98 notZero(s(X)). 8.27/2.98 geq(s(X), s(Y)) :- geq(X, Y). 8.27/2.98 geq(X, 0). 8.27/2.98 8.27/2.98 8.27/2.98 Query: rem(g,a,g) 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (1) PrologToDTProblemTransformerProof (SOUND) 8.27/2.98 Built DT problem from termination graph DT10. 8.27/2.98 8.27/2.98 { 8.27/2.98 "root": 2, 8.27/2.98 "program": { 8.27/2.98 "directives": [], 8.27/2.98 "clauses": [ 8.27/2.98 [ 8.27/2.98 "(rem X Y R)", 8.27/2.98 "(',' (notZero Y) (',' (sub X Y Z) (rem Z Y R)))" 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(rem X Y X)", 8.27/2.98 "(',' (notZero Y) (geq X Y))" 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(sub (s X) (s Y) Z)", 8.27/2.98 "(sub X Y Z)" 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(sub X (0) X)", 8.27/2.98 null 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(notZero (s X))", 8.27/2.98 null 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(geq (s X) (s Y))", 8.27/2.98 "(geq X Y)" 8.27/2.98 ], 8.27/2.98 [ 8.27/2.98 "(geq X (0))", 8.27/2.98 null 8.27/2.98 ] 8.27/2.98 ] 8.27/2.98 }, 8.27/2.98 "graph": { 8.27/2.98 "nodes": { 8.27/2.98 "47": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 0, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T1 T2 T3)" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 1, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T1 T2 T3)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T1", 8.27/2.98 "T3" 8.27/2.98 ], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "48": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(',' (notZero T10) (',' (sub T7 T10 X7) (rem X7 T10 T9)))" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 1, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T7 T2 T9)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "type": "Nodes", 8.27/2.98 "370": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 6, 8.27/2.98 "scope": 6, 8.27/2.98 "term": "(geq T60 (s T68))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "250": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(sub T44 T46 X64)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T44"], 8.27/2.98 "free": ["X64"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "251": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "372": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(geq T79 T81)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T79"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "373": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "231": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(sub T7 (s T16) X7)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T7"], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "374": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 5, 8.27/2.98 "scope": 7, 8.27/2.98 "term": "(geq T79 T81)" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 6, 8.27/2.98 "scope": 7, 8.27/2.98 "term": "(geq T79 T81)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T79"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "232": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(rem T19 (s T20) T9)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T9", 8.27/2.98 "T20", 8.27/2.98 "T19" 8.27/2.98 ], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "377": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 5, 8.27/2.98 "scope": 7, 8.27/2.98 "term": "(geq T79 T81)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T79"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "235": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 2, 8.27/2.98 "scope": 3, 8.27/2.98 "term": "(sub T7 (s T16) X7)" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 3, 8.27/2.98 "scope": 3, 8.27/2.98 "term": "(sub T7 (s T16) X7)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T7"], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "378": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 6, 8.27/2.98 "scope": 7, 8.27/2.98 "term": "(geq T79 T81)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T79"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "236": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 2, 8.27/2.98 "scope": 3, 8.27/2.98 "term": "(sub T7 (s T16) X7)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T7"], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "379": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(geq T92 T94)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T92"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "237": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 3, 8.27/2.98 "scope": 3, 8.27/2.98 "term": "(sub T7 (s T16) X7)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T7"], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "380": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "360": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(',' (notZero T62) (geq T60 T62))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "240": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(sub T31 T33 X40)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T31"], 8.27/2.98 "free": ["X40"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "361": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "241": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "363": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 4, 8.27/2.98 "scope": 5, 8.27/2.98 "term": "(',' (notZero T62) (geq T60 T62))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "243": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 2, 8.27/2.98 "scope": 4, 8.27/2.98 "term": "(sub T31 T33 X40)" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 3, 8.27/2.98 "scope": 4, 8.27/2.98 "term": "(sub T31 T33 X40)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T31"], 8.27/2.98 "free": ["X40"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "342": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 1, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T7 T2 T9)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "386": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(true)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "2": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(rem T1 T2 T3)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T1", 8.27/2.98 "T3" 8.27/2.98 ], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "321": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(true)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "365": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(geq T60 (s T68))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "387": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "366": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "388": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "246": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 2, 8.27/2.98 "scope": 4, 8.27/2.98 "term": "(sub T31 T33 X40)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T31"], 8.27/2.98 "free": ["X40"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "323": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "389": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "225": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 4, 8.27/2.98 "scope": 2, 8.27/2.98 "term": "(',' (notZero T10) (',' (sub T7 T10 X7) (rem X7 T10 T9)))" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": -1, 8.27/2.98 "scope": 2, 8.27/2.98 "term": null 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 1, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T7 T2 T9)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "247": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 3, 8.27/2.98 "scope": 4, 8.27/2.98 "term": "(sub T31 T33 X40)" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T31"], 8.27/2.98 "free": ["X40"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "324": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "368": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": 5, 8.27/2.98 "scope": 6, 8.27/2.98 "term": "(geq T60 (s T68))" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 6, 8.27/2.98 "scope": 6, 8.27/2.98 "term": "(geq T60 (s T68))" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "226": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 4, 8.27/2.98 "scope": 2, 8.27/2.98 "term": "(',' (notZero T10) (',' (sub T7 T10 X7) (rem X7 T10 T9)))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "369": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": 5, 8.27/2.98 "scope": 6, 8.27/2.98 "term": "(geq T60 (s T68))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": ["T60"], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "227": { 8.27/2.98 "goal": [ 8.27/2.98 { 8.27/2.98 "clause": -1, 8.27/2.98 "scope": 2, 8.27/2.98 "term": null 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "clause": 1, 8.27/2.98 "scope": 1, 8.27/2.98 "term": "(rem T7 T2 T9)" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "326": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "228": { 8.27/2.98 "goal": [{ 8.27/2.98 "clause": -1, 8.27/2.98 "scope": -1, 8.27/2.98 "term": "(',' (sub T7 (s T16) X7) (rem X7 (s T16) T9))" 8.27/2.98 }], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [ 8.27/2.98 "T7", 8.27/2.98 "T9" 8.27/2.98 ], 8.27/2.98 "free": ["X7"], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "229": { 8.27/2.98 "goal": [], 8.27/2.98 "kb": { 8.27/2.98 "nonunifying": [], 8.27/2.98 "intvars": {}, 8.27/2.98 "arithmetic": { 8.27/2.98 "type": "PlainIntegerRelationState", 8.27/2.98 "relations": [] 8.27/2.98 }, 8.27/2.98 "ground": [], 8.27/2.98 "free": [], 8.27/2.98 "exprvars": [] 8.27/2.98 } 8.27/2.98 } 8.27/2.98 }, 8.27/2.98 "edges": [ 8.27/2.98 { 8.27/2.98 "from": 2, 8.27/2.98 "to": 47, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 47, 8.27/2.98 "to": 48, 8.27/2.98 "label": "ONLY EVAL with clause\nrem(X4, X5, X6) :- ','(notZero(X5), ','(sub(X4, X5, X7), rem(X7, X5, X6))).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T10,\nX5 -> T10,\nT3 -> T9,\nX6 -> T9,\nT8 -> T10" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 48, 8.27/2.98 "to": 225, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 225, 8.27/2.98 "to": 226, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 225, 8.27/2.98 "to": 227, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 226, 8.27/2.98 "to": 228, 8.27/2.98 "label": "EVAL with clause\nnotZero(s(X12)).\nand substitutionX12 -> T16,\nT10 -> s(T16),\nT15 -> T16" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 226, 8.27/2.98 "to": 229, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 227, 8.27/2.98 "to": 342, 8.27/2.98 "label": "FAILURE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 228, 8.27/2.98 "to": 231, 8.27/2.98 "label": "SPLIT 1" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 228, 8.27/2.98 "to": 232, 8.27/2.98 "label": "SPLIT 2\nnew knowledge:\nT7 is ground\nT20 is ground\nT19 is ground\nreplacements:X7 -> T19,\nT16 -> T20" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 231, 8.27/2.98 "to": 235, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 232, 8.27/2.98 "to": 2, 8.27/2.98 "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> s(T20)\nT3 -> T9" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 235, 8.27/2.98 "to": 236, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 235, 8.27/2.98 "to": 237, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 236, 8.27/2.98 "to": 240, 8.27/2.98 "label": "EVAL with clause\nsub(s(X37), s(X38), X39) :- sub(X37, X38, X39).\nand substitutionX37 -> T31,\nT7 -> s(T31),\nT16 -> T33,\nX38 -> T33,\nX7 -> X40,\nX39 -> X40,\nT32 -> T33" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 236, 8.27/2.98 "to": 241, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 237, 8.27/2.98 "to": 326, 8.27/2.98 "label": "BACKTRACK\nfor clause: sub(X, 0, X)because of non-unification" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 240, 8.27/2.98 "to": 243, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 243, 8.27/2.98 "to": 246, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 243, 8.27/2.98 "to": 247, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 246, 8.27/2.98 "to": 250, 8.27/2.98 "label": "EVAL with clause\nsub(s(X61), s(X62), X63) :- sub(X61, X62, X63).\nand substitutionX61 -> T44,\nT31 -> s(T44),\nX62 -> T46,\nT33 -> s(T46),\nX40 -> X64,\nX63 -> X64,\nT45 -> T46" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 246, 8.27/2.98 "to": 251, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 247, 8.27/2.98 "to": 321, 8.27/2.98 "label": "EVAL with clause\nsub(X71, 0, X71).\nand substitutionT31 -> T51,\nX71 -> T51,\nT33 -> 0,\nX40 -> T51" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 247, 8.27/2.98 "to": 323, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 250, 8.27/2.98 "to": 240, 8.27/2.98 "label": "INSTANCE with matching:\nT31 -> T44\nT33 -> T46\nX40 -> X64" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 321, 8.27/2.98 "to": 324, 8.27/2.98 "label": "SUCCESS" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 342, 8.27/2.98 "to": 360, 8.27/2.98 "label": "EVAL with clause\nrem(X81, X82, X81) :- ','(notZero(X82), geq(X81, X82)).\nand substitutionT7 -> T60,\nX81 -> T60,\nT2 -> T62,\nX82 -> T62,\nT9 -> T60,\nT61 -> T62" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 342, 8.27/2.98 "to": 361, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 360, 8.27/2.98 "to": 363, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 363, 8.27/2.98 "to": 365, 8.27/2.98 "label": "EVAL with clause\nnotZero(s(X87)).\nand substitutionX87 -> T68,\nT62 -> s(T68),\nT67 -> T68" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 363, 8.27/2.98 "to": 366, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 365, 8.27/2.98 "to": 368, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 368, 8.27/2.98 "to": 369, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 368, 8.27/2.98 "to": 370, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 369, 8.27/2.98 "to": 372, 8.27/2.98 "label": "EVAL with clause\ngeq(s(X98), s(X99)) :- geq(X98, X99).\nand substitutionX98 -> T79,\nT60 -> s(T79),\nT68 -> T81,\nX99 -> T81,\nT80 -> T81" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 369, 8.27/2.98 "to": 373, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 370, 8.27/2.98 "to": 389, 8.27/2.98 "label": "BACKTRACK\nfor clause: geq(X, 0)because of non-unification" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 372, 8.27/2.98 "to": 374, 8.27/2.98 "label": "CASE" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 374, 8.27/2.98 "to": 377, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 374, 8.27/2.98 "to": 378, 8.27/2.98 "label": "PARALLEL" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 377, 8.27/2.98 "to": 379, 8.27/2.98 "label": "EVAL with clause\ngeq(s(X110), s(X111)) :- geq(X110, X111).\nand substitutionX110 -> T92,\nT79 -> s(T92),\nX111 -> T94,\nT81 -> s(T94),\nT93 -> T94" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 377, 8.27/2.98 "to": 380, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 378, 8.27/2.98 "to": 386, 8.27/2.98 "label": "EVAL with clause\ngeq(X116, 0).\nand substitutionT79 -> T99,\nX116 -> T99,\nT81 -> 0" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 378, 8.27/2.98 "to": 387, 8.27/2.98 "label": "EVAL-BACKTRACK" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 379, 8.27/2.98 "to": 372, 8.27/2.98 "label": "INSTANCE with matching:\nT79 -> T92\nT81 -> T94" 8.27/2.98 }, 8.27/2.98 { 8.27/2.98 "from": 386, 8.27/2.98 "to": 388, 8.27/2.98 "label": "SUCCESS" 8.27/2.98 } 8.27/2.98 ], 8.27/2.98 "type": "Graph" 8.27/2.98 } 8.27/2.98 } 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (2) 8.27/2.98 Obligation: 8.27/2.98 Triples: 8.27/2.98 8.27/2.98 subD(s(X1), s(X2), X3) :- subD(X1, X2, X3). 8.27/2.98 geqC(s(X1), s(X2)) :- geqC(X1, X2). 8.27/2.98 remA(s(X1), s(X2), X3) :- subD(X1, X2, X4). 8.27/2.98 remA(X1, s(X2), X3) :- ','(subcB(X1, X2, X4), remA(X4, s(X2), X3)). 8.27/2.98 remA(s(X1), s(X2), s(X1)) :- geqC(X1, X2). 8.27/2.98 8.27/2.98 Clauses: 8.27/2.98 8.27/2.98 remcA(X1, s(X2), X3) :- ','(subcB(X1, X2, X4), remcA(X4, s(X2), X3)). 8.27/2.98 remcA(s(X1), s(X2), s(X1)) :- geqcC(X1, X2). 8.27/2.98 subcD(s(X1), s(X2), X3) :- subcD(X1, X2, X3). 8.27/2.98 subcD(X1, 0, X1). 8.27/2.98 geqcC(s(X1), s(X2)) :- geqcC(X1, X2). 8.27/2.98 geqcC(X1, 0). 8.27/2.98 subcB(s(X1), X2, X3) :- subcD(X1, X2, X3). 8.27/2.98 8.27/2.98 Afs: 8.27/2.98 8.27/2.98 remA(x1, x2, x3) = remA(x1, x3) 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (3) TriplesToPiDPProof (SOUND) 8.27/2.98 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.27/2.98 8.27/2.98 remA_in_3: (b,f,b) (b,b,b) 8.27/2.98 8.27/2.98 subD_in_3: (b,f,f) (b,b,f) 8.27/2.98 8.27/2.98 subcB_in_3: (b,f,f) (b,b,f) 8.27/2.98 8.27/2.98 subcD_in_3: (b,f,f) (b,b,f) 8.27/2.98 8.27/2.98 geqC_in_2: (b,b) (b,f) 8.27/2.98 8.27/2.98 Transforming TRIPLES into the following Term Rewriting System: 8.27/2.98 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), X3) -> U3_GAG(X1, X2, X3, subD_in_gaa(X1, X2, X4)) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X4) 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> U1_GAA(X1, X2, X3, subD_in_gaa(X1, X2, X3)) 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X3) 8.27/2.98 REMA_IN_GAG(X1, s(X2), X3) -> U4_GAG(X1, X2, X3, subcB_in_gaa(X1, X2, X4)) 8.27/2.98 U4_GAG(X1, X2, X3, subcB_out_gaa(X1, X2, X4)) -> U5_GAG(X1, X2, X3, remA_in_ggg(X4, s(X2), X3)) 8.27/2.98 U4_GAG(X1, X2, X3, subcB_out_gaa(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), X3) -> U3_GGG(X1, X2, X3, subD_in_gga(X1, X2, X4)) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X4) 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, subD_in_gga(X1, X2, X3)) 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X3) 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2, X4)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> U5_GGG(X1, X2, X3, remA_in_ggg(X4, s(X2), X3)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), s(X1)) -> U6_GGG(X1, X2, geqC_in_gg(X1, X2)) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), s(X1)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, geqC_in_gg(X1, X2)) 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), s(X1)) -> U6_GAG(X1, X2, geqC_in_ga(X1, X2)) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), s(X1)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> U2_GA(X1, X2, geqC_in_ga(X1, X2)) 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subD_in_gaa(x1, x2, x3) = subD_in_gaa(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 remA_in_ggg(x1, x2, x3) = remA_in_ggg(x1, x2, x3) 8.27/2.98 8.27/2.98 subD_in_gga(x1, x2, x3) = subD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 geqC_in_gg(x1, x2) = geqC_in_gg(x1, x2) 8.27/2.98 8.27/2.98 geqC_in_ga(x1, x2) = geqC_in_ga(x1) 8.27/2.98 8.27/2.98 REMA_IN_GAG(x1, x2, x3) = REMA_IN_GAG(x1, x3) 8.27/2.98 8.27/2.98 U3_GAG(x1, x2, x3, x4) = U3_GAG(x1, x3, x4) 8.27/2.98 8.27/2.98 SUBD_IN_GAA(x1, x2, x3) = SUBD_IN_GAA(x1) 8.27/2.98 8.27/2.98 U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) 8.27/2.98 8.27/2.98 U4_GAG(x1, x2, x3, x4) = U4_GAG(x1, x3, x4) 8.27/2.98 8.27/2.98 U5_GAG(x1, x2, x3, x4) = U5_GAG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 REMA_IN_GGG(x1, x2, x3) = REMA_IN_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 U3_GGG(x1, x2, x3, x4) = U3_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 SUBD_IN_GGA(x1, x2, x3) = SUBD_IN_GGA(x1, x2) 8.27/2.98 8.27/2.98 U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) 8.27/2.98 8.27/2.98 U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 U5_GGG(x1, x2, x3, x4) = U5_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 U6_GGG(x1, x2, x3) = U6_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GG(x1, x2) = GEQC_IN_GG(x1, x2) 8.27/2.98 8.27/2.98 U2_GG(x1, x2, x3) = U2_GG(x1, x2, x3) 8.27/2.98 8.27/2.98 U6_GAG(x1, x2, x3) = U6_GAG(x1, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GA(x1, x2) = GEQC_IN_GA(x1) 8.27/2.98 8.27/2.98 U2_GA(x1, x2, x3) = U2_GA(x1, x3) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 8.27/2.98 8.27/2.98 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 8.27/2.98 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (4) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), X3) -> U3_GAG(X1, X2, X3, subD_in_gaa(X1, X2, X4)) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X4) 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> U1_GAA(X1, X2, X3, subD_in_gaa(X1, X2, X3)) 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X3) 8.27/2.98 REMA_IN_GAG(X1, s(X2), X3) -> U4_GAG(X1, X2, X3, subcB_in_gaa(X1, X2, X4)) 8.27/2.98 U4_GAG(X1, X2, X3, subcB_out_gaa(X1, X2, X4)) -> U5_GAG(X1, X2, X3, remA_in_ggg(X4, s(X2), X3)) 8.27/2.98 U4_GAG(X1, X2, X3, subcB_out_gaa(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), X3) -> U3_GGG(X1, X2, X3, subD_in_gga(X1, X2, X4)) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X4) 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, subD_in_gga(X1, X2, X3)) 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X3) 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2, X4)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> U5_GGG(X1, X2, X3, remA_in_ggg(X4, s(X2), X3)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), s(X1)) -> U6_GGG(X1, X2, geqC_in_gg(X1, X2)) 8.27/2.98 REMA_IN_GGG(s(X1), s(X2), s(X1)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, geqC_in_gg(X1, X2)) 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), s(X1)) -> U6_GAG(X1, X2, geqC_in_ga(X1, X2)) 8.27/2.98 REMA_IN_GAG(s(X1), s(X2), s(X1)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> U2_GA(X1, X2, geqC_in_ga(X1, X2)) 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subD_in_gaa(x1, x2, x3) = subD_in_gaa(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 remA_in_ggg(x1, x2, x3) = remA_in_ggg(x1, x2, x3) 8.27/2.98 8.27/2.98 subD_in_gga(x1, x2, x3) = subD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 geqC_in_gg(x1, x2) = geqC_in_gg(x1, x2) 8.27/2.98 8.27/2.98 geqC_in_ga(x1, x2) = geqC_in_ga(x1) 8.27/2.98 8.27/2.98 REMA_IN_GAG(x1, x2, x3) = REMA_IN_GAG(x1, x3) 8.27/2.98 8.27/2.98 U3_GAG(x1, x2, x3, x4) = U3_GAG(x1, x3, x4) 8.27/2.98 8.27/2.98 SUBD_IN_GAA(x1, x2, x3) = SUBD_IN_GAA(x1) 8.27/2.98 8.27/2.98 U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) 8.27/2.98 8.27/2.98 U4_GAG(x1, x2, x3, x4) = U4_GAG(x1, x3, x4) 8.27/2.98 8.27/2.98 U5_GAG(x1, x2, x3, x4) = U5_GAG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 REMA_IN_GGG(x1, x2, x3) = REMA_IN_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 U3_GGG(x1, x2, x3, x4) = U3_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 SUBD_IN_GGA(x1, x2, x3) = SUBD_IN_GGA(x1, x2) 8.27/2.98 8.27/2.98 U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) 8.27/2.98 8.27/2.98 U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 U5_GGG(x1, x2, x3, x4) = U5_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 U6_GGG(x1, x2, x3) = U6_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GG(x1, x2) = GEQC_IN_GG(x1, x2) 8.27/2.98 8.27/2.98 U2_GG(x1, x2, x3) = U2_GG(x1, x2, x3) 8.27/2.98 8.27/2.98 U6_GAG(x1, x2, x3) = U6_GAG(x1, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GA(x1, x2) = GEQC_IN_GA(x1) 8.27/2.98 8.27/2.98 U2_GA(x1, x2, x3) = U2_GA(x1, x3) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (5) DependencyGraphProof (EQUIVALENT) 8.27/2.98 The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 16 less nodes. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (6) 8.27/2.98 Complex Obligation (AND) 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (7) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GA(x1, x2) = GEQC_IN_GA(x1) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (8) UsableRulesProof (EQUIVALENT) 8.27/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (9) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GA(s(X1), s(X2)) -> GEQC_IN_GA(X1, X2) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 GEQC_IN_GA(x1, x2) = GEQC_IN_GA(x1) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (10) PiDPToQDPProof (SOUND) 8.27/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (11) 8.27/2.98 Obligation: 8.27/2.98 Q DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GA(s(X1)) -> GEQC_IN_GA(X1) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 Q is empty. 8.27/2.98 We have to consider all (P,Q,R)-chains. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (12) QDPSizeChangeProof (EQUIVALENT) 8.27/2.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 8.27/2.98 8.27/2.98 From the DPs we obtained the following set of size-change graphs: 8.27/2.98 *GEQC_IN_GA(s(X1)) -> GEQC_IN_GA(X1) 8.27/2.98 The graph contains the following edges 1 > 1 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (13) 8.27/2.98 YES 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (14) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 GEQC_IN_GG(x1, x2) = GEQC_IN_GG(x1, x2) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (15) UsableRulesProof (EQUIVALENT) 8.27/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (16) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 Pi is empty. 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (17) PiDPToQDPProof (EQUIVALENT) 8.27/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (18) 8.27/2.98 Obligation: 8.27/2.98 Q DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 Q is empty. 8.27/2.98 We have to consider all (P,Q,R)-chains. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (19) QDPSizeChangeProof (EQUIVALENT) 8.27/2.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 8.27/2.98 8.27/2.98 From the DPs we obtained the following set of size-change graphs: 8.27/2.98 *GEQC_IN_GG(s(X1), s(X2)) -> GEQC_IN_GG(X1, X2) 8.27/2.98 The graph contains the following edges 1 > 1, 2 > 2 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (20) 8.27/2.98 YES 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (21) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X3) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 SUBD_IN_GGA(x1, x2, x3) = SUBD_IN_GGA(x1, x2) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (22) UsableRulesProof (EQUIVALENT) 8.27/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (23) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2), X3) -> SUBD_IN_GGA(X1, X2, X3) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 SUBD_IN_GGA(x1, x2, x3) = SUBD_IN_GGA(x1, x2) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (24) PiDPToQDPProof (SOUND) 8.27/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (25) 8.27/2.98 Obligation: 8.27/2.98 Q DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 SUBD_IN_GGA(s(X1), s(X2)) -> SUBD_IN_GGA(X1, X2) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 Q is empty. 8.27/2.98 We have to consider all (P,Q,R)-chains. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (26) QDPSizeChangeProof (EQUIVALENT) 8.27/2.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 8.27/2.98 8.27/2.98 From the DPs we obtained the following set of size-change graphs: 8.27/2.98 *SUBD_IN_GGA(s(X1), s(X2)) -> SUBD_IN_GGA(X1, X2) 8.27/2.98 The graph contains the following edges 1 > 1, 2 > 2 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (27) 8.27/2.98 YES 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (28) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2, X4)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 REMA_IN_GGG(x1, x2, x3) = REMA_IN_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (29) UsableRulesProof (EQUIVALENT) 8.27/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (30) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2, X4)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 REMA_IN_GGG(x1, x2, x3) = REMA_IN_GGG(x1, x2, x3) 8.27/2.98 8.27/2.98 U4_GGG(x1, x2, x3, x4) = U4_GGG(x1, x2, x3, x4) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (31) PiDPToQDPProof (SOUND) 8.27/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (32) 8.27/2.98 Obligation: 8.27/2.98 Q DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gga(s(X1), X2) -> U13_gga(X1, X2, subcD_in_gga(X1, X2)) 8.27/2.98 U13_gga(X1, X2, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 subcD_in_gga(s(X1), s(X2)) -> U11_gga(X1, X2, subcD_in_gga(X1, X2)) 8.27/2.98 subcD_in_gga(X1, 0) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 8.27/2.98 The set Q consists of the following terms: 8.27/2.98 8.27/2.98 subcB_in_gga(x0, x1) 8.27/2.98 U13_gga(x0, x1, x2) 8.27/2.98 subcD_in_gga(x0, x1) 8.27/2.98 U11_gga(x0, x1, x2) 8.27/2.98 8.27/2.98 We have to consider all (P,Q,R)-chains. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (33) QDPQMonotonicMRRProof (EQUIVALENT) 8.27/2.98 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 8.27/2.98 8.27/2.98 Strictly oriented dependency pairs: 8.27/2.98 8.27/2.98 REMA_IN_GGG(X1, s(X2), X3) -> U4_GGG(X1, X2, X3, subcB_in_gga(X1, X2)) 8.27/2.98 U4_GGG(X1, X2, X3, subcB_out_gga(X1, X2, X4)) -> REMA_IN_GGG(X4, s(X2), X3) 8.27/2.98 8.27/2.98 Strictly oriented rules of the TRS R: 8.27/2.98 8.27/2.98 subcD_in_gga(s(X1), s(X2)) -> U11_gga(X1, X2, subcD_in_gga(X1, X2)) 8.27/2.98 8.27/2.98 Used ordering: Polynomial interpretation [POLO]: 8.27/2.98 8.27/2.98 POL(0) = 0 8.27/2.98 POL(REMA_IN_GGG(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_3 8.27/2.98 POL(U11_gga(x_1, x_2, x_3)) = 2*x_1 + x_3 8.27/2.98 POL(U13_gga(x_1, x_2, x_3)) = 2 + x_3 8.27/2.98 POL(U4_GGG(x_1, x_2, x_3, x_4)) = 2*x_3 + 2*x_4 8.27/2.98 POL(s(x_1)) = 2 + 2*x_1 8.27/2.98 POL(subcB_in_gga(x_1, x_2)) = x_1 8.27/2.98 POL(subcB_out_gga(x_1, x_2, x_3)) = 2 + 2*x_3 8.27/2.98 POL(subcD_in_gga(x_1, x_2)) = 2*x_1 8.27/2.98 POL(subcD_out_gga(x_1, x_2, x_3)) = 2*x_3 8.27/2.98 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (34) 8.27/2.98 Obligation: 8.27/2.98 Q DP problem: 8.27/2.98 P is empty. 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gga(s(X1), X2) -> U13_gga(X1, X2, subcD_in_gga(X1, X2)) 8.27/2.98 U13_gga(X1, X2, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 subcD_in_gga(X1, 0) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 8.27/2.98 The set Q consists of the following terms: 8.27/2.98 8.27/2.98 subcB_in_gga(x0, x1) 8.27/2.98 U13_gga(x0, x1, x2) 8.27/2.98 subcD_in_gga(x0, x1) 8.27/2.98 U11_gga(x0, x1, x2) 8.27/2.98 8.27/2.98 We have to consider all (P,Q,R)-chains. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (35) PisEmptyProof (EQUIVALENT) 8.27/2.98 The TRS P is empty. Hence, there is no (P,Q,R) chain. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (36) 8.27/2.98 YES 8.27/2.98 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (37) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X3) 8.27/2.98 8.27/2.98 The TRS R consists of the following rules: 8.27/2.98 8.27/2.98 subcB_in_gaa(s(X1), X2, X3) -> U13_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(s(X1), s(X2), X3) -> U11_gaa(X1, X2, X3, subcD_in_gaa(X1, X2, X3)) 8.27/2.98 subcD_in_gaa(X1, 0, X1) -> subcD_out_gaa(X1, 0, X1) 8.27/2.98 U11_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcD_out_gaa(s(X1), s(X2), X3) 8.27/2.98 U13_gaa(X1, X2, X3, subcD_out_gaa(X1, X2, X3)) -> subcB_out_gaa(s(X1), X2, X3) 8.27/2.98 subcB_in_gga(s(X1), X2, X3) -> U13_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(s(X1), s(X2), X3) -> U11_gga(X1, X2, X3, subcD_in_gga(X1, X2, X3)) 8.27/2.98 subcD_in_gga(X1, 0, X1) -> subcD_out_gga(X1, 0, X1) 8.27/2.98 U11_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcD_out_gga(s(X1), s(X2), X3) 8.27/2.98 U13_gga(X1, X2, X3, subcD_out_gga(X1, X2, X3)) -> subcB_out_gga(s(X1), X2, X3) 8.27/2.98 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 subcB_in_gaa(x1, x2, x3) = subcB_in_gaa(x1) 8.27/2.98 8.27/2.98 U13_gaa(x1, x2, x3, x4) = U13_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_in_gaa(x1, x2, x3) = subcD_in_gaa(x1) 8.27/2.98 8.27/2.98 U11_gaa(x1, x2, x3, x4) = U11_gaa(x1, x4) 8.27/2.98 8.27/2.98 subcD_out_gaa(x1, x2, x3) = subcD_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gaa(x1, x2, x3) = subcB_out_gaa(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_in_gga(x1, x2, x3) = subcB_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U13_gga(x1, x2, x3, x4) = U13_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 subcD_in_gga(x1, x2, x3) = subcD_in_gga(x1, x2) 8.27/2.98 8.27/2.98 U11_gga(x1, x2, x3, x4) = U11_gga(x1, x2, x4) 8.27/2.98 8.27/2.98 0 = 0 8.27/2.98 8.27/2.98 subcD_out_gga(x1, x2, x3) = subcD_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 subcB_out_gga(x1, x2, x3) = subcB_out_gga(x1, x2, x3) 8.27/2.98 8.27/2.98 SUBD_IN_GAA(x1, x2, x3) = SUBD_IN_GAA(x1) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (38) UsableRulesProof (EQUIVALENT) 8.27/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (39) 8.27/2.98 Obligation: 8.27/2.98 Pi DP problem: 8.27/2.98 The TRS P consists of the following rules: 8.27/2.98 8.27/2.98 SUBD_IN_GAA(s(X1), s(X2), X3) -> SUBD_IN_GAA(X1, X2, X3) 8.27/2.98 8.27/2.98 R is empty. 8.27/2.98 The argument filtering Pi contains the following mapping: 8.27/2.98 s(x1) = s(x1) 8.27/2.98 8.27/2.98 SUBD_IN_GAA(x1, x2, x3) = SUBD_IN_GAA(x1) 8.27/2.98 8.27/2.98 8.27/2.98 We have to consider all (P,R,Pi)-chains 8.27/2.98 ---------------------------------------- 8.27/2.98 8.27/2.98 (40) PiDPToQDPProof (SOUND) 8.27/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.27/2.99 ---------------------------------------- 8.27/2.99 8.27/2.99 (41) 8.27/2.99 Obligation: 8.27/2.99 Q DP problem: 8.27/2.99 The TRS P consists of the following rules: 8.27/2.99 8.27/2.99 SUBD_IN_GAA(s(X1)) -> SUBD_IN_GAA(X1) 8.27/2.99 8.27/2.99 R is empty. 8.27/2.99 Q is empty. 8.27/2.99 We have to consider all (P,Q,R)-chains. 8.27/2.99 ---------------------------------------- 8.27/2.99 8.27/2.99 (42) QDPSizeChangeProof (EQUIVALENT) 8.27/2.99 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 8.27/2.99 8.27/2.99 From the DPs we obtained the following set of size-change graphs: 8.27/2.99 *SUBD_IN_GAA(s(X1)) -> SUBD_IN_GAA(X1) 8.27/2.99 The graph contains the following edges 1 > 1 8.27/2.99 8.27/2.99 8.27/2.99 ---------------------------------------- 8.27/2.99 8.27/2.99 (43) 8.27/2.99 YES 8.39/3.02 EOF