14.26/4.55 YES 14.43/4.60 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 14.43/4.60 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.43/4.60 14.43/4.60 14.43/4.60 Left Termination of the query pattern 14.43/4.60 14.43/4.60 mergesort(g,a) 14.43/4.60 14.43/4.60 w.r.t. the given Prolog program could successfully be proven: 14.43/4.60 14.43/4.60 (0) Prolog 14.43/4.60 (1) PrologToDTProblemTransformerProof [SOUND, 28 ms] 14.43/4.60 (2) TRIPLES 14.43/4.60 (3) TriplesToPiDPProof [SOUND, 0 ms] 14.43/4.60 (4) PiDP 14.43/4.60 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 14.43/4.60 (6) AND 14.43/4.60 (7) PiDP 14.43/4.60 (8) UsableRulesProof [EQUIVALENT, 0 ms] 14.43/4.60 (9) PiDP 14.43/4.60 (10) PiDPToQDPProof [EQUIVALENT, 0 ms] 14.43/4.60 (11) QDP 14.43/4.60 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 14.43/4.60 (13) YES 14.43/4.60 (14) PiDP 14.43/4.60 (15) UsableRulesProof [EQUIVALENT, 0 ms] 14.43/4.60 (16) PiDP 14.43/4.60 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 14.43/4.60 (18) QDP 14.43/4.60 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 14.43/4.60 (20) YES 14.43/4.60 (21) PiDP 14.43/4.60 (22) UsableRulesProof [EQUIVALENT, 0 ms] 14.43/4.60 (23) PiDP 14.43/4.60 (24) PiDPToQDPProof [SOUND, 0 ms] 14.43/4.60 (25) QDP 14.43/4.60 (26) MRRProof [EQUIVALENT, 29 ms] 14.43/4.60 (27) QDP 14.43/4.60 (28) MRRProof [EQUIVALENT, 22 ms] 14.43/4.60 (29) QDP 14.43/4.60 (30) DependencyGraphProof [EQUIVALENT, 0 ms] 14.43/4.60 (31) QDP 14.43/4.60 (32) UsableRulesProof [EQUIVALENT, 0 ms] 14.43/4.60 (33) QDP 14.43/4.60 (34) QReductionProof [EQUIVALENT, 0 ms] 14.43/4.60 (35) QDP 14.43/4.60 (36) QDPSizeChangeProof [EQUIVALENT, 0 ms] 14.43/4.60 (37) YES 14.43/4.60 (38) PiDP 14.43/4.60 (39) UsableRulesProof [EQUIVALENT, 0 ms] 14.43/4.60 (40) PiDP 14.43/4.60 (41) PiDPToQDPProof [SOUND, 0 ms] 14.43/4.60 (42) QDP 14.43/4.60 (43) QDPSizeChangeProof [EQUIVALENT, 0 ms] 14.43/4.60 (44) YES 14.43/4.60 (45) PiDP 14.43/4.60 (46) PiDPToQDPProof [SOUND, 0 ms] 14.43/4.60 (47) QDP 14.43/4.60 (48) TransformationProof [EQUIVALENT, 0 ms] 14.43/4.60 (49) QDP 14.43/4.60 (50) QDPOrderProof [EQUIVALENT, 57 ms] 14.43/4.60 (51) QDP 14.43/4.60 (52) DependencyGraphProof [EQUIVALENT, 0 ms] 14.43/4.60 (53) TRUE 14.43/4.60 14.43/4.60 14.43/4.60 ---------------------------------------- 14.43/4.60 14.43/4.60 (0) 14.43/4.60 Obligation: 14.43/4.60 Clauses: 14.43/4.60 14.43/4.60 mergesort([], []). 14.43/4.60 mergesort(.(E, []), .(E, [])). 14.43/4.60 mergesort(.(E, .(F, U)), V) :- ','(split(.(E, .(F, U)), W, Y), ','(mergesort(W, X), ','(mergesort(Y, Z), merge(X, Z, V)))). 14.43/4.60 merge(X, [], X). 14.43/4.60 merge([], X, X). 14.43/4.60 merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z)). 14.43/4.60 merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z)). 14.43/4.60 split([], [], []). 14.43/4.60 split(.(E, U), .(E, V), W) :- split(U, W, V). 14.43/4.60 gt(s(X), s(Y)) :- gt(X, Y). 14.43/4.60 gt(s(X), 0). 14.43/4.60 le(s(X), s(Y)) :- le(X, Y). 14.43/4.60 le(0, s(Y)). 14.43/4.60 le(0, 0). 14.43/4.60 14.43/4.60 14.43/4.60 Query: mergesort(g,a) 14.43/4.60 ---------------------------------------- 14.43/4.60 14.43/4.60 (1) PrologToDTProblemTransformerProof (SOUND) 14.43/4.60 Built DT problem from termination graph DT10. 14.43/4.60 14.43/4.60 { 14.43/4.60 "root": 12, 14.43/4.60 "program": { 14.43/4.60 "directives": [], 14.43/4.60 "clauses": [ 14.43/4.60 [ 14.43/4.60 "(mergesort ([]) ([]))", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(mergesort (. E ([])) (. E ([])))", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(mergesort (. E (. F U)) V)", 14.43/4.60 "(',' (split (. E (. F U)) W Y) (',' (mergesort W X) (',' (mergesort Y Z) (merge X Z V))))" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(merge X ([]) X)", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(merge ([]) X X)", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(merge (. A X) (. B Y) (. A Z))", 14.43/4.60 "(',' (le A B) (merge X (. B Y) Z))" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(merge (. A X) (. B Y) (. B Z))", 14.43/4.60 "(',' (gt A B) (merge (. A X) Y Z))" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(split ([]) ([]) ([]))", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(split (. E U) (. E V) W)", 14.43/4.60 "(split U W V)" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(gt (s X) (s Y))", 14.43/4.60 "(gt X Y)" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(gt (s X) (0))", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(le (s X) (s Y))", 14.43/4.60 "(le X Y)" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(le (0) (s Y))", 14.43/4.60 null 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(le (0) (0))", 14.43/4.60 null 14.43/4.60 ] 14.43/4.60 ] 14.43/4.60 }, 14.43/4.60 "graph": { 14.43/4.60 "nodes": { 14.43/4.60 "type": "Nodes", 14.43/4.60 "590": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(mergesort T24 X23)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T24"], 14.43/4.60 "free": ["X23"], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "591": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T38", 14.43/4.60 "T39" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "673": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "630": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "674": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "675": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "676": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "753": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(',' (gt T111 T113) (merge (. T111 T112) T114 T116))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T112", 14.43/4.60 "T113", 14.43/4.60 "T114" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "358": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "633": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 4, 14.43/4.60 "scope": 5, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T38", 14.43/4.60 "T39" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "677": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "754": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "513": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "634": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 5, 14.43/4.60 "scope": 5, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 6, 14.43/4.60 "scope": 5, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T38", 14.43/4.60 "T39" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "678": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "755": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(gt T111 T113)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T113" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "239": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort (. T4 ([])) T2)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T4"], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "514": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "756": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(merge (. T111 T112) T114 T116)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T112", 14.43/4.60 "T114" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "757": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 9, 14.43/4.60 "scope": 7, 14.43/4.60 "term": "(gt T111 T113)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 10, 14.43/4.60 "scope": 7, 14.43/4.60 "term": "(gt T111 T113)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T113" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "439": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(',' (split (. T22 T23) X41 X40) (',' (mergesort (. T21 X40) X22) (',' (mergesort X41 X23) (merge X22 X23 T14))))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T21", 14.43/4.60 "T22", 14.43/4.60 "T23" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X22", 14.43/4.60 "X23", 14.43/4.60 "X40", 14.43/4.60 "X41" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "758": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 9, 14.43/4.60 "scope": 7, 14.43/4.60 "term": "(gt T111 T113)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T113" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "638": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "759": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 10, 14.43/4.60 "scope": 7, 14.43/4.60 "term": "(gt T111 T113)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T111", 14.43/4.60 "T113" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "639": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "12": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T1"], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "13": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 0, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 1, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T1"], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "16": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 1, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort ([]) T2)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort ([]) T2)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "17": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 1, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [[ 14.43/4.60 "(mergesort T1 T2)", 14.43/4.60 "(mergesort ([]) ([]))" 14.43/4.60 ]], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T1"], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "760": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(gt T129 T130)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T129", 14.43/4.60 "T130" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "442": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(split (. T22 T23) X41 X40)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T22", 14.43/4.60 "T23" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X40", 14.43/4.60 "X41" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "640": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "761": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "443": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(',' (mergesort (. T21 T25) X22) (',' (mergesort T24 X23) (merge X22 X23 T14)))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T21", 14.43/4.60 "T24", 14.43/4.60 "T25" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X22", 14.43/4.60 "X23" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "762": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(true)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "763": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "643": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 5, 14.43/4.60 "scope": 5, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T38", 14.43/4.60 "T39" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "764": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "369": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 7, 14.43/4.60 "scope": 2, 14.43/4.60 "term": "(',' (split (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 8, 14.43/4.60 "scope": 2, 14.43/4.60 "term": "(',' (split (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T10", 14.43/4.60 "T11", 14.43/4.60 "T12" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X20", 14.43/4.60 "X21", 14.43/4.60 "X22", 14.43/4.60 "X23" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "644": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 6, 14.43/4.60 "scope": 5, 14.43/4.60 "term": "(merge T38 T39 T14)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T38", 14.43/4.60 "T39" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "647": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(',' (le T72 T74) (merge T73 (. T74 T75) T77))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T72", 14.43/4.60 "T73", 14.43/4.60 "T74", 14.43/4.60 "T75" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "648": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "26": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 1, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort ([]) T2)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort ([]) T2)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "27": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort ([]) T2)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "28": { 14.43/4.60 "goal": [], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "250": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort T1 T2)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [ 14.43/4.60 [ 14.43/4.60 "(mergesort T1 T2)", 14.43/4.60 "(mergesort ([]) ([]))" 14.43/4.60 ], 14.43/4.60 [ 14.43/4.60 "(mergesort T1 T2)", 14.43/4.60 "(mergesort (. X7 ([])) (. X7 ([])))" 14.43/4.60 ] 14.43/4.60 ], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T1"], 14.43/4.60 "free": ["X7"], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "330": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(',' (split (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T10", 14.43/4.60 "T11", 14.43/4.60 "T12" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X20", 14.43/4.60 "X21", 14.43/4.60 "X22", 14.43/4.60 "X23" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "495": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(split T31 X59 X58)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T31"], 14.43/4.60 "free": [ 14.43/4.60 "X58", 14.43/4.60 "X59" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "375": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 8, 14.43/4.60 "scope": 2, 14.43/4.60 "term": "(',' (split (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T10", 14.43/4.60 "T11", 14.43/4.60 "T12" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X20", 14.43/4.60 "X21", 14.43/4.60 "X22", 14.43/4.60 "X23" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "651": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T72", 14.43/4.60 "T74" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "652": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(merge T73 (. T74 T75) T77)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T73", 14.43/4.60 "T74", 14.43/4.60 "T75" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "257": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 2, 14.43/4.60 "scope": 1, 14.43/4.60 "term": "(mergesort (. T4 ([])) T2)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": ["T4"], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "656": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 11, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 12, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 13, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T72", 14.43/4.60 "T74" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "657": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": 11, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T72", 14.43/4.60 "T74" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "658": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 12, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 13, 14.43/4.60 "scope": 6, 14.43/4.60 "term": "(le T72 T74)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T72", 14.43/4.60 "T74" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "659": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(le T90 T91)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T90", 14.43/4.60 "T91" 14.43/4.60 ], 14.43/4.60 "free": [], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "460": { 14.43/4.60 "goal": [ 14.43/4.60 { 14.43/4.60 "clause": 7, 14.43/4.60 "scope": 3, 14.43/4.60 "term": "(split (. T22 T23) X41 X40)" 14.43/4.60 }, 14.43/4.60 { 14.43/4.60 "clause": 8, 14.43/4.60 "scope": 3, 14.43/4.60 "term": "(split (. T22 T23) X41 X40)" 14.43/4.60 } 14.43/4.60 ], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T22", 14.43/4.60 "T23" 14.43/4.60 ], 14.43/4.60 "free": [ 14.43/4.60 "X40", 14.43/4.60 "X41" 14.43/4.60 ], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "581": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.60 "scope": -1, 14.43/4.60 "term": "(mergesort (. T21 T25) X22)" 14.43/4.60 }], 14.43/4.60 "kb": { 14.43/4.60 "nonunifying": [], 14.43/4.60 "intvars": {}, 14.43/4.60 "arithmetic": { 14.43/4.60 "type": "PlainIntegerRelationState", 14.43/4.60 "relations": [] 14.43/4.60 }, 14.43/4.60 "ground": [ 14.43/4.60 "T21", 14.43/4.60 "T25" 14.43/4.60 ], 14.43/4.60 "free": ["X22"], 14.43/4.60 "exprvars": [] 14.43/4.60 } 14.43/4.60 }, 14.43/4.60 "582": { 14.43/4.60 "goal": [{ 14.43/4.60 "clause": -1, 14.43/4.61 "scope": -1, 14.43/4.61 "term": "(',' (mergesort T24 X23) (merge T38 X23 T14))" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T24", 14.43/4.61 "T38" 14.43/4.61 ], 14.43/4.61 "free": ["X23"], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "661": { 14.43/4.61 "goal": [], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "267": { 14.43/4.61 "goal": [], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "465": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 8, 14.43/4.61 "scope": 3, 14.43/4.61 "term": "(split (. T22 T23) X41 X40)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T22", 14.43/4.61 "T23" 14.43/4.61 ], 14.43/4.61 "free": [ 14.43/4.61 "X40", 14.43/4.61 "X41" 14.43/4.61 ], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "542": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": -1, 14.43/4.61 "scope": -1, 14.43/4.61 "term": "(split T37 X77 X76)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": ["T37"], 14.43/4.61 "free": [ 14.43/4.61 "X76", 14.43/4.61 "X77" 14.43/4.61 ], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "663": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 12, 14.43/4.61 "scope": 6, 14.43/4.61 "term": "(le T72 T74)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T72", 14.43/4.61 "T74" 14.43/4.61 ], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "620": { 14.43/4.61 "goal": [ 14.43/4.61 { 14.43/4.61 "clause": 3, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 4, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 5, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 6, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 } 14.43/4.61 ], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T38", 14.43/4.61 "T39" 14.43/4.61 ], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "665": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 13, 14.43/4.61 "scope": 6, 14.43/4.61 "term": "(le T72 T74)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T72", 14.43/4.61 "T74" 14.43/4.61 ], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "501": { 14.43/4.61 "goal": [ 14.43/4.61 { 14.43/4.61 "clause": 7, 14.43/4.61 "scope": 4, 14.43/4.61 "term": "(split T31 X59 X58)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 8, 14.43/4.61 "scope": 4, 14.43/4.61 "term": "(split T31 X59 X58)" 14.43/4.61 } 14.43/4.61 ], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": ["T31"], 14.43/4.61 "free": [ 14.43/4.61 "X58", 14.43/4.61 "X59" 14.43/4.61 ], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "546": { 14.43/4.61 "goal": [], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "623": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 3, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T38", 14.43/4.61 "T39" 14.43/4.61 ], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "624": { 14.43/4.61 "goal": [ 14.43/4.61 { 14.43/4.61 "clause": 4, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 5, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "clause": 6, 14.43/4.61 "scope": 5, 14.43/4.61 "term": "(merge T38 T39 T14)" 14.43/4.61 } 14.43/4.61 ], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [ 14.43/4.61 "T38", 14.43/4.61 "T39" 14.43/4.61 ], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "504": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 7, 14.43/4.61 "scope": 4, 14.43/4.61 "term": "(split T31 X59 X58)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": ["T31"], 14.43/4.61 "free": [ 14.43/4.61 "X58", 14.43/4.61 "X59" 14.43/4.61 ], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "506": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": 8, 14.43/4.61 "scope": 4, 14.43/4.61 "term": "(split T31 X59 X58)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": ["T31"], 14.43/4.61 "free": [ 14.43/4.61 "X58", 14.43/4.61 "X59" 14.43/4.61 ], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "628": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": -1, 14.43/4.61 "scope": -1, 14.43/4.61 "term": "(true)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "629": { 14.43/4.61 "goal": [], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "509": { 14.43/4.61 "goal": [{ 14.43/4.61 "clause": -1, 14.43/4.61 "scope": -1, 14.43/4.61 "term": "(true)" 14.43/4.61 }], 14.43/4.61 "kb": { 14.43/4.61 "nonunifying": [], 14.43/4.61 "intvars": {}, 14.43/4.61 "arithmetic": { 14.43/4.61 "type": "PlainIntegerRelationState", 14.43/4.61 "relations": [] 14.43/4.61 }, 14.43/4.61 "ground": [], 14.43/4.61 "free": [], 14.43/4.61 "exprvars": [] 14.43/4.61 } 14.43/4.61 } 14.43/4.61 }, 14.43/4.61 "edges": [ 14.43/4.61 { 14.43/4.61 "from": 12, 14.43/4.61 "to": 13, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 13, 14.43/4.61 "to": 16, 14.43/4.61 "label": "EVAL with clause\nmergesort([], []).\nand substitutionT1 -> [],\nT2 -> []" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 13, 14.43/4.61 "to": 17, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 16, 14.43/4.61 "to": 26, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 17, 14.43/4.61 "to": 239, 14.43/4.61 "label": "EVAL with clause\nmergesort(.(X7, []), .(X7, [])).\nand substitutionX7 -> T4,\nT1 -> .(T4, []),\nT2 -> .(T4, [])" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 17, 14.43/4.61 "to": 250, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 26, 14.43/4.61 "to": 27, 14.43/4.61 "label": "BACKTRACK\nfor clause: mergesort(.(E, []), .(E, []))because of non-unification" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 27, 14.43/4.61 "to": 28, 14.43/4.61 "label": "BACKTRACK\nfor clause: mergesort(.(E, .(F, U)), V) :- ','(split(.(E, .(F, U)), W, Y), ','(mergesort(W, X), ','(mergesort(Y, Z), merge(X, Z, V))))because of non-unification" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 239, 14.43/4.61 "to": 257, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 250, 14.43/4.61 "to": 330, 14.43/4.61 "label": "EVAL with clause\nmergesort(.(X16, .(X17, X18)), X19) :- ','(split(.(X16, .(X17, X18)), X20, X21), ','(mergesort(X20, X22), ','(mergesort(X21, X23), merge(X22, X23, X19)))).\nand substitutionX16 -> T10,\nX17 -> T11,\nX18 -> T12,\nT1 -> .(T10, .(T11, T12)),\nT2 -> T14,\nX19 -> T14,\nT13 -> T14" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 250, 14.43/4.61 "to": 358, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 257, 14.43/4.61 "to": 267, 14.43/4.61 "label": "BACKTRACK\nfor clause: mergesort(.(E, .(F, U)), V) :- ','(split(.(E, .(F, U)), W, Y), ','(mergesort(W, X), ','(mergesort(Y, Z), merge(X, Z, V))))because of non-unification" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 330, 14.43/4.61 "to": 369, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 369, 14.43/4.61 "to": 375, 14.43/4.61 "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 375, 14.43/4.61 "to": 439, 14.43/4.61 "label": "ONLY EVAL with clause\nsplit(.(X36, X37), .(X36, X38), X39) :- split(X37, X39, X38).\nand substitutionT10 -> T21,\nX36 -> T21,\nT11 -> T22,\nT12 -> T23,\nX37 -> .(T22, T23),\nX38 -> X40,\nX20 -> .(T21, X40),\nX21 -> X41,\nX39 -> X41" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 439, 14.43/4.61 "to": 442, 14.43/4.61 "label": "SPLIT 1" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 439, 14.43/4.61 "to": 443, 14.43/4.61 "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT23 is ground\nT24 is ground\nT25 is ground\nreplacements:X41 -> T24,\nX40 -> T25" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 442, 14.43/4.61 "to": 460, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 443, 14.43/4.61 "to": 581, 14.43/4.61 "label": "SPLIT 1" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 443, 14.43/4.61 "to": 582, 14.43/4.61 "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT25 is ground\nT38 is ground\nreplacements:X22 -> T38" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 460, 14.43/4.61 "to": 465, 14.43/4.61 "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 465, 14.43/4.61 "to": 495, 14.43/4.61 "label": "ONLY EVAL with clause\nsplit(.(X54, X55), .(X54, X56), X57) :- split(X55, X57, X56).\nand substitutionT22 -> T30,\nX54 -> T30,\nT23 -> T31,\nX55 -> T31,\nX56 -> X58,\nX41 -> .(T30, X58),\nX40 -> X59,\nX57 -> X59" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 495, 14.43/4.61 "to": 501, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 501, 14.43/4.61 "to": 504, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 501, 14.43/4.61 "to": 506, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 504, 14.43/4.61 "to": 509, 14.43/4.61 "label": "EVAL with clause\nsplit([], [], []).\nand substitutionT31 -> [],\nX59 -> [],\nX58 -> []" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 504, 14.43/4.61 "to": 513, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 506, 14.43/4.61 "to": 542, 14.43/4.61 "label": "EVAL with clause\nsplit(.(X72, X73), .(X72, X74), X75) :- split(X73, X75, X74).\nand substitutionX72 -> T36,\nX73 -> T37,\nT31 -> .(T36, T37),\nX74 -> X76,\nX59 -> .(T36, X76),\nX58 -> X77,\nX75 -> X77" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 506, 14.43/4.61 "to": 546, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 509, 14.43/4.61 "to": 514, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 542, 14.43/4.61 "to": 495, 14.43/4.61 "label": "INSTANCE with matching:\nT31 -> T37\nX59 -> X77\nX58 -> X76" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 581, 14.43/4.61 "to": 12, 14.43/4.61 "label": "INSTANCE with matching:\nT1 -> .(T21, T25)\nT2 -> X22" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 582, 14.43/4.61 "to": 590, 14.43/4.61 "label": "SPLIT 1" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 582, 14.43/4.61 "to": 591, 14.43/4.61 "label": "SPLIT 2\nnew knowledge:\nT24 is ground\nT39 is ground\nreplacements:X23 -> T39" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 590, 14.43/4.61 "to": 12, 14.43/4.61 "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> X23" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 591, 14.43/4.61 "to": 620, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 620, 14.43/4.61 "to": 623, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 620, 14.43/4.61 "to": 624, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 623, 14.43/4.61 "to": 628, 14.43/4.61 "label": "EVAL with clause\nmerge(X84, [], X84).\nand substitutionT38 -> T46,\nX84 -> T46,\nT39 -> [],\nT14 -> T46" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 623, 14.43/4.61 "to": 629, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 624, 14.43/4.61 "to": 633, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 624, 14.43/4.61 "to": 634, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 628, 14.43/4.61 "to": 630, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 633, 14.43/4.61 "to": 638, 14.43/4.61 "label": "EVAL with clause\nmerge([], X89, X89).\nand substitutionT38 -> [],\nT39 -> T51,\nX89 -> T51,\nT14 -> T51" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 633, 14.43/4.61 "to": 639, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 634, 14.43/4.61 "to": 643, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 634, 14.43/4.61 "to": 644, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 638, 14.43/4.61 "to": 640, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 643, 14.43/4.61 "to": 647, 14.43/4.61 "label": "EVAL with clause\nmerge(.(X110, X111), .(X112, X113), .(X110, X114)) :- ','(le(X110, X112), merge(X111, .(X112, X113), X114)).\nand substitutionX110 -> T72,\nX111 -> T73,\nT38 -> .(T72, T73),\nX112 -> T74,\nX113 -> T75,\nT39 -> .(T74, T75),\nX114 -> T77,\nT14 -> .(T72, T77),\nT76 -> T77" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 643, 14.43/4.61 "to": 648, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 644, 14.43/4.61 "to": 753, 14.43/4.61 "label": "EVAL with clause\nmerge(.(X148, X149), .(X150, X151), .(X150, X152)) :- ','(gt(X148, X150), merge(.(X148, X149), X151, X152)).\nand substitutionX148 -> T111,\nX149 -> T112,\nT38 -> .(T111, T112),\nX150 -> T113,\nX151 -> T114,\nT39 -> .(T113, T114),\nX152 -> T116,\nT14 -> .(T113, T116),\nT115 -> T116" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 644, 14.43/4.61 "to": 754, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 647, 14.43/4.61 "to": 651, 14.43/4.61 "label": "SPLIT 1" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 647, 14.43/4.61 "to": 652, 14.43/4.61 "label": "SPLIT 2\nnew knowledge:\nT72 is ground\nT74 is ground" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 651, 14.43/4.61 "to": 656, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 652, 14.43/4.61 "to": 591, 14.43/4.61 "label": "INSTANCE with matching:\nT38 -> T73\nT39 -> .(T74, T75)\nT14 -> T77" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 656, 14.43/4.61 "to": 657, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 656, 14.43/4.61 "to": 658, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 657, 14.43/4.61 "to": 659, 14.43/4.61 "label": "EVAL with clause\nle(s(X127), s(X128)) :- le(X127, X128).\nand substitutionX127 -> T90,\nT72 -> s(T90),\nX128 -> T91,\nT74 -> s(T91)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 657, 14.43/4.61 "to": 661, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 658, 14.43/4.61 "to": 663, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 658, 14.43/4.61 "to": 665, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 659, 14.43/4.61 "to": 651, 14.43/4.61 "label": "INSTANCE with matching:\nT72 -> T90\nT74 -> T91" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 663, 14.43/4.61 "to": 673, 14.43/4.61 "label": "EVAL with clause\nle(0, s(X135)).\nand substitutionT72 -> 0,\nX135 -> T98,\nT74 -> s(T98)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 663, 14.43/4.61 "to": 674, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 665, 14.43/4.61 "to": 676, 14.43/4.61 "label": "EVAL with clause\nle(0, 0).\nand substitutionT72 -> 0,\nT74 -> 0" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 665, 14.43/4.61 "to": 677, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 673, 14.43/4.61 "to": 675, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 676, 14.43/4.61 "to": 678, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 753, 14.43/4.61 "to": 755, 14.43/4.61 "label": "SPLIT 1" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 753, 14.43/4.61 "to": 756, 14.43/4.61 "label": "SPLIT 2\nnew knowledge:\nT111 is ground\nT113 is ground" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 755, 14.43/4.61 "to": 757, 14.43/4.61 "label": "CASE" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 756, 14.43/4.61 "to": 591, 14.43/4.61 "label": "INSTANCE with matching:\nT38 -> .(T111, T112)\nT39 -> T114\nT14 -> T116" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 757, 14.43/4.61 "to": 758, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 757, 14.43/4.61 "to": 759, 14.43/4.61 "label": "PARALLEL" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 758, 14.43/4.61 "to": 760, 14.43/4.61 "label": "EVAL with clause\ngt(s(X165), s(X166)) :- gt(X165, X166).\nand substitutionX165 -> T129,\nT111 -> s(T129),\nX166 -> T130,\nT113 -> s(T130)" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 758, 14.43/4.61 "to": 761, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 759, 14.43/4.61 "to": 762, 14.43/4.61 "label": "EVAL with clause\ngt(s(X171), 0).\nand substitutionX171 -> T135,\nT111 -> s(T135),\nT113 -> 0" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 759, 14.43/4.61 "to": 763, 14.43/4.61 "label": "EVAL-BACKTRACK" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 760, 14.43/4.61 "to": 755, 14.43/4.61 "label": "INSTANCE with matching:\nT111 -> T129\nT113 -> T130" 14.43/4.61 }, 14.43/4.61 { 14.43/4.61 "from": 762, 14.43/4.61 "to": 764, 14.43/4.61 "label": "SUCCESS" 14.43/4.61 } 14.43/4.61 ], 14.43/4.61 "type": "Graph" 14.43/4.61 } 14.43/4.61 } 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (2) 14.43/4.61 Obligation: 14.43/4.61 Triples: 14.43/4.61 14.43/4.61 splitA(.(X1, X2), .(X1, X3), X4) :- splitA(X2, X4, X3). 14.43/4.61 mergeC(.(X1, X2), .(X3, X4), .(X1, X5)) :- leE(X1, X3). 14.43/4.61 mergeC(.(X1, X2), .(X3, X4), .(X1, X5)) :- ','(lecE(X1, X3), mergeC(X2, .(X3, X4), X5)). 14.43/4.61 mergeC(.(X1, X2), .(X3, X4), .(X3, X5)) :- gtF(X1, X3). 14.43/4.61 mergeC(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcF(X1, X3), mergeC(.(X1, X2), X4, X5)). 14.43/4.61 leE(s(X1), s(X2)) :- leE(X1, X2). 14.43/4.61 gtF(s(X1), s(X2)) :- gtF(X1, X2). 14.43/4.61 mergesortB(.(X1, .(X2, X3)), X4) :- splitA(X3, X5, X6). 14.43/4.61 mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcD(X2, X3, X5, X6), mergesortB(.(X1, X6), X7)). 14.43/4.61 mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcD(X2, X3, X5, X6), ','(mergesortcB(.(X1, X6), X7), mergesortB(X5, X8))). 14.43/4.61 mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcD(X2, X3, X5, X6), ','(mergesortcB(.(X1, X6), X7), ','(mergesortcB(X5, X8), mergeC(X7, X8, X4)))). 14.43/4.61 14.43/4.61 Clauses: 14.43/4.61 14.43/4.61 splitcA([], [], []). 14.43/4.61 splitcA(.(X1, X2), .(X1, X3), X4) :- splitcA(X2, X4, X3). 14.43/4.61 mergesortcB([], []). 14.43/4.61 mergesortcB(.(X1, []), .(X1, [])). 14.43/4.61 mergesortcB(.(X1, .(X2, X3)), X4) :- ','(splitcD(X2, X3, X5, X6), ','(mergesortcB(.(X1, X6), X7), ','(mergesortcB(X5, X8), mergecC(X7, X8, X4)))). 14.43/4.61 mergecC(X1, [], X1). 14.43/4.61 mergecC([], X1, X1). 14.43/4.61 mergecC(.(X1, X2), .(X3, X4), .(X1, X5)) :- ','(lecE(X1, X3), mergecC(X2, .(X3, X4), X5)). 14.43/4.61 mergecC(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcF(X1, X3), mergecC(.(X1, X2), X4, X5)). 14.43/4.61 lecE(s(X1), s(X2)) :- lecE(X1, X2). 14.43/4.61 lecE(0, s(X1)). 14.43/4.61 lecE(0, 0). 14.43/4.61 gtcF(s(X1), s(X2)) :- gtcF(X1, X2). 14.43/4.61 gtcF(s(X1), 0). 14.43/4.61 splitcD(X1, X2, .(X1, X3), X4) :- splitcA(X2, X4, X3). 14.43/4.61 14.43/4.61 Afs: 14.43/4.61 14.43/4.61 mergesortB(x1, x2) = mergesortB(x1) 14.43/4.61 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (3) TriplesToPiDPProof (SOUND) 14.43/4.61 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 14.43/4.61 14.43/4.61 mergesortB_in_2: (b,f) 14.43/4.61 14.43/4.61 splitA_in_3: (b,f,f) 14.43/4.61 14.43/4.61 splitcD_in_4: (b,b,f,f) 14.43/4.61 14.43/4.61 splitcA_in_3: (b,f,f) 14.43/4.61 14.43/4.61 mergesortcB_in_2: (b,f) 14.43/4.61 14.43/4.61 mergecC_in_3: (b,b,f) 14.43/4.61 14.43/4.61 lecE_in_2: (b,b) 14.43/4.61 14.43/4.61 gtcF_in_2: (b,b) 14.43/4.61 14.43/4.61 mergeC_in_3: (b,b,f) 14.43/4.61 14.43/4.61 leE_in_2: (b,b) 14.43/4.61 14.43/4.61 gtF_in_2: (b,b) 14.43/4.61 14.43/4.61 Transforming TRIPLES into the following Term Rewriting System: 14.43/4.61 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U10_GA(X1, X2, X3, X4, splitA_in_gaa(X3, X5, X6)) 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> SPLITA_IN_GAA(X3, X5, X6) 14.43/4.61 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> U1_GAA(X1, X2, X3, X4, splitA_in_gaa(X2, X4, X3)) 14.43/4.61 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> SPLITA_IN_GAA(X2, X4, X3) 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U12_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X1, X6), X7)) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6), X7) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U14_GA(X1, X2, X3, X4, mergesortB_in_ga(X5, X8)) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5, X8) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U15_GA(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U16_GA(X1, X2, X3, X4, mergeC_in_gga(X7, X8, X4)) 14.43/4.61 U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> MERGEC_IN_GGA(X7, X8, X4) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U2_GGA(X1, X2, X3, X4, X5, leE_in_gg(X1, X3)) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> LEE_IN_GG(X1, X3) 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> U8_GG(X1, X2, leE_in_gg(X1, X2)) 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U4_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U5_GGA(X1, X2, X3, X4, X5, gtF_in_gg(X1, X3)) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTF_IN_GG(X1, X3) 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> U9_GG(X1, X2, gtF_in_gg(X1, X2)) 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) 14.43/4.61 14.43/4.61 The TRS R consists of the following rules: 14.43/4.61 14.43/4.61 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.61 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.61 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.61 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.61 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.61 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.61 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.61 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.61 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.61 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.61 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.61 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.61 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.61 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.61 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.61 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.61 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.61 14.43/4.61 The argument filtering Pi contains the following mapping: 14.43/4.61 mergesortB_in_ga(x1, x2) = mergesortB_in_ga(x1) 14.43/4.61 14.43/4.61 .(x1, x2) = .(x1, x2) 14.43/4.61 14.43/4.61 splitA_in_gaa(x1, x2, x3) = splitA_in_gaa(x1) 14.43/4.61 14.43/4.61 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.61 14.43/4.61 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.61 14.43/4.61 [] = [] 14.43/4.61 14.43/4.61 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.61 14.43/4.61 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.61 14.43/4.61 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.61 14.43/4.61 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.61 14.43/4.61 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.61 14.43/4.61 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 s(x1) = s(x1) 14.43/4.61 14.43/4.61 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 0 = 0 14.43/4.61 14.43/4.61 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 mergeC_in_gga(x1, x2, x3) = mergeC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 leE_in_gg(x1, x2) = leE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 gtF_in_gg(x1, x2) = gtF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) 14.43/4.61 14.43/4.61 U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) 14.43/4.61 14.43/4.61 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x2, x5) 14.43/4.61 14.43/4.61 U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U12_GA(x1, x2, x3, x4, x5) = U12_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U15_GA(x1, x2, x3, x4, x5, x6) = U15_GA(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U16_GA(x1, x2, x3, x4, x5) = U16_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) 14.43/4.61 14.43/4.61 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 LEE_IN_GG(x1, x2) = LEE_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) 14.43/4.61 14.43/4.61 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 GTF_IN_GG(x1, x2) = GTF_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) 14.43/4.61 14.43/4.61 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 14.43/4.61 14.43/4.61 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 14.43/4.61 14.43/4.61 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (4) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U10_GA(X1, X2, X3, X4, splitA_in_gaa(X3, X5, X6)) 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> SPLITA_IN_GAA(X3, X5, X6) 14.43/4.61 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> U1_GAA(X1, X2, X3, X4, splitA_in_gaa(X2, X4, X3)) 14.43/4.61 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> SPLITA_IN_GAA(X2, X4, X3) 14.43/4.61 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U12_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X1, X6), X7)) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6), X7) 14.43/4.61 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U14_GA(X1, X2, X3, X4, mergesortB_in_ga(X5, X8)) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5, X8) 14.43/4.61 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U15_GA(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U16_GA(X1, X2, X3, X4, mergeC_in_gga(X7, X8, X4)) 14.43/4.61 U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> MERGEC_IN_GGA(X7, X8, X4) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U2_GGA(X1, X2, X3, X4, X5, leE_in_gg(X1, X3)) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> LEE_IN_GG(X1, X3) 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> U8_GG(X1, X2, leE_in_gg(X1, X2)) 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U4_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U5_GGA(X1, X2, X3, X4, X5, gtF_in_gg(X1, X3)) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTF_IN_GG(X1, X3) 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> U9_GG(X1, X2, gtF_in_gg(X1, X2)) 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) 14.43/4.61 14.43/4.61 The TRS R consists of the following rules: 14.43/4.61 14.43/4.61 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.61 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.61 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.61 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.61 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.61 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.61 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.61 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.61 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.61 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.61 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.61 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.61 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.61 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.61 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.61 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.61 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.61 14.43/4.61 The argument filtering Pi contains the following mapping: 14.43/4.61 mergesortB_in_ga(x1, x2) = mergesortB_in_ga(x1) 14.43/4.61 14.43/4.61 .(x1, x2) = .(x1, x2) 14.43/4.61 14.43/4.61 splitA_in_gaa(x1, x2, x3) = splitA_in_gaa(x1) 14.43/4.61 14.43/4.61 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.61 14.43/4.61 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.61 14.43/4.61 [] = [] 14.43/4.61 14.43/4.61 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.61 14.43/4.61 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.61 14.43/4.61 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.61 14.43/4.61 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.61 14.43/4.61 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.61 14.43/4.61 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 s(x1) = s(x1) 14.43/4.61 14.43/4.61 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 0 = 0 14.43/4.61 14.43/4.61 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 mergeC_in_gga(x1, x2, x3) = mergeC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 leE_in_gg(x1, x2) = leE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 gtF_in_gg(x1, x2) = gtF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) 14.43/4.61 14.43/4.61 U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) 14.43/4.61 14.43/4.61 U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x2, x5) 14.43/4.61 14.43/4.61 U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U12_GA(x1, x2, x3, x4, x5) = U12_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U15_GA(x1, x2, x3, x4, x5, x6) = U15_GA(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U16_GA(x1, x2, x3, x4, x5) = U16_GA(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) 14.43/4.61 14.43/4.61 U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 LEE_IN_GG(x1, x2) = LEE_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) 14.43/4.61 14.43/4.61 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 GTF_IN_GG(x1, x2) = GTF_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) 14.43/4.61 14.43/4.61 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (5) DependencyGraphProof (EQUIVALENT) 14.43/4.61 The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 16 less nodes. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (6) 14.43/4.61 Complex Obligation (AND) 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (7) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 The TRS R consists of the following rules: 14.43/4.61 14.43/4.61 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.61 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.61 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.61 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.61 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.61 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.61 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.61 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.61 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.61 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.61 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.61 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.61 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.61 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.61 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.61 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.61 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.61 14.43/4.61 The argument filtering Pi contains the following mapping: 14.43/4.61 .(x1, x2) = .(x1, x2) 14.43/4.61 14.43/4.61 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.61 14.43/4.61 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.61 14.43/4.61 [] = [] 14.43/4.61 14.43/4.61 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.61 14.43/4.61 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.61 14.43/4.61 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.61 14.43/4.61 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.61 14.43/4.61 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.61 14.43/4.61 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 s(x1) = s(x1) 14.43/4.61 14.43/4.61 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 0 = 0 14.43/4.61 14.43/4.61 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 GTF_IN_GG(x1, x2) = GTF_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (8) UsableRulesProof (EQUIVALENT) 14.43/4.61 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (9) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 R is empty. 14.43/4.61 Pi is empty. 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (10) PiDPToQDPProof (EQUIVALENT) 14.43/4.61 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (11) 14.43/4.61 Obligation: 14.43/4.61 Q DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 R is empty. 14.43/4.61 Q is empty. 14.43/4.61 We have to consider all (P,Q,R)-chains. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (12) QDPSizeChangeProof (EQUIVALENT) 14.43/4.61 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. 14.43/4.61 14.43/4.61 From the DPs we obtained the following set of size-change graphs: 14.43/4.61 *GTF_IN_GG(s(X1), s(X2)) -> GTF_IN_GG(X1, X2) 14.43/4.61 The graph contains the following edges 1 > 1, 2 > 2 14.43/4.61 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (13) 14.43/4.61 YES 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (14) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 The TRS R consists of the following rules: 14.43/4.61 14.43/4.61 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.61 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.61 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.61 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.61 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.61 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.61 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.61 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.61 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.61 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.61 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.61 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.61 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.61 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.61 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.61 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.61 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.61 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.61 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.61 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.61 14.43/4.61 The argument filtering Pi contains the following mapping: 14.43/4.61 .(x1, x2) = .(x1, x2) 14.43/4.61 14.43/4.61 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.61 14.43/4.61 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.61 14.43/4.61 [] = [] 14.43/4.61 14.43/4.61 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.61 14.43/4.61 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.61 14.43/4.61 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.61 14.43/4.61 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.61 14.43/4.61 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.61 14.43/4.61 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.61 14.43/4.61 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.61 14.43/4.61 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.61 14.43/4.61 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.61 14.43/4.61 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.61 14.43/4.61 s(x1) = s(x1) 14.43/4.61 14.43/4.61 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 0 = 0 14.43/4.61 14.43/4.61 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.61 14.43/4.61 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.61 14.43/4.61 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.61 14.43/4.61 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.61 14.43/4.61 LEE_IN_GG(x1, x2) = LEE_IN_GG(x1, x2) 14.43/4.61 14.43/4.61 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (15) UsableRulesProof (EQUIVALENT) 14.43/4.61 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (16) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 R is empty. 14.43/4.61 Pi is empty. 14.43/4.61 We have to consider all (P,R,Pi)-chains 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (17) PiDPToQDPProof (EQUIVALENT) 14.43/4.61 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (18) 14.43/4.61 Obligation: 14.43/4.61 Q DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 14.43/4.61 R is empty. 14.43/4.61 Q is empty. 14.43/4.61 We have to consider all (P,Q,R)-chains. 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (19) QDPSizeChangeProof (EQUIVALENT) 14.43/4.61 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. 14.43/4.61 14.43/4.61 From the DPs we obtained the following set of size-change graphs: 14.43/4.61 *LEE_IN_GG(s(X1), s(X2)) -> LEE_IN_GG(X1, X2) 14.43/4.61 The graph contains the following edges 1 > 1, 2 > 2 14.43/4.61 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (20) 14.43/4.61 YES 14.43/4.61 14.43/4.61 ---------------------------------------- 14.43/4.61 14.43/4.61 (21) 14.43/4.61 Obligation: 14.43/4.61 Pi DP problem: 14.43/4.61 The TRS P consists of the following rules: 14.43/4.61 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.61 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) 14.43/4.61 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.61 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) 14.43/4.61 14.43/4.61 The TRS R consists of the following rules: 14.43/4.61 14.43/4.61 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.61 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.61 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.61 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.61 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.61 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.61 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.61 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.61 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.62 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.62 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.62 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The argument filtering Pi contains the following mapping: 14.43/4.62 .(x1, x2) = .(x1, x2) 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.62 14.43/4.62 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.62 14.43/4.62 [] = [] 14.43/4.62 14.43/4.62 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.62 14.43/4.62 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.62 14.43/4.62 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.62 14.43/4.62 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.62 14.43/4.62 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.62 14.43/4.62 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.62 14.43/4.62 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.62 14.43/4.62 s(x1) = s(x1) 14.43/4.62 14.43/4.62 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 0 = 0 14.43/4.62 14.43/4.62 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.62 14.43/4.62 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) 14.43/4.62 14.43/4.62 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 14.43/4.62 We have to consider all (P,R,Pi)-chains 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (22) UsableRulesProof (EQUIVALENT) 14.43/4.62 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (23) 14.43/4.62 Obligation: 14.43/4.62 Pi DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.62 U3_GGA(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The argument filtering Pi contains the following mapping: 14.43/4.62 .(x1, x2) = .(x1, x2) 14.43/4.62 14.43/4.62 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.62 14.43/4.62 s(x1) = s(x1) 14.43/4.62 14.43/4.62 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 0 = 0 14.43/4.62 14.43/4.62 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.62 14.43/4.62 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.62 14.43/4.62 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) 14.43/4.62 14.43/4.62 U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 14.43/4.62 We have to consider all (P,R,Pi)-chains 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (24) PiDPToQDPProof (SOUND) 14.43/4.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (25) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 U3_GGA(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (26) MRRProof (EQUIVALENT) 14.43/4.62 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 14.43/4.62 14.43/4.62 14.43/4.62 Strictly oriented rules of the TRS R: 14.43/4.62 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 14.43/4.62 Used ordering: Polynomial interpretation [POLO]: 14.43/4.62 14.43/4.62 POL(.(x_1, x_2)) = 2*x_1 + x_2 14.43/4.62 POL(0) = 1 14.43/4.62 POL(MERGEC_IN_GGA(x_1, x_2)) = 2*x_1 + 2*x_2 14.43/4.62 POL(U27_gg(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 14.43/4.62 POL(U28_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 14.43/4.62 POL(U3_GGA(x_1, x_2, x_3, x_4, x_5)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 + x_5 14.43/4.62 POL(U6_GGA(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + x_3 + 2*x_4 + 2*x_5 14.43/4.62 POL(gtcF_in_gg(x_1, x_2)) = x_1 + x_2 14.43/4.62 POL(gtcF_out_gg(x_1, x_2)) = x_1 + x_2 14.43/4.62 POL(lecE_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 14.43/4.62 POL(lecE_out_gg(x_1, x_2)) = x_1 + 2*x_2 14.43/4.62 POL(s(x_1)) = 2*x_1 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (27) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 U3_GGA(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (28) MRRProof (EQUIVALENT) 14.43/4.62 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 14.43/4.62 14.43/4.62 Strictly oriented dependency pairs: 14.43/4.62 14.43/4.62 U3_GGA(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) 14.43/4.62 14.43/4.62 14.43/4.62 Used ordering: Polynomial interpretation [POLO]: 14.43/4.62 14.43/4.62 POL(.(x_1, x_2)) = 2*x_1 + x_2 14.43/4.62 POL(0) = 0 14.43/4.62 POL(MERGEC_IN_GGA(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 14.43/4.62 POL(U27_gg(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 14.43/4.62 POL(U28_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 14.43/4.62 POL(U3_GGA(x_1, x_2, x_3, x_4, x_5)) = 1 + x_1 + 2*x_2 + 2*x_3 + 2*x_4 + x_5 14.43/4.62 POL(U6_GGA(x_1, x_2, x_3, x_4, x_5)) = 1 + 2*x_1 + 2*x_2 + x_3 + 2*x_4 + 2*x_5 14.43/4.62 POL(gtcF_in_gg(x_1, x_2)) = x_1 + x_2 14.43/4.62 POL(gtcF_out_gg(x_1, x_2)) = x_1 + x_2 14.43/4.62 POL(lecE_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 14.43/4.62 POL(lecE_out_gg(x_1, x_2)) = 1 + x_1 + 2*x_2 14.43/4.62 POL(s(x_1)) = 2*x_1 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (29) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (30) DependencyGraphProof (EQUIVALENT) 14.43/4.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (31) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (32) UsableRulesProof (EQUIVALENT) 14.43/4.62 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (33) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (34) QReductionProof (EQUIVALENT) 14.43/4.62 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 14.43/4.62 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (35) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (36) QDPSizeChangeProof (EQUIVALENT) 14.43/4.62 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. 14.43/4.62 14.43/4.62 From the DPs we obtained the following set of size-change graphs: 14.43/4.62 *U6_GGA(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) 14.43/4.62 The graph contains the following edges 4 >= 2 14.43/4.62 14.43/4.62 14.43/4.62 *MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 The graph contains the following edges 1 > 1, 1 > 2, 2 > 3, 2 > 4 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (37) 14.43/4.62 YES 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (38) 14.43/4.62 Obligation: 14.43/4.62 Pi DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> SPLITA_IN_GAA(X2, X4, X3) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.62 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.62 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.62 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.62 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.62 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.62 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.62 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.62 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.62 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The argument filtering Pi contains the following mapping: 14.43/4.62 .(x1, x2) = .(x1, x2) 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.62 14.43/4.62 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.62 14.43/4.62 [] = [] 14.43/4.62 14.43/4.62 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.62 14.43/4.62 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.62 14.43/4.62 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.62 14.43/4.62 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.62 14.43/4.62 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.62 14.43/4.62 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.62 14.43/4.62 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.62 14.43/4.62 s(x1) = s(x1) 14.43/4.62 14.43/4.62 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 0 = 0 14.43/4.62 14.43/4.62 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.62 14.43/4.62 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) 14.43/4.62 14.43/4.62 14.43/4.62 We have to consider all (P,R,Pi)-chains 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (39) UsableRulesProof (EQUIVALENT) 14.43/4.62 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (40) 14.43/4.62 Obligation: 14.43/4.62 Pi DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 SPLITA_IN_GAA(.(X1, X2), .(X1, X3), X4) -> SPLITA_IN_GAA(X2, X4, X3) 14.43/4.62 14.43/4.62 R is empty. 14.43/4.62 The argument filtering Pi contains the following mapping: 14.43/4.62 .(x1, x2) = .(x1, x2) 14.43/4.62 14.43/4.62 SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) 14.43/4.62 14.43/4.62 14.43/4.62 We have to consider all (P,R,Pi)-chains 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (41) PiDPToQDPProof (SOUND) 14.43/4.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (42) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 SPLITA_IN_GAA(.(X1, X2)) -> SPLITA_IN_GAA(X2) 14.43/4.62 14.43/4.62 R is empty. 14.43/4.62 Q is empty. 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (43) QDPSizeChangeProof (EQUIVALENT) 14.43/4.62 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. 14.43/4.62 14.43/4.62 From the DPs we obtained the following set of size-change graphs: 14.43/4.62 *SPLITA_IN_GAA(.(X1, X2)) -> SPLITA_IN_GAA(X2) 14.43/4.62 The graph contains the following edges 1 > 1 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (44) 14.43/4.62 YES 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (45) 14.43/4.62 Obligation: 14.43/4.62 Pi DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.62 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6), X7) 14.43/4.62 U11_GA(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.62 U13_GA(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5, X8) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(X1, X2, .(X1, X3), X4) -> U29_ggaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.62 splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2), .(X1, X3), X4) -> U18_gaa(X1, X2, X3, X4, splitcA_in_gaa(X2, X4, X3)) 14.43/4.62 U18_gaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 U29_ggaa(X1, X2, X3, X4, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) 14.43/4.62 mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.62 mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcD_in_ggaa(X2, X3, X5, X6)) 14.43/4.62 U19_ga(X1, X2, X3, X4, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X5, mergesortcB_in_ga(.(X1, X6), X7)) 14.43/4.62 U20_ga(X1, X2, X3, X4, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(X5, X8)) 14.43/4.62 U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) 14.43/4.62 mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, X5, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, X5, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) 14.43/4.62 U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The argument filtering Pi contains the following mapping: 14.43/4.62 .(x1, x2) = .(x1, x2) 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x1, x2, x3, x4) = splitcD_in_ggaa(x1, x2) 14.43/4.62 14.43/4.62 U29_ggaa(x1, x2, x3, x4, x5) = U29_ggaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) 14.43/4.62 14.43/4.62 [] = [] 14.43/4.62 14.43/4.62 splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) 14.43/4.62 14.43/4.62 U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x1, x2, x5) 14.43/4.62 14.43/4.62 splitcD_out_ggaa(x1, x2, x3, x4) = splitcD_out_ggaa(x1, x2, x3, x4) 14.43/4.62 14.43/4.62 mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) 14.43/4.62 14.43/4.62 mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) 14.43/4.62 14.43/4.62 U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) 14.43/4.62 14.43/4.62 mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) 14.43/4.62 14.43/4.62 U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 lecE_in_gg(x1, x2) = lecE_in_gg(x1, x2) 14.43/4.62 14.43/4.62 s(x1) = s(x1) 14.43/4.62 14.43/4.62 U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 0 = 0 14.43/4.62 14.43/4.62 lecE_out_gg(x1, x2) = lecE_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 gtcF_in_gg(x1, x2) = gtcF_in_gg(x1, x2) 14.43/4.62 14.43/4.62 U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) 14.43/4.62 14.43/4.62 gtcF_out_gg(x1, x2) = gtcF_out_gg(x1, x2) 14.43/4.62 14.43/4.62 U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) 14.43/4.62 14.43/4.62 MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) 14.43/4.62 14.43/4.62 U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) 14.43/4.62 14.43/4.62 U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) 14.43/4.62 14.43/4.62 14.43/4.62 We have to consider all (P,R,Pi)-chains 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (46) PiDPToQDPProof (SOUND) 14.43/4.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (47) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, splitcD_in_ggaa(X2, X3)) 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6)) 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 U13_GA(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(X1, X2) -> U29_ggaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2)) -> U18_gaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 U18_gaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 U29_ggaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 mergesortcB_in_ga([]) -> mergesortcB_out_ga([], []) 14.43/4.62 mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.62 mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcD_in_ggaa(X2, X3)) 14.43/4.62 U19_ga(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 U20_ga(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(X5)) 14.43/4.62 U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) 14.43/4.62 mergecC_in_gga(X1, []) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U23_gga(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, mergecC_in_gga(X2, .(X3, X4))) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U25_gga(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, mergecC_in_gga(.(X1, X2), X4)) 14.43/4.62 U26_gga(X1, X2, X3, X4, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x0, x1) 14.43/4.62 splitcA_in_gaa(x0) 14.43/4.62 U18_gaa(x0, x1, x2) 14.43/4.62 U29_ggaa(x0, x1, x2) 14.43/4.62 mergesortcB_in_ga(x0) 14.43/4.62 U19_ga(x0, x1, x2, x3) 14.43/4.62 U20_ga(x0, x1, x2, x3, x4) 14.43/4.62 U21_ga(x0, x1, x2, x3, x4) 14.43/4.62 mergecC_in_gga(x0, x1) 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U23_gga(x0, x1, x2, x3, x4) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 U25_gga(x0, x1, x2, x3, x4) 14.43/4.62 U26_gga(x0, x1, x2, x3, x4) 14.43/4.62 U24_gga(x0, x1, x2, x3, x4) 14.43/4.62 U22_ga(x0, x1, x2, x3) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (48) TransformationProof (EQUIVALENT) 14.43/4.62 By rewriting [LPAR04] the rule MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, splitcD_in_ggaa(X2, X3)) at position [3] we obtained the following new rules [LPAR04]: 14.43/4.62 14.43/4.62 (MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, U29_ggaa(X2, X3, splitcA_in_gaa(X3))),MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, U29_ggaa(X2, X3, splitcA_in_gaa(X3)))) 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (49) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6)) 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 U13_GA(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5) 14.43/4.62 MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, U29_ggaa(X2, X3, splitcA_in_gaa(X3))) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(X1, X2) -> U29_ggaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2)) -> U18_gaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 U18_gaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 U29_ggaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 mergesortcB_in_ga([]) -> mergesortcB_out_ga([], []) 14.43/4.62 mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.62 mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcD_in_ggaa(X2, X3)) 14.43/4.62 U19_ga(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 U20_ga(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(X5)) 14.43/4.62 U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) 14.43/4.62 mergecC_in_gga(X1, []) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U23_gga(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, mergecC_in_gga(X2, .(X3, X4))) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U25_gga(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, mergecC_in_gga(.(X1, X2), X4)) 14.43/4.62 U26_gga(X1, X2, X3, X4, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x0, x1) 14.43/4.62 splitcA_in_gaa(x0) 14.43/4.62 U18_gaa(x0, x1, x2) 14.43/4.62 U29_ggaa(x0, x1, x2) 14.43/4.62 mergesortcB_in_ga(x0) 14.43/4.62 U19_ga(x0, x1, x2, x3) 14.43/4.62 U20_ga(x0, x1, x2, x3, x4) 14.43/4.62 U21_ga(x0, x1, x2, x3, x4) 14.43/4.62 mergecC_in_gga(x0, x1) 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U23_gga(x0, x1, x2, x3, x4) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 U25_gga(x0, x1, x2, x3, x4) 14.43/4.62 U26_gga(x0, x1, x2, x3, x4) 14.43/4.62 U24_gga(x0, x1, x2, x3, x4) 14.43/4.62 U22_ga(x0, x1, x2, x3) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (50) QDPOrderProof (EQUIVALENT) 14.43/4.62 We use the reduction pair processor [LPAR04,JAR06]. 14.43/4.62 14.43/4.62 14.43/4.62 The following pairs can be oriented strictly and are deleted. 14.43/4.62 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X6)) 14.43/4.62 U13_GA(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> MERGESORTB_IN_GA(X5) 14.43/4.62 The remaining pairs can at least be oriented weakly. 14.43/4.62 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 14.43/4.62 14.43/4.62 POL( U13_GA_5(x_1, ..., x_5) ) = 2x_4 + 2 14.43/4.62 POL( mergesortcB_in_ga_1(x_1) ) = 0 14.43/4.62 POL( ._2(x_1, x_2) ) = 2x_2 + 1 14.43/4.62 POL( [] ) = 0 14.43/4.62 POL( mergesortcB_out_ga_2(x_1, x_2) ) = max{0, x_2 - 2} 14.43/4.62 POL( U19_ga_4(x_1, ..., x_4) ) = 2x_1 + 2 14.43/4.62 POL( splitcD_in_ggaa_2(x_1, x_2) ) = 2 14.43/4.62 POL( U11_GA_4(x_1, ..., x_4) ) = 2x_4 + 2 14.43/4.62 POL( U29_ggaa_3(x_1, ..., x_3) ) = 2x_3 + 1 14.43/4.62 POL( splitcA_in_gaa_1(x_1) ) = 2x_1 14.43/4.62 POL( splitcA_out_gaa_3(x_1, ..., x_3) ) = x_2 + x_3 14.43/4.62 POL( U18_gaa_3(x_1, ..., x_3) ) = 2x_3 + 1 14.43/4.62 POL( splitcD_out_ggaa_4(x_1, ..., x_4) ) = x_3 + 2x_4 14.43/4.62 POL( U20_ga_5(x_1, ..., x_5) ) = max{0, 2x_2 + x_3 + 2x_4 + 2x_5 - 2} 14.43/4.62 POL( U21_ga_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_2 - 2} 14.43/4.62 POL( U22_ga_4(x_1, ..., x_4) ) = x_3 + 2x_4 + 2 14.43/4.62 POL( mergecC_in_gga_2(x_1, x_2) ) = max{0, -2} 14.43/4.62 POL( mergecC_out_gga_3(x_1, ..., x_3) ) = x_1 + x_3 + 2 14.43/4.62 POL( U23_gga_5(x_1, ..., x_5) ) = max{0, 2x_1 + 2x_2 + 2x_3 + x_4 + 2x_5 - 2} 14.43/4.62 POL( lecE_in_gg_2(x_1, x_2) ) = 2x_1 + 2x_2 14.43/4.62 POL( U25_gga_5(x_1, ..., x_5) ) = 2x_1 + 2x_2 + 2x_4 + 2 14.43/4.62 POL( gtcF_in_gg_2(x_1, x_2) ) = 0 14.43/4.62 POL( s_1(x_1) ) = x_1 14.43/4.62 POL( U27_gg_3(x_1, ..., x_3) ) = 2 14.43/4.62 POL( 0 ) = 0 14.43/4.62 POL( lecE_out_gg_2(x_1, x_2) ) = max{0, 2x_1 - 2} 14.43/4.62 POL( U24_gga_5(x_1, ..., x_5) ) = max{0, 2x_1 + x_3 - 2} 14.43/4.62 POL( U28_gg_3(x_1, ..., x_3) ) = 2x_1 + 2 14.43/4.62 POL( gtcF_out_gg_2(x_1, x_2) ) = max{0, -2} 14.43/4.62 POL( U26_gga_5(x_1, ..., x_5) ) = max{0, 2x_3 - 2} 14.43/4.62 POL( MERGESORTB_IN_GA_1(x_1) ) = max{0, 2x_1 - 2} 14.43/4.62 14.43/4.62 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 14.43/4.62 14.43/4.62 splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2)) -> U18_gaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 U29_ggaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 U18_gaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 14.43/4.62 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (51) 14.43/4.62 Obligation: 14.43/4.62 Q DP problem: 14.43/4.62 The TRS P consists of the following rules: 14.43/4.62 14.43/4.62 U11_GA(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U13_GA(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, U29_ggaa(X2, X3, splitcA_in_gaa(X3))) 14.43/4.62 14.43/4.62 The TRS R consists of the following rules: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(X1, X2) -> U29_ggaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) 14.43/4.62 splitcA_in_gaa(.(X1, X2)) -> U18_gaa(X1, X2, splitcA_in_gaa(X2)) 14.43/4.62 U18_gaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcA_out_gaa(.(X1, X2), .(X1, X3), X4) 14.43/4.62 U29_ggaa(X1, X2, splitcA_out_gaa(X2, X4, X3)) -> splitcD_out_ggaa(X1, X2, .(X1, X3), X4) 14.43/4.62 mergesortcB_in_ga([]) -> mergesortcB_out_ga([], []) 14.43/4.62 mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) 14.43/4.62 mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcD_in_ggaa(X2, X3)) 14.43/4.62 U19_ga(X1, X2, X3, splitcD_out_ggaa(X2, X3, X5, X6)) -> U20_ga(X1, X2, X3, X5, mergesortcB_in_ga(.(X1, X6))) 14.43/4.62 U20_ga(X1, X2, X3, X5, mergesortcB_out_ga(.(X1, X6), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(X5)) 14.43/4.62 U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(X5, X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) 14.43/4.62 mergecC_in_gga(X1, []) -> mergecC_out_gga(X1, [], X1) 14.43/4.62 mergecC_in_gga([], X1) -> mergecC_out_gga([], X1, X1) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U23_gga(X1, X2, X3, X4, lecE_in_gg(X1, X3)) 14.43/4.62 lecE_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecE_in_gg(X1, X2)) 14.43/4.62 lecE_in_gg(0, s(X1)) -> lecE_out_gg(0, s(X1)) 14.43/4.62 lecE_in_gg(0, 0) -> lecE_out_gg(0, 0) 14.43/4.62 U27_gg(X1, X2, lecE_out_gg(X1, X2)) -> lecE_out_gg(s(X1), s(X2)) 14.43/4.62 U23_gga(X1, X2, X3, X4, lecE_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, mergecC_in_gga(X2, .(X3, X4))) 14.43/4.62 mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U25_gga(X1, X2, X3, X4, gtcF_in_gg(X1, X3)) 14.43/4.62 gtcF_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcF_in_gg(X1, X2)) 14.43/4.62 gtcF_in_gg(s(X1), 0) -> gtcF_out_gg(s(X1), 0) 14.43/4.62 U28_gg(X1, X2, gtcF_out_gg(X1, X2)) -> gtcF_out_gg(s(X1), s(X2)) 14.43/4.62 U25_gga(X1, X2, X3, X4, gtcF_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, mergecC_in_gga(.(X1, X2), X4)) 14.43/4.62 U26_gga(X1, X2, X3, X4, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) 14.43/4.62 U24_gga(X1, X2, X3, X4, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) 14.43/4.62 U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) 14.43/4.62 14.43/4.62 The set Q consists of the following terms: 14.43/4.62 14.43/4.62 splitcD_in_ggaa(x0, x1) 14.43/4.62 splitcA_in_gaa(x0) 14.43/4.62 U18_gaa(x0, x1, x2) 14.43/4.62 U29_ggaa(x0, x1, x2) 14.43/4.62 mergesortcB_in_ga(x0) 14.43/4.62 U19_ga(x0, x1, x2, x3) 14.43/4.62 U20_ga(x0, x1, x2, x3, x4) 14.43/4.62 U21_ga(x0, x1, x2, x3, x4) 14.43/4.62 mergecC_in_gga(x0, x1) 14.43/4.62 lecE_in_gg(x0, x1) 14.43/4.62 U27_gg(x0, x1, x2) 14.43/4.62 U23_gga(x0, x1, x2, x3, x4) 14.43/4.62 gtcF_in_gg(x0, x1) 14.43/4.62 U28_gg(x0, x1, x2) 14.43/4.62 U25_gga(x0, x1, x2, x3, x4) 14.43/4.62 U26_gga(x0, x1, x2, x3, x4) 14.43/4.62 U24_gga(x0, x1, x2, x3, x4) 14.43/4.62 U22_ga(x0, x1, x2, x3) 14.43/4.62 14.43/4.62 We have to consider all (P,Q,R)-chains. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (52) DependencyGraphProof (EQUIVALENT) 14.43/4.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 14.43/4.62 ---------------------------------------- 14.43/4.62 14.43/4.62 (53) 14.43/4.62 TRUE 14.63/4.66 EOF