4.44/2.05 YES 4.75/2.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.75/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.75/2.07 4.75/2.07 4.75/2.07 Left Termination of the query pattern 4.75/2.07 4.75/2.07 rotate(g,a) 4.75/2.07 4.75/2.07 w.r.t. the given Prolog program could successfully be proven: 4.75/2.07 4.75/2.07 (0) Prolog 4.75/2.07 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 4.75/2.07 (2) TRIPLES 4.75/2.07 (3) TriplesToPiDPProof [SOUND, 0 ms] 4.75/2.07 (4) PiDP 4.75/2.07 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.75/2.07 (6) AND 4.75/2.07 (7) PiDP 4.75/2.07 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.75/2.07 (9) PiDP 4.75/2.07 (10) PiDPToQDPProof [SOUND, 0 ms] 4.75/2.07 (11) QDP 4.75/2.07 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.75/2.07 (13) YES 4.75/2.07 (14) PiDP 4.75/2.07 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.75/2.07 (16) PiDP 4.75/2.07 (17) PiDPToQDPProof [SOUND, 0 ms] 4.75/2.07 (18) QDP 4.75/2.07 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.75/2.07 (20) YES 4.75/2.07 (21) PiDP 4.75/2.07 (22) UsableRulesProof [EQUIVALENT, 0 ms] 4.75/2.07 (23) PiDP 4.75/2.07 (24) PiDPToQDPProof [SOUND, 0 ms] 4.75/2.07 (25) QDP 4.75/2.07 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.75/2.07 (27) YES 4.75/2.07 4.75/2.07 4.75/2.07 ---------------------------------------- 4.75/2.07 4.75/2.07 (0) 4.75/2.07 Obligation: 4.75/2.07 Clauses: 4.75/2.07 4.75/2.07 rotate(X, Y) :- ','(append(A, B, X), append(B, A, Y)). 4.75/2.07 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 4.75/2.07 append([], Ys, Ys). 4.75/2.07 4.75/2.07 4.75/2.07 Query: rotate(g,a) 4.75/2.07 ---------------------------------------- 4.75/2.07 4.75/2.07 (1) PrologToDTProblemTransformerProof (SOUND) 4.75/2.07 Built DT problem from termination graph DT10. 4.75/2.07 4.75/2.07 { 4.75/2.07 "root": 106, 4.75/2.07 "program": { 4.75/2.07 "directives": [], 4.75/2.07 "clauses": [ 4.75/2.07 [ 4.75/2.07 "(rotate X Y)", 4.75/2.07 "(',' (append A B X) (append B A Y))" 4.75/2.07 ], 4.75/2.07 [ 4.75/2.07 "(append (. X Xs) Ys (. X Zs))", 4.75/2.07 "(append Xs Ys Zs)" 4.75/2.07 ], 4.75/2.07 [ 4.75/2.07 "(append ([]) Ys Ys)", 4.75/2.07 null 4.75/2.07 ] 4.75/2.07 ] 4.75/2.07 }, 4.75/2.07 "graph": { 4.75/2.07 "nodes": { 4.75/2.07 "170": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": -1, 4.75/2.07 "scope": -1, 4.75/2.07 "term": "(append X89 X90 T33)" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": ["T33"], 4.75/2.07 "free": [ 4.75/2.07 "X89", 4.75/2.07 "X90" 4.75/2.07 ], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "192": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": -1, 4.75/2.07 "scope": -1, 4.75/2.07 "term": "(true)" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "171": { 4.75/2.07 "goal": [], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "193": { 4.75/2.07 "goal": [], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "type": "Nodes", 4.75/2.07 "194": { 4.75/2.07 "goal": [], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "195": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": -1, 4.75/2.07 "scope": -1, 4.75/2.07 "term": "(append T86 ([]) T7)" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": ["T86"], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "130": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": 2, 4.75/2.07 "scope": 2, 4.75/2.07 "term": "(',' (append X5 X6 T5) (append X6 X5 T7))" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": ["T5"], 4.75/2.07 "free": [ 4.75/2.07 "X5", 4.75/2.07 "X6" 4.75/2.07 ], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "131": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": -1, 4.75/2.07 "scope": -1, 4.75/2.07 "term": "(',' (append X40 X41 T17) (append X41 (. T16 X40) T7))" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [ 4.75/2.07 "T16", 4.75/2.07 "T17" 4.75/2.07 ], 4.75/2.07 "free": [ 4.75/2.07 "X40", 4.75/2.07 "X41" 4.75/2.07 ], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "175": { 4.75/2.07 "goal": [{ 4.75/2.07 "clause": -1, 4.75/2.07 "scope": -1, 4.75/2.07 "term": "(true)" 4.75/2.07 }], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.07 "intvars": {}, 4.75/2.07 "arithmetic": { 4.75/2.07 "type": "PlainIntegerRelationState", 4.75/2.07 "relations": [] 4.75/2.07 }, 4.75/2.07 "ground": [], 4.75/2.07 "free": [], 4.75/2.07 "exprvars": [] 4.75/2.07 } 4.75/2.07 }, 4.75/2.07 "132": { 4.75/2.07 "goal": [], 4.75/2.07 "kb": { 4.75/2.07 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "176": { 4.75/2.08 "goal": [], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "135": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(append X40 X41 T17)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T17"], 4.75/2.08 "free": [ 4.75/2.08 "X40", 4.75/2.08 "X41" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "179": { 4.75/2.08 "goal": [ 4.75/2.08 { 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 4, 4.75/2.08 "term": "(append T21 (. T16 T20) T7)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 4, 4.75/2.08 "term": "(append T21 (. T16 T20) T7)" 4.75/2.08 } 4.75/2.08 ], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [ 4.75/2.08 "T16", 4.75/2.08 "T20", 4.75/2.08 "T21" 4.75/2.08 ], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "212": { 4.75/2.08 "goal": [ 4.75/2.08 { 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 5, 4.75/2.08 "term": "(append T86 ([]) T7)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 5, 4.75/2.08 "term": "(append T86 ([]) T7)" 4.75/2.08 } 4.75/2.08 ], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T86"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "136": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(append T21 (. T16 T20) T7)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [ 4.75/2.08 "T16", 4.75/2.08 "T20", 4.75/2.08 "T21" 4.75/2.08 ], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "213": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 5, 4.75/2.08 "term": "(append T86 ([]) T7)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T86"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "137": { 4.75/2.08 "goal": [ 4.75/2.08 { 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 3, 4.75/2.08 "term": "(append X40 X41 T17)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 3, 4.75/2.08 "term": "(append X40 X41 T17)" 4.75/2.08 } 4.75/2.08 ], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T17"], 4.75/2.08 "free": [ 4.75/2.08 "X40", 4.75/2.08 "X41" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "214": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 5, 4.75/2.08 "term": "(append T86 ([]) T7)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T86"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "215": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(append T103 ([]) T105)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T103"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "216": { 4.75/2.08 "goal": [], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "217": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(true)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "218": { 4.75/2.08 "goal": [], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "219": { 4.75/2.08 "goal": [], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "180": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 4, 4.75/2.08 "term": "(append T21 (. T16 T20) T7)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [ 4.75/2.08 "T16", 4.75/2.08 "T20", 4.75/2.08 "T21" 4.75/2.08 ], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "181": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 4, 4.75/2.08 "term": "(append T21 (. T16 T20) T7)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [ 4.75/2.08 "T16", 4.75/2.08 "T20", 4.75/2.08 "T21" 4.75/2.08 ], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "187": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(append T65 (. T66 T67) T69)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [ 4.75/2.08 "T65", 4.75/2.08 "T66", 4.75/2.08 "T67" 4.75/2.08 ], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "188": { 4.75/2.08 "goal": [], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": [], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "168": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 3, 4.75/2.08 "term": "(append X40 X41 T17)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T17"], 4.75/2.08 "free": [ 4.75/2.08 "X40", 4.75/2.08 "X41" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "169": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 3, 4.75/2.08 "term": "(append X40 X41 T17)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T17"], 4.75/2.08 "free": [ 4.75/2.08 "X40", 4.75/2.08 "X41" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "126": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 0, 4.75/2.08 "scope": 1, 4.75/2.08 "term": "(rotate T1 T2)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T1"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "127": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(',' (append X5 X6 T5) (append X6 X5 T7))" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T5"], 4.75/2.08 "free": [ 4.75/2.08 "X5", 4.75/2.08 "X6" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "106": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": -1, 4.75/2.08 "scope": -1, 4.75/2.08 "term": "(rotate T1 T2)" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T1"], 4.75/2.08 "free": [], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "128": { 4.75/2.08 "goal": [ 4.75/2.08 { 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 2, 4.75/2.08 "term": "(',' (append X5 X6 T5) (append X6 X5 T7))" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "clause": 2, 4.75/2.08 "scope": 2, 4.75/2.08 "term": "(',' (append X5 X6 T5) (append X6 X5 T7))" 4.75/2.08 } 4.75/2.08 ], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T5"], 4.75/2.08 "free": [ 4.75/2.08 "X5", 4.75/2.08 "X6" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "129": { 4.75/2.08 "goal": [{ 4.75/2.08 "clause": 1, 4.75/2.08 "scope": 2, 4.75/2.08 "term": "(',' (append X5 X6 T5) (append X6 X5 T7))" 4.75/2.08 }], 4.75/2.08 "kb": { 4.75/2.08 "nonunifying": [], 4.75/2.08 "intvars": {}, 4.75/2.08 "arithmetic": { 4.75/2.08 "type": "PlainIntegerRelationState", 4.75/2.08 "relations": [] 4.75/2.08 }, 4.75/2.08 "ground": ["T5"], 4.75/2.08 "free": [ 4.75/2.08 "X5", 4.75/2.08 "X6" 4.75/2.08 ], 4.75/2.08 "exprvars": [] 4.75/2.08 } 4.75/2.08 } 4.75/2.08 }, 4.75/2.08 "edges": [ 4.75/2.08 { 4.75/2.08 "from": 106, 4.75/2.08 "to": 126, 4.75/2.08 "label": "CASE" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 126, 4.75/2.08 "to": 127, 4.75/2.08 "label": "ONLY EVAL with clause\nrotate(X3, X4) :- ','(append(X5, X6, X3), append(X6, X5, X4)).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> T7,\nX4 -> T7,\nT6 -> T7" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 127, 4.75/2.08 "to": 128, 4.75/2.08 "label": "CASE" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 128, 4.75/2.08 "to": 129, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 128, 4.75/2.08 "to": 130, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 129, 4.75/2.08 "to": 131, 4.75/2.08 "label": "EVAL with clause\nappend(.(X35, X36), X37, .(X35, X38)) :- append(X36, X37, X38).\nand substitutionX35 -> T16,\nX36 -> X40,\nX5 -> .(T16, X40),\nX6 -> X41,\nX37 -> X41,\nX39 -> T16,\nX38 -> T17,\nT5 -> .(T16, T17)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 129, 4.75/2.08 "to": 132, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 130, 4.75/2.08 "to": 195, 4.75/2.08 "label": "ONLY EVAL with clause\nappend([], X143, X143).\nand substitutionX5 -> [],\nX6 -> T86,\nX143 -> T86,\nT5 -> T86,\nX144 -> T86" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 131, 4.75/2.08 "to": 135, 4.75/2.08 "label": "SPLIT 1" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 131, 4.75/2.08 "to": 136, 4.75/2.08 "label": "SPLIT 2\nnew knowledge:\nT20 is ground\nT21 is ground\nT17 is ground\nreplacements:X40 -> T20,\nX41 -> T21" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 135, 4.75/2.08 "to": 137, 4.75/2.08 "label": "CASE" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 136, 4.75/2.08 "to": 179, 4.75/2.08 "label": "CASE" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 137, 4.75/2.08 "to": 168, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 137, 4.75/2.08 "to": 169, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 168, 4.75/2.08 "to": 170, 4.75/2.08 "label": "EVAL with clause\nappend(.(X84, X85), X86, .(X84, X87)) :- append(X85, X86, X87).\nand substitutionX84 -> T32,\nX85 -> X89,\nX40 -> .(T32, X89),\nX41 -> X90,\nX86 -> X90,\nX88 -> T32,\nX87 -> T33,\nT17 -> .(T32, T33)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 168, 4.75/2.08 "to": 171, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 169, 4.75/2.08 "to": 175, 4.75/2.08 "label": "ONLY EVAL with clause\nappend([], X102, X102).\nand substitutionX40 -> [],\nX41 -> T38,\nX102 -> T38,\nT17 -> T38,\nX103 -> T38" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 170, 4.75/2.08 "to": 135, 4.75/2.08 "label": "INSTANCE with matching:\nX40 -> X89\nX41 -> X90\nT17 -> T33" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 175, 4.75/2.08 "to": 176, 4.75/2.08 "label": "SUCCESS" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 179, 4.75/2.08 "to": 180, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 179, 4.75/2.08 "to": 181, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 180, 4.75/2.08 "to": 187, 4.75/2.08 "label": "EVAL with clause\nappend(.(X124, X125), X126, .(X124, X127)) :- append(X125, X126, X127).\nand substitutionX124 -> T64,\nX125 -> T65,\nT21 -> .(T64, T65),\nT16 -> T66,\nT20 -> T67,\nX126 -> .(T66, T67),\nX127 -> T69,\nT7 -> .(T64, T69),\nT68 -> T69" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 180, 4.75/2.08 "to": 188, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 181, 4.75/2.08 "to": 192, 4.75/2.08 "label": "EVAL with clause\nappend([], X134, X134).\nand substitutionT21 -> [],\nT16 -> T79,\nT20 -> T80,\nX134 -> .(T79, T80),\nT7 -> .(T79, T80)" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 181, 4.75/2.08 "to": 193, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 187, 4.75/2.08 "to": 136, 4.75/2.08 "label": "INSTANCE with matching:\nT21 -> T65\nT16 -> T66\nT20 -> T67\nT7 -> T69" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 192, 4.75/2.08 "to": 194, 4.75/2.08 "label": "SUCCESS" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 195, 4.75/2.08 "to": 212, 4.75/2.08 "label": "CASE" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 212, 4.75/2.08 "to": 213, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 212, 4.75/2.08 "to": 214, 4.75/2.08 "label": "PARALLEL" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 213, 4.75/2.08 "to": 215, 4.75/2.08 "label": "EVAL with clause\nappend(.(X165, X166), X167, .(X165, X168)) :- append(X166, X167, X168).\nand substitutionX165 -> T102,\nX166 -> T103,\nT86 -> .(T102, T103),\nX167 -> [],\nX168 -> T105,\nT7 -> .(T102, T105),\nT104 -> T105" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 213, 4.75/2.08 "to": 216, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 214, 4.75/2.08 "to": 217, 4.75/2.08 "label": "EVAL with clause\nappend([], X175, X175).\nand substitutionT86 -> [],\nX175 -> [],\nT7 -> []" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 214, 4.75/2.08 "to": 218, 4.75/2.08 "label": "EVAL-BACKTRACK" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 215, 4.75/2.08 "to": 195, 4.75/2.08 "label": "INSTANCE with matching:\nT86 -> T103\nT7 -> T105" 4.75/2.08 }, 4.75/2.08 { 4.75/2.08 "from": 217, 4.75/2.08 "to": 219, 4.75/2.08 "label": "SUCCESS" 4.75/2.08 } 4.75/2.08 ], 4.75/2.08 "type": "Graph" 4.75/2.08 } 4.75/2.08 } 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (2) 4.75/2.08 Obligation: 4.75/2.08 Triples: 4.75/2.08 4.75/2.08 appendA(.(X1, X2), X3, .(X1, X4)) :- appendA(X2, X3, X4). 4.75/2.08 appendB(.(X1, X2), X3, X4, .(X1, X5)) :- appendB(X2, X3, X4, X5). 4.75/2.08 appendC(.(X1, X2), .(X1, X3)) :- appendC(X2, X3). 4.75/2.08 rotateD(.(X1, X2), X3) :- appendA(X4, X5, X2). 4.75/2.08 rotateD(.(X1, X2), X3) :- ','(appendcA(X4, X5, X2), appendB(X5, X1, X4, X3)). 4.75/2.08 rotateD(X1, X2) :- appendC(X1, X2). 4.75/2.08 4.75/2.08 Clauses: 4.75/2.08 4.75/2.08 appendcA(.(X1, X2), X3, .(X1, X4)) :- appendcA(X2, X3, X4). 4.75/2.08 appendcA([], X1, X1). 4.75/2.08 appendcB(.(X1, X2), X3, X4, .(X1, X5)) :- appendcB(X2, X3, X4, X5). 4.75/2.08 appendcB([], X1, X2, .(X1, X2)). 4.75/2.08 appendcC(.(X1, X2), .(X1, X3)) :- appendcC(X2, X3). 4.75/2.08 appendcC([], []). 4.75/2.08 4.75/2.08 Afs: 4.75/2.08 4.75/2.08 rotateD(x1, x2) = rotateD(x1) 4.75/2.08 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (3) TriplesToPiDPProof (SOUND) 4.75/2.08 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.75/2.08 4.75/2.08 rotateD_in_2: (b,f) 4.75/2.08 4.75/2.08 appendA_in_3: (f,f,b) 4.75/2.08 4.75/2.08 appendcA_in_3: (f,f,b) 4.75/2.08 4.75/2.08 appendB_in_4: (b,b,b,f) 4.75/2.08 4.75/2.08 appendC_in_2: (b,f) 4.75/2.08 4.75/2.08 Transforming TRIPLES into the following Term Rewriting System: 4.75/2.08 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> U4_GA(X1, X2, X3, appendA_in_aag(X4, X5, X2)) 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> APPENDA_IN_AAG(X4, X5, X2) 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> U5_GA(X1, X2, X3, appendcA_in_aag(X4, X5, X2)) 4.75/2.08 U5_GA(X1, X2, X3, appendcA_out_aag(X4, X5, X2)) -> U6_GA(X1, X2, X3, appendB_in_ggga(X5, X1, X4, X3)) 4.75/2.08 U5_GA(X1, X2, X3, appendcA_out_aag(X4, X5, X2)) -> APPENDB_IN_GGGA(X5, X1, X4, X3) 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> U2_GGGA(X1, X2, X3, X4, X5, appendB_in_ggga(X2, X3, X4, X5)) 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPENDB_IN_GGGA(X2, X3, X4, X5) 4.75/2.08 ROTATED_IN_GA(X1, X2) -> U7_GA(X1, X2, appendC_in_ga(X1, X2)) 4.75/2.08 ROTATED_IN_GA(X1, X2) -> APPENDC_IN_GA(X1, X2) 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> U3_GA(X1, X2, X3, appendC_in_ga(X2, X3)) 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> APPENDC_IN_GA(X2, X3) 4.75/2.08 4.75/2.08 The TRS R consists of the following rules: 4.75/2.08 4.75/2.08 appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U9_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) 4.75/2.08 appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) 4.75/2.08 U9_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) 4.75/2.08 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) 4.75/2.08 4.75/2.08 appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) 4.75/2.08 4.75/2.08 U9_aag(x1, x2, x3, x4, x5) = U9_aag(x1, x4, x5) 4.75/2.08 4.75/2.08 appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) 4.75/2.08 4.75/2.08 appendB_in_ggga(x1, x2, x3, x4) = appendB_in_ggga(x1, x2, x3) 4.75/2.08 4.75/2.08 appendC_in_ga(x1, x2) = appendC_in_ga(x1) 4.75/2.08 4.75/2.08 ROTATED_IN_GA(x1, x2) = ROTATED_IN_GA(x1) 4.75/2.08 4.75/2.08 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 4.75/2.08 4.75/2.08 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) 4.75/2.08 4.75/2.08 U5_GA(x1, x2, x3, x4) = U5_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(x1, x2, x3, x4) = APPENDB_IN_GGGA(x1, x2, x3) 4.75/2.08 4.75/2.08 U2_GGGA(x1, x2, x3, x4, x5, x6) = U2_GGGA(x1, x2, x3, x4, x6) 4.75/2.08 4.75/2.08 U7_GA(x1, x2, x3) = U7_GA(x1, x3) 4.75/2.08 4.75/2.08 APPENDC_IN_GA(x1, x2) = APPENDC_IN_GA(x1) 4.75/2.08 4.75/2.08 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 4.75/2.08 4.75/2.08 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 4.75/2.08 4.75/2.08 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (4) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> U4_GA(X1, X2, X3, appendA_in_aag(X4, X5, X2)) 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> APPENDA_IN_AAG(X4, X5, X2) 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 4.75/2.08 ROTATED_IN_GA(.(X1, X2), X3) -> U5_GA(X1, X2, X3, appendcA_in_aag(X4, X5, X2)) 4.75/2.08 U5_GA(X1, X2, X3, appendcA_out_aag(X4, X5, X2)) -> U6_GA(X1, X2, X3, appendB_in_ggga(X5, X1, X4, X3)) 4.75/2.08 U5_GA(X1, X2, X3, appendcA_out_aag(X4, X5, X2)) -> APPENDB_IN_GGGA(X5, X1, X4, X3) 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> U2_GGGA(X1, X2, X3, X4, X5, appendB_in_ggga(X2, X3, X4, X5)) 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPENDB_IN_GGGA(X2, X3, X4, X5) 4.75/2.08 ROTATED_IN_GA(X1, X2) -> U7_GA(X1, X2, appendC_in_ga(X1, X2)) 4.75/2.08 ROTATED_IN_GA(X1, X2) -> APPENDC_IN_GA(X1, X2) 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> U3_GA(X1, X2, X3, appendC_in_ga(X2, X3)) 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> APPENDC_IN_GA(X2, X3) 4.75/2.08 4.75/2.08 The TRS R consists of the following rules: 4.75/2.08 4.75/2.08 appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U9_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) 4.75/2.08 appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) 4.75/2.08 U9_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) 4.75/2.08 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) 4.75/2.08 4.75/2.08 appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) 4.75/2.08 4.75/2.08 U9_aag(x1, x2, x3, x4, x5) = U9_aag(x1, x4, x5) 4.75/2.08 4.75/2.08 appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) 4.75/2.08 4.75/2.08 appendB_in_ggga(x1, x2, x3, x4) = appendB_in_ggga(x1, x2, x3) 4.75/2.08 4.75/2.08 appendC_in_ga(x1, x2) = appendC_in_ga(x1) 4.75/2.08 4.75/2.08 ROTATED_IN_GA(x1, x2) = ROTATED_IN_GA(x1) 4.75/2.08 4.75/2.08 U4_GA(x1, x2, x3, x4) = U4_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 4.75/2.08 4.75/2.08 U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) 4.75/2.08 4.75/2.08 U5_GA(x1, x2, x3, x4) = U5_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 U6_GA(x1, x2, x3, x4) = U6_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(x1, x2, x3, x4) = APPENDB_IN_GGGA(x1, x2, x3) 4.75/2.08 4.75/2.08 U2_GGGA(x1, x2, x3, x4, x5, x6) = U2_GGGA(x1, x2, x3, x4, x6) 4.75/2.08 4.75/2.08 U7_GA(x1, x2, x3) = U7_GA(x1, x3) 4.75/2.08 4.75/2.08 APPENDC_IN_GA(x1, x2) = APPENDC_IN_GA(x1) 4.75/2.08 4.75/2.08 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (5) DependencyGraphProof (EQUIVALENT) 4.75/2.08 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 10 less nodes. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (6) 4.75/2.08 Complex Obligation (AND) 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (7) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> APPENDC_IN_GA(X2, X3) 4.75/2.08 4.75/2.08 The TRS R consists of the following rules: 4.75/2.08 4.75/2.08 appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U9_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) 4.75/2.08 appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) 4.75/2.08 U9_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) 4.75/2.08 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) 4.75/2.08 4.75/2.08 U9_aag(x1, x2, x3, x4, x5) = U9_aag(x1, x4, x5) 4.75/2.08 4.75/2.08 appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) 4.75/2.08 4.75/2.08 APPENDC_IN_GA(x1, x2) = APPENDC_IN_GA(x1) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (8) UsableRulesProof (EQUIVALENT) 4.75/2.08 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (9) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDC_IN_GA(.(X1, X2), .(X1, X3)) -> APPENDC_IN_GA(X2, X3) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 APPENDC_IN_GA(x1, x2) = APPENDC_IN_GA(x1) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (10) PiDPToQDPProof (SOUND) 4.75/2.08 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (11) 4.75/2.08 Obligation: 4.75/2.08 Q DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDC_IN_GA(.(X1, X2)) -> APPENDC_IN_GA(X2) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 Q is empty. 4.75/2.08 We have to consider all (P,Q,R)-chains. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (12) QDPSizeChangeProof (EQUIVALENT) 4.75/2.08 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.75/2.08 4.75/2.08 From the DPs we obtained the following set of size-change graphs: 4.75/2.08 *APPENDC_IN_GA(.(X1, X2)) -> APPENDC_IN_GA(X2) 4.75/2.08 The graph contains the following edges 1 > 1 4.75/2.08 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (13) 4.75/2.08 YES 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (14) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPENDB_IN_GGGA(X2, X3, X4, X5) 4.75/2.08 4.75/2.08 The TRS R consists of the following rules: 4.75/2.08 4.75/2.08 appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U9_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) 4.75/2.08 appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) 4.75/2.08 U9_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) 4.75/2.08 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) 4.75/2.08 4.75/2.08 U9_aag(x1, x2, x3, x4, x5) = U9_aag(x1, x4, x5) 4.75/2.08 4.75/2.08 appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(x1, x2, x3, x4) = APPENDB_IN_GGGA(x1, x2, x3) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (15) UsableRulesProof (EQUIVALENT) 4.75/2.08 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (16) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4, .(X1, X5)) -> APPENDB_IN_GGGA(X2, X3, X4, X5) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(x1, x2, x3, x4) = APPENDB_IN_GGGA(x1, x2, x3) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (17) PiDPToQDPProof (SOUND) 4.75/2.08 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (18) 4.75/2.08 Obligation: 4.75/2.08 Q DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDB_IN_GGGA(.(X1, X2), X3, X4) -> APPENDB_IN_GGGA(X2, X3, X4) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 Q is empty. 4.75/2.08 We have to consider all (P,Q,R)-chains. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (19) QDPSizeChangeProof (EQUIVALENT) 4.75/2.08 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.75/2.08 4.75/2.08 From the DPs we obtained the following set of size-change graphs: 4.75/2.08 *APPENDB_IN_GGGA(.(X1, X2), X3, X4) -> APPENDB_IN_GGGA(X2, X3, X4) 4.75/2.08 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 4.75/2.08 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (20) 4.75/2.08 YES 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (21) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 4.75/2.08 4.75/2.08 The TRS R consists of the following rules: 4.75/2.08 4.75/2.08 appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U9_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) 4.75/2.08 appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) 4.75/2.08 U9_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) 4.75/2.08 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) 4.75/2.08 4.75/2.08 U9_aag(x1, x2, x3, x4, x5) = U9_aag(x1, x4, x5) 4.75/2.08 4.75/2.08 appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (22) UsableRulesProof (EQUIVALENT) 4.75/2.08 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (23) 4.75/2.08 Obligation: 4.75/2.08 Pi DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 The argument filtering Pi contains the following mapping: 4.75/2.08 .(x1, x2) = .(x1, x2) 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) 4.75/2.08 4.75/2.08 4.75/2.08 We have to consider all (P,R,Pi)-chains 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (24) PiDPToQDPProof (SOUND) 4.75/2.08 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (25) 4.75/2.08 Obligation: 4.75/2.08 Q DP problem: 4.75/2.08 The TRS P consists of the following rules: 4.75/2.08 4.75/2.08 APPENDA_IN_AAG(.(X1, X4)) -> APPENDA_IN_AAG(X4) 4.75/2.08 4.75/2.08 R is empty. 4.75/2.08 Q is empty. 4.75/2.08 We have to consider all (P,Q,R)-chains. 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (26) QDPSizeChangeProof (EQUIVALENT) 4.75/2.08 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.75/2.08 4.75/2.08 From the DPs we obtained the following set of size-change graphs: 4.75/2.08 *APPENDA_IN_AAG(.(X1, X4)) -> APPENDA_IN_AAG(X4) 4.75/2.08 The graph contains the following edges 1 > 1 4.75/2.08 4.75/2.08 4.75/2.08 ---------------------------------------- 4.75/2.08 4.75/2.08 (27) 4.75/2.08 YES 4.75/2.11 EOF