4.05/1.87 YES 4.31/2.36 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.31/2.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.31/2.36 4.31/2.36 4.31/2.36 Left Termination of the query pattern 4.31/2.36 4.31/2.36 transpose(g,a) 4.31/2.36 4.31/2.36 w.r.t. the given Prolog program could successfully be proven: 4.31/2.36 4.31/2.36 (0) Prolog 4.31/2.36 (1) PrologToDTProblemTransformerProof [SOUND, 41 ms] 4.31/2.36 (2) TRIPLES 4.31/2.36 (3) TriplesToPiDPProof [SOUND, 0 ms] 4.31/2.36 (4) PiDP 4.31/2.36 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.31/2.36 (6) AND 4.31/2.36 (7) PiDP 4.31/2.36 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.31/2.36 (9) PiDP 4.31/2.36 (10) PiDPToQDPProof [SOUND, 1 ms] 4.31/2.36 (11) QDP 4.31/2.36 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.31/2.36 (13) YES 4.31/2.36 (14) PiDP 4.31/2.36 (15) PiDPToQDPProof [SOUND, 0 ms] 4.31/2.36 (16) QDP 4.31/2.36 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.31/2.36 (18) YES 4.31/2.36 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (0) 4.31/2.36 Obligation: 4.31/2.36 Clauses: 4.31/2.36 4.31/2.36 transpose(A, B) :- transpose_aux(A, [], B). 4.31/2.36 transpose_aux(.(R, Rs), X1, .(C, Cs)) :- ','(row2col(R, .(C, Cs), Cols1, Accm), transpose_aux(Rs, Accm, Cols1)). 4.31/2.36 transpose_aux([], X, X). 4.31/2.36 row2col(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), .([], As)) :- row2col(Xs, Cols, Cols1, As). 4.31/2.36 row2col([], [], [], []). 4.31/2.36 4.31/2.36 4.31/2.36 Query: transpose(g,a) 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (1) PrologToDTProblemTransformerProof (SOUND) 4.31/2.36 Built DT problem from termination graph DT10. 4.31/2.36 4.31/2.36 { 4.31/2.36 "root": 2, 4.31/2.36 "program": { 4.31/2.36 "directives": [], 4.31/2.36 "clauses": [ 4.31/2.36 [ 4.31/2.36 "(transpose A B)", 4.31/2.36 "(transpose_aux A ([]) B)" 4.31/2.36 ], 4.31/2.36 [ 4.31/2.36 "(transpose_aux (. R Rs) X1 (. C Cs))", 4.31/2.36 "(',' (row2col R (. C Cs) Cols1 Accm) (transpose_aux Rs Accm Cols1))" 4.31/2.36 ], 4.31/2.36 [ 4.31/2.36 "(transpose_aux ([]) X X)", 4.31/2.36 null 4.31/2.36 ], 4.31/2.36 [ 4.31/2.36 "(row2col (. X Xs) (. (. X Ys) Cols) (. Ys Cols1) (. ([]) As))", 4.31/2.36 "(row2col Xs Cols Cols1 As)" 4.31/2.36 ], 4.31/2.36 [ 4.31/2.36 "(row2col ([]) ([]) ([]) ([]))", 4.31/2.36 null 4.31/2.36 ] 4.31/2.36 ] 4.31/2.36 }, 4.31/2.36 "graph": { 4.31/2.36 "nodes": { 4.31/2.36 "type": "Nodes", 4.31/2.36 "150": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 3, 4.31/2.36 "scope": 3, 4.31/2.36 "term": "(row2col T24 (. T28 T29) X35 X36)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T24"], 4.31/2.36 "free": [ 4.31/2.36 "X35", 4.31/2.36 "X36" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "151": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 4, 4.31/2.36 "scope": 3, 4.31/2.36 "term": "(row2col T24 (. T28 T29) X35 X36)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T24"], 4.31/2.36 "free": [ 4.31/2.36 "X35", 4.31/2.36 "X36" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "152": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(row2col T57 T60 X91 X92)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T57"], 4.31/2.36 "free": [ 4.31/2.36 "X91", 4.31/2.36 "X92" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "153": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "154": { 4.31/2.36 "goal": [ 4.31/2.36 { 4.31/2.36 "clause": 3, 4.31/2.36 "scope": 4, 4.31/2.36 "term": "(row2col T57 T60 X91 X92)" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "clause": 4, 4.31/2.36 "scope": 4, 4.31/2.36 "term": "(row2col T57 T60 X91 X92)" 4.31/2.36 } 4.31/2.36 ], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T57"], 4.31/2.36 "free": [ 4.31/2.36 "X91", 4.31/2.36 "X92" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "155": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 3, 4.31/2.36 "scope": 4, 4.31/2.36 "term": "(row2col T57 T60 X91 X92)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T57"], 4.31/2.36 "free": [ 4.31/2.36 "X91", 4.31/2.36 "X92" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "156": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 4, 4.31/2.36 "scope": 4, 4.31/2.36 "term": "(row2col T57 T60 X91 X92)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T57"], 4.31/2.36 "free": [ 4.31/2.36 "X91", 4.31/2.36 "X92" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "310": { 4.31/2.36 "goal": [ 4.31/2.36 { 4.31/2.36 "clause": 1, 4.31/2.36 "scope": 5, 4.31/2.36 "term": "(transpose_aux T25 T35 T34)" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "clause": 2, 4.31/2.36 "scope": 5, 4.31/2.36 "term": "(transpose_aux T25 T35 T34)" 4.31/2.36 } 4.31/2.36 ], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T25", 4.31/2.36 "T35" 4.31/2.36 ], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "157": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(row2col T82 T85 X139 X140)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T82"], 4.31/2.36 "free": [ 4.31/2.36 "X139", 4.31/2.36 "X140" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "311": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 1, 4.31/2.36 "scope": 5, 4.31/2.36 "term": "(transpose_aux T25 T35 T34)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T25", 4.31/2.36 "T35" 4.31/2.36 ], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "158": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "312": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 2, 4.31/2.36 "scope": 5, 4.31/2.36 "term": "(transpose_aux T25 T35 T34)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T25", 4.31/2.36 "T35" 4.31/2.36 ], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "313": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(',' (row2col T115 (. T120 T121) X185 X186) (transpose_aux T116 X186 X185))" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T115", 4.31/2.36 "T116" 4.31/2.36 ], 4.31/2.36 "free": [ 4.31/2.36 "X185", 4.31/2.36 "X186" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "314": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "315": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(true)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "316": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "140": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 1, 4.31/2.36 "scope": 2, 4.31/2.36 "term": "(transpose_aux T5 ([]) T7)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T5"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "141": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 2, 4.31/2.36 "scope": 2, 4.31/2.36 "term": "(transpose_aux T5 ([]) T7)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T5"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "142": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(',' (row2col T24 (. T28 T29) X35 X36) (transpose_aux T25 X36 X35))" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T24", 4.31/2.36 "T25" 4.31/2.36 ], 4.31/2.36 "free": [ 4.31/2.36 "X35", 4.31/2.36 "X36" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "2": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(transpose T1 T2)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T1"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "145": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "3": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": 0, 4.31/2.36 "scope": 1, 4.31/2.36 "term": "(transpose T1 T2)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T1"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "147": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(row2col T24 (. T28 T29) X35 X36)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T24"], 4.31/2.36 "free": [ 4.31/2.36 "X35", 4.31/2.36 "X36" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "148": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(transpose_aux T25 T35 T34)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [ 4.31/2.36 "T25", 4.31/2.36 "T35" 4.31/2.36 ], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "6": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(transpose_aux T5 ([]) T7)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T5"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "149": { 4.31/2.36 "goal": [ 4.31/2.36 { 4.31/2.36 "clause": 3, 4.31/2.36 "scope": 3, 4.31/2.36 "term": "(row2col T24 (. T28 T29) X35 X36)" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "clause": 4, 4.31/2.36 "scope": 3, 4.31/2.36 "term": "(row2col T24 (. T28 T29) X35 X36)" 4.31/2.36 } 4.31/2.36 ], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T24"], 4.31/2.36 "free": [ 4.31/2.36 "X35", 4.31/2.36 "X36" 4.31/2.36 ], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "325": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "7": { 4.31/2.36 "goal": [ 4.31/2.36 { 4.31/2.36 "clause": 1, 4.31/2.36 "scope": 2, 4.31/2.36 "term": "(transpose_aux T5 ([]) T7)" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "clause": 2, 4.31/2.36 "scope": 2, 4.31/2.36 "term": "(transpose_aux T5 ([]) T7)" 4.31/2.36 } 4.31/2.36 ], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": ["T5"], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "327": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(true)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "306": { 4.31/2.36 "goal": [{ 4.31/2.36 "clause": -1, 4.31/2.36 "scope": -1, 4.31/2.36 "term": "(true)" 4.31/2.36 }], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "328": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "307": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "329": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "308": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "309": { 4.31/2.36 "goal": [], 4.31/2.36 "kb": { 4.31/2.36 "nonunifying": [], 4.31/2.36 "intvars": {}, 4.31/2.36 "arithmetic": { 4.31/2.36 "type": "PlainIntegerRelationState", 4.31/2.36 "relations": [] 4.31/2.36 }, 4.31/2.36 "ground": [], 4.31/2.36 "free": [], 4.31/2.36 "exprvars": [] 4.31/2.36 } 4.31/2.36 } 4.31/2.36 }, 4.31/2.36 "edges": [ 4.31/2.36 { 4.31/2.36 "from": 2, 4.31/2.36 "to": 3, 4.31/2.36 "label": "CASE" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 3, 4.31/2.36 "to": 6, 4.31/2.36 "label": "ONLY EVAL with clause\ntranspose(X4, X5) :- transpose_aux(X4, [], X5).\nand substitutionT1 -> T5,\nX4 -> T5,\nT2 -> T7,\nX5 -> T7,\nT6 -> T7" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 6, 4.31/2.36 "to": 7, 4.31/2.36 "label": "CASE" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 7, 4.31/2.36 "to": 140, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 7, 4.31/2.36 "to": 141, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 140, 4.31/2.36 "to": 142, 4.31/2.36 "label": "EVAL with clause\ntranspose_aux(.(X30, X31), X32, .(X33, X34)) :- ','(row2col(X30, .(X33, X34), X35, X36), transpose_aux(X31, X36, X35)).\nand substitutionX30 -> T24,\nX31 -> T25,\nT5 -> .(T24, T25),\nX32 -> [],\nX33 -> T28,\nX34 -> T29,\nT7 -> .(T28, T29),\nT26 -> T28,\nT27 -> T29" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 140, 4.31/2.36 "to": 145, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 141, 4.31/2.36 "to": 327, 4.31/2.36 "label": "EVAL with clause\ntranspose_aux([], X200, X200).\nand substitutionT5 -> [],\nX200 -> [],\nT7 -> []" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 141, 4.31/2.36 "to": 328, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 142, 4.31/2.36 "to": 147, 4.31/2.36 "label": "SPLIT 1" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 142, 4.31/2.36 "to": 148, 4.31/2.36 "label": "SPLIT 2\nnew knowledge:\nT24 is ground\nT35 is ground\nreplacements:X35 -> T34,\nX36 -> T35" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 147, 4.31/2.36 "to": 149, 4.31/2.36 "label": "CASE" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 148, 4.31/2.36 "to": 310, 4.31/2.36 "label": "CASE" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 149, 4.31/2.36 "to": 150, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 149, 4.31/2.36 "to": 151, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 150, 4.31/2.36 "to": 152, 4.31/2.36 "label": "EVAL with clause\nrow2col(.(X85, X86), .(.(X85, X87), X88), .(X87, X89), .([], X90)) :- row2col(X86, X88, X89, X90).\nand substitutionX85 -> T56,\nX86 -> T57,\nT24 -> .(T56, T57),\nX87 -> T58,\nT28 -> .(T56, T58),\nT29 -> T60,\nX88 -> T60,\nX89 -> X91,\nX35 -> .(T58, X91),\nX90 -> X92,\nX36 -> .([], X92),\nT59 -> T60" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 150, 4.31/2.36 "to": 153, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 151, 4.31/2.36 "to": 309, 4.31/2.36 "label": "BACKTRACK\nfor clause: row2col([], [], [], [])because of non-unification" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 152, 4.31/2.36 "to": 154, 4.31/2.36 "label": "CASE" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 154, 4.31/2.36 "to": 155, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 154, 4.31/2.36 "to": 156, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 155, 4.31/2.36 "to": 157, 4.31/2.36 "label": "EVAL with clause\nrow2col(.(X133, X134), .(.(X133, X135), X136), .(X135, X137), .([], X138)) :- row2col(X134, X136, X137, X138).\nand substitutionX133 -> T81,\nX134 -> T82,\nT57 -> .(T81, T82),\nX135 -> T83,\nX136 -> T85,\nT60 -> .(.(T81, T83), T85),\nX137 -> X139,\nX91 -> .(T83, X139),\nX138 -> X140,\nX92 -> .([], X140),\nT84 -> T85" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 155, 4.31/2.36 "to": 158, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 156, 4.31/2.36 "to": 306, 4.31/2.36 "label": "EVAL with clause\nrow2col([], [], [], []).\nand substitutionT57 -> [],\nT60 -> [],\nX91 -> [],\nX92 -> []" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 156, 4.31/2.36 "to": 307, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 157, 4.31/2.36 "to": 152, 4.31/2.36 "label": "INSTANCE with matching:\nT57 -> T82\nT60 -> T85\nX91 -> X139\nX92 -> X140" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 306, 4.31/2.36 "to": 308, 4.31/2.36 "label": "SUCCESS" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 310, 4.31/2.36 "to": 311, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 310, 4.31/2.36 "to": 312, 4.31/2.36 "label": "PARALLEL" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 311, 4.31/2.36 "to": 313, 4.31/2.36 "label": "EVAL with clause\ntranspose_aux(.(X180, X181), X182, .(X183, X184)) :- ','(row2col(X180, .(X183, X184), X185, X186), transpose_aux(X181, X186, X185)).\nand substitutionX180 -> T115,\nX181 -> T116,\nT25 -> .(T115, T116),\nT35 -> T117,\nX182 -> T117,\nX183 -> T120,\nX184 -> T121,\nT34 -> .(T120, T121),\nT118 -> T120,\nT119 -> T121" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 311, 4.31/2.36 "to": 314, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 312, 4.31/2.36 "to": 315, 4.31/2.36 "label": "EVAL with clause\ntranspose_aux([], X197, X197).\nand substitutionT25 -> [],\nT35 -> T128,\nX197 -> T128,\nT34 -> T128" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 312, 4.31/2.36 "to": 316, 4.31/2.36 "label": "EVAL-BACKTRACK" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 313, 4.31/2.36 "to": 142, 4.31/2.36 "label": "INSTANCE with matching:\nT24 -> T115\nT28 -> T120\nT29 -> T121\nX35 -> X185\nX36 -> X186\nT25 -> T116" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 315, 4.31/2.36 "to": 325, 4.31/2.36 "label": "SUCCESS" 4.31/2.36 }, 4.31/2.36 { 4.31/2.36 "from": 327, 4.31/2.36 "to": 329, 4.31/2.36 "label": "SUCCESS" 4.31/2.36 } 4.31/2.36 ], 4.31/2.36 "type": "Graph" 4.31/2.36 } 4.31/2.36 } 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (2) 4.31/2.36 Obligation: 4.31/2.36 Triples: 4.31/2.36 4.31/2.36 row2colA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) :- row2colA(X2, X4, X5, X6). 4.31/2.36 pB(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) :- row2colA(X2, X4, X5, X6). 4.31/2.36 pB(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) :- ','(row2colcC(X1, X2, X3, .(X4, X5), X6), pB(X7, X4, X5, X9, X10, X8)). 4.31/2.36 transposeD(.(X1, X2), .(X3, X4)) :- pB(X1, X3, X4, X5, X6, X2). 4.31/2.36 4.31/2.36 Clauses: 4.31/2.36 4.31/2.36 row2colcA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) :- row2colcA(X2, X4, X5, X6). 4.31/2.36 row2colcA([], [], [], []). 4.31/2.36 qcB(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) :- ','(row2colcC(X1, X2, X3, .(X4, X5), X6), qcB(X7, X4, X5, X9, X10, X8)). 4.31/2.36 qcB(X1, X2, X3, X4, X4, []) :- row2colcC(X1, X2, X3, X4, X4). 4.31/2.36 row2colcC(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) :- row2colcA(X2, X4, X5, X6). 4.31/2.36 4.31/2.36 Afs: 4.31/2.36 4.31/2.36 transposeD(x1, x2) = transposeD(x1) 4.31/2.36 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (3) TriplesToPiDPProof (SOUND) 4.31/2.36 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.31/2.36 4.31/2.36 transposeD_in_2: (b,f) 4.31/2.36 4.31/2.36 pB_in_6: (b,f,f,f,f,b) 4.31/2.36 4.31/2.36 row2colA_in_4: (b,f,f,f) 4.31/2.36 4.31/2.36 row2colcC_in_5: (b,f,f,f,f) 4.31/2.36 4.31/2.36 row2colcA_in_4: (b,f,f,f) 4.31/2.36 4.31/2.36 Transforming TRIPLES into the following Term Rewriting System: 4.31/2.36 4.31/2.36 Pi DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> U5_GA(X1, X2, X3, X4, pB_in_gaaaag(X1, X3, X4, X5, X6, X2)) 4.31/2.36 TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> PB_IN_GAAAAG(X1, X3, X4, X5, X6, X2) 4.31/2.36 PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> U2_GAAAAG(X1, X2, X3, X4, X5, X6, X7, row2colA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U1_GAAA(X1, X2, X3, X4, X5, X6, row2colA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) 4.31/2.36 U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> U4_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, pB_in_gaaaag(X7, X4, X5, X9, X10, X8)) 4.31/2.36 U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) 4.31/2.36 4.31/2.36 The TRS R consists of the following rules: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) 4.31/2.36 U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) 4.31/2.36 U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) 4.31/2.36 4.31/2.36 The argument filtering Pi contains the following mapping: 4.31/2.36 .(x1, x2) = .(x1, x2) 4.31/2.36 4.31/2.36 pB_in_gaaaag(x1, x2, x3, x4, x5, x6) = pB_in_gaaaag(x1, x6) 4.31/2.36 4.31/2.36 row2colA_in_gaaa(x1, x2, x3, x4) = row2colA_in_gaaa(x1) 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) 4.31/2.36 4.31/2.36 U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) 4.31/2.36 4.31/2.36 U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 [] = [] 4.31/2.36 4.31/2.36 row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) 4.31/2.36 4.31/2.36 row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) 4.31/2.36 4.31/2.36 TRANSPOSED_IN_GA(x1, x2) = TRANSPOSED_IN_GA(x1) 4.31/2.36 4.31/2.36 U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x5) 4.31/2.36 4.31/2.36 PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) 4.31/2.36 4.31/2.36 U2_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8) = U2_GAAAAG(x1, x2, x7, x8) 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) 4.31/2.36 4.31/2.36 U1_GAAA(x1, x2, x3, x4, x5, x6, x7) = U1_GAAA(x1, x2, x7) 4.31/2.36 4.31/2.36 U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) 4.31/2.36 4.31/2.36 U4_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U4_GAAAAG(x1, x6, x7, x8, x9) 4.31/2.36 4.31/2.36 4.31/2.36 We have to consider all (P,R,Pi)-chains 4.31/2.36 4.31/2.36 4.31/2.36 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 4.31/2.36 4.31/2.36 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (4) 4.31/2.36 Obligation: 4.31/2.36 Pi DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> U5_GA(X1, X2, X3, X4, pB_in_gaaaag(X1, X3, X4, X5, X6, X2)) 4.31/2.36 TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> PB_IN_GAAAAG(X1, X3, X4, X5, X6, X2) 4.31/2.36 PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> U2_GAAAAG(X1, X2, X3, X4, X5, X6, X7, row2colA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U1_GAAA(X1, X2, X3, X4, X5, X6, row2colA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) 4.31/2.36 U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> U4_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, pB_in_gaaaag(X7, X4, X5, X9, X10, X8)) 4.31/2.36 U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) 4.31/2.36 4.31/2.36 The TRS R consists of the following rules: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) 4.31/2.36 U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) 4.31/2.36 U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) 4.31/2.36 4.31/2.36 The argument filtering Pi contains the following mapping: 4.31/2.36 .(x1, x2) = .(x1, x2) 4.31/2.36 4.31/2.36 pB_in_gaaaag(x1, x2, x3, x4, x5, x6) = pB_in_gaaaag(x1, x6) 4.31/2.36 4.31/2.36 row2colA_in_gaaa(x1, x2, x3, x4) = row2colA_in_gaaa(x1) 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) 4.31/2.36 4.31/2.36 U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) 4.31/2.36 4.31/2.36 U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 [] = [] 4.31/2.36 4.31/2.36 row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) 4.31/2.36 4.31/2.36 row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) 4.31/2.36 4.31/2.36 TRANSPOSED_IN_GA(x1, x2) = TRANSPOSED_IN_GA(x1) 4.31/2.36 4.31/2.36 U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x5) 4.31/2.36 4.31/2.36 PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) 4.31/2.36 4.31/2.36 U2_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8) = U2_GAAAAG(x1, x2, x7, x8) 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) 4.31/2.36 4.31/2.36 U1_GAAA(x1, x2, x3, x4, x5, x6, x7) = U1_GAAA(x1, x2, x7) 4.31/2.36 4.31/2.36 U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) 4.31/2.36 4.31/2.36 U4_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U4_GAAAAG(x1, x6, x7, x8, x9) 4.31/2.36 4.31/2.36 4.31/2.36 We have to consider all (P,R,Pi)-chains 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (5) DependencyGraphProof (EQUIVALENT) 4.31/2.36 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (6) 4.31/2.36 Complex Obligation (AND) 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (7) 4.31/2.36 Obligation: 4.31/2.36 Pi DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 4.31/2.36 The TRS R consists of the following rules: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) 4.31/2.36 U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) 4.31/2.36 U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) 4.31/2.36 4.31/2.36 The argument filtering Pi contains the following mapping: 4.31/2.36 .(x1, x2) = .(x1, x2) 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) 4.31/2.36 4.31/2.36 U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) 4.31/2.36 4.31/2.36 U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 [] = [] 4.31/2.36 4.31/2.36 row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) 4.31/2.36 4.31/2.36 row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) 4.31/2.36 4.31/2.36 4.31/2.36 We have to consider all (P,R,Pi)-chains 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (8) UsableRulesProof (EQUIVALENT) 4.31/2.36 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (9) 4.31/2.36 Obligation: 4.31/2.36 Pi DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) 4.31/2.36 4.31/2.36 R is empty. 4.31/2.36 The argument filtering Pi contains the following mapping: 4.31/2.36 .(x1, x2) = .(x1, x2) 4.31/2.36 4.31/2.36 [] = [] 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) 4.31/2.36 4.31/2.36 4.31/2.36 We have to consider all (P,R,Pi)-chains 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (10) PiDPToQDPProof (SOUND) 4.31/2.36 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (11) 4.31/2.36 Obligation: 4.31/2.36 Q DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 ROW2COLA_IN_GAAA(.(X1, X2)) -> ROW2COLA_IN_GAAA(X2) 4.31/2.36 4.31/2.36 R is empty. 4.31/2.36 Q is empty. 4.31/2.36 We have to consider all (P,Q,R)-chains. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (12) QDPSizeChangeProof (EQUIVALENT) 4.31/2.36 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. 4.31/2.36 4.31/2.36 From the DPs we obtained the following set of size-change graphs: 4.31/2.36 *ROW2COLA_IN_GAAA(.(X1, X2)) -> ROW2COLA_IN_GAAA(X2) 4.31/2.36 The graph contains the following edges 1 > 1 4.31/2.36 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (13) 4.31/2.36 YES 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (14) 4.31/2.36 Obligation: 4.31/2.36 Pi DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) 4.31/2.36 U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) 4.31/2.36 4.31/2.36 The TRS R consists of the following rules: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) 4.31/2.36 row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) 4.31/2.36 U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) 4.31/2.36 U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) 4.31/2.36 4.31/2.36 The argument filtering Pi contains the following mapping: 4.31/2.36 .(x1, x2) = .(x1, x2) 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) 4.31/2.36 4.31/2.36 U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) 4.31/2.36 4.31/2.36 U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) 4.31/2.36 4.31/2.36 [] = [] 4.31/2.36 4.31/2.36 row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) 4.31/2.36 4.31/2.36 row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) 4.31/2.36 4.31/2.36 PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) 4.31/2.36 4.31/2.36 U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) 4.31/2.36 4.31/2.36 4.31/2.36 We have to consider all (P,R,Pi)-chains 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (15) PiDPToQDPProof (SOUND) 4.31/2.36 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (16) 4.31/2.36 Obligation: 4.31/2.36 Q DP problem: 4.31/2.36 The TRS P consists of the following rules: 4.31/2.36 4.31/2.36 PB_IN_GAAAAG(X1, .(X7, X8)) -> U3_GAAAAG(X1, X7, X8, row2colcC_in_gaaaa(X1)) 4.31/2.36 U3_GAAAAG(X1, X7, X8, row2colcC_out_gaaaa(X1, X6)) -> PB_IN_GAAAAG(X7, X8) 4.31/2.36 4.31/2.36 The TRS R consists of the following rules: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(.(X1, X2)) -> U11_gaaaa(X1, X2, row2colcA_in_gaaa(X2)) 4.31/2.36 row2colcA_in_gaaa(.(X1, X2)) -> U7_gaaa(X1, X2, row2colcA_in_gaaa(X2)) 4.31/2.36 row2colcA_in_gaaa([]) -> row2colcA_out_gaaa([], []) 4.31/2.36 U7_gaaa(X1, X2, row2colcA_out_gaaa(X2, X6)) -> row2colcA_out_gaaa(.(X1, X2), .([], X6)) 4.31/2.36 U11_gaaaa(X1, X2, row2colcA_out_gaaa(X2, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .([], X6)) 4.31/2.36 4.31/2.36 The set Q consists of the following terms: 4.31/2.36 4.31/2.36 row2colcC_in_gaaaa(x0) 4.31/2.36 row2colcA_in_gaaa(x0) 4.31/2.36 U7_gaaa(x0, x1, x2) 4.31/2.36 U11_gaaaa(x0, x1, x2) 4.31/2.36 4.31/2.36 We have to consider all (P,Q,R)-chains. 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (17) QDPSizeChangeProof (EQUIVALENT) 4.31/2.36 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. 4.31/2.36 4.31/2.36 From the DPs we obtained the following set of size-change graphs: 4.31/2.36 *U3_GAAAAG(X1, X7, X8, row2colcC_out_gaaaa(X1, X6)) -> PB_IN_GAAAAG(X7, X8) 4.31/2.36 The graph contains the following edges 2 >= 1, 3 >= 2 4.31/2.36 4.31/2.36 4.31/2.36 *PB_IN_GAAAAG(X1, .(X7, X8)) -> U3_GAAAAG(X1, X7, X8, row2colcC_in_gaaaa(X1)) 4.31/2.36 The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 4.31/2.36 4.31/2.36 4.31/2.36 ---------------------------------------- 4.31/2.36 4.31/2.36 (18) 4.31/2.36 YES 4.31/2.40 EOF