3.80/1.75 YES 3.80/1.76 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.80/1.76 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.80/1.76 3.80/1.76 3.80/1.76 Left Termination of the query pattern 3.80/1.76 3.80/1.76 fl(g,a,g) 3.80/1.76 3.80/1.76 w.r.t. the given Prolog program could successfully be proven: 3.80/1.76 3.80/1.76 (0) Prolog 3.80/1.76 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.80/1.76 (2) TRIPLES 3.80/1.76 (3) TriplesToPiDPProof [SOUND, 0 ms] 3.80/1.76 (4) PiDP 3.80/1.76 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.80/1.76 (6) PiDP 3.80/1.76 (7) PiDPToQDPProof [SOUND, 0 ms] 3.80/1.76 (8) QDP 3.80/1.76 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.80/1.76 (10) YES 3.80/1.76 3.80/1.76 3.80/1.76 ---------------------------------------- 3.80/1.76 3.80/1.76 (0) 3.80/1.76 Obligation: 3.80/1.76 Clauses: 3.80/1.76 3.80/1.76 fl([], [], 0). 3.80/1.76 fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). 3.80/1.76 append([], X, X). 3.80/1.76 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 3.80/1.76 3.80/1.76 3.80/1.76 Query: fl(g,a,g) 3.80/1.76 ---------------------------------------- 3.80/1.76 3.80/1.76 (1) PrologToDTProblemTransformerProof (SOUND) 3.80/1.76 Built DT problem from termination graph DT10. 3.80/1.76 3.80/1.76 { 3.80/1.76 "root": 9, 3.80/1.76 "program": { 3.80/1.76 "directives": [], 3.80/1.76 "clauses": [ 3.80/1.76 [ 3.80/1.76 "(fl ([]) ([]) (0))", 3.80/1.76 null 3.80/1.76 ], 3.80/1.76 [ 3.80/1.76 "(fl (. E X) R (s Z))", 3.80/1.76 "(',' (append E Y R) (fl X Y Z))" 3.80/1.76 ], 3.80/1.76 [ 3.80/1.76 "(append ([]) X X)", 3.80/1.76 null 3.80/1.76 ], 3.80/1.76 [ 3.80/1.76 "(append (. X Xs) Ys (. X Zs))", 3.80/1.76 "(append Xs Ys Zs)" 3.80/1.76 ] 3.80/1.76 ] 3.80/1.76 }, 3.80/1.76 "graph": { 3.80/1.76 "nodes": { 3.80/1.76 "191": { 3.80/1.76 "goal": [ 3.80/1.76 { 3.80/1.76 "clause": 2, 3.80/1.76 "scope": 2, 3.80/1.76 "term": "(',' (append T8 X13 T12) (fl T9 X13 T11))" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "clause": 3, 3.80/1.76 "scope": 2, 3.80/1.76 "term": "(',' (append T8 X13 T12) (fl T9 X13 T11))" 3.80/1.76 } 3.80/1.76 ], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T8", 3.80/1.76 "T9", 3.80/1.76 "T11" 3.80/1.76 ], 3.80/1.76 "free": ["X13"], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "type": "Nodes", 3.80/1.76 "150": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": 1, 3.80/1.76 "scope": 1, 3.80/1.76 "term": "(fl ([]) T2 (0))" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "183": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": -1, 3.80/1.76 "scope": -1, 3.80/1.76 "term": "(',' (append T8 X13 T12) (fl T9 X13 T11))" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T8", 3.80/1.76 "T9", 3.80/1.76 "T11" 3.80/1.76 ], 3.80/1.76 "free": ["X13"], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "197": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": 2, 3.80/1.76 "scope": 2, 3.80/1.76 "term": "(',' (append T8 X13 T12) (fl T9 X13 T11))" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T8", 3.80/1.76 "T9", 3.80/1.76 "T11" 3.80/1.76 ], 3.80/1.76 "free": ["X13"], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "187": { 3.80/1.76 "goal": [], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "144": { 3.80/1.76 "goal": [ 3.80/1.76 { 3.80/1.76 "clause": -1, 3.80/1.76 "scope": -1, 3.80/1.76 "term": "(true)" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "clause": 1, 3.80/1.76 "scope": 1, 3.80/1.76 "term": "(fl ([]) T2 (0))" 3.80/1.76 } 3.80/1.76 ], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "155": { 3.80/1.76 "goal": [], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "199": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": 3, 3.80/1.76 "scope": 2, 3.80/1.76 "term": "(',' (append T8 X13 T12) (fl T9 X13 T11))" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T8", 3.80/1.76 "T9", 3.80/1.76 "T11" 3.80/1.76 ], 3.80/1.76 "free": ["X13"], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "145": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": 1, 3.80/1.76 "scope": 1, 3.80/1.76 "term": "(fl T1 T2 T3)" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [[ 3.80/1.76 "(fl T1 T2 T3)", 3.80/1.76 "(fl ([]) ([]) (0))" 3.80/1.76 ]], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T1", 3.80/1.76 "T3" 3.80/1.76 ], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "223": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": -1, 3.80/1.76 "scope": -1, 3.80/1.76 "term": "(',' (append T26 X38 T28) (fl T9 X38 T11))" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T9", 3.80/1.76 "T11", 3.80/1.76 "T26" 3.80/1.76 ], 3.80/1.76 "free": ["X38"], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "202": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": -1, 3.80/1.76 "scope": -1, 3.80/1.76 "term": "(fl T9 T18 T11)" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T9", 3.80/1.76 "T11" 3.80/1.76 ], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "224": { 3.80/1.76 "goal": [], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "203": { 3.80/1.76 "goal": [], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "9": { 3.80/1.76 "goal": [{ 3.80/1.76 "clause": -1, 3.80/1.76 "scope": -1, 3.80/1.76 "term": "(fl T1 T2 T3)" 3.80/1.76 }], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T1", 3.80/1.76 "T3" 3.80/1.76 ], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "10": { 3.80/1.76 "goal": [ 3.80/1.76 { 3.80/1.76 "clause": 0, 3.80/1.76 "scope": 1, 3.80/1.76 "term": "(fl T1 T2 T3)" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "clause": 1, 3.80/1.76 "scope": 1, 3.80/1.76 "term": "(fl T1 T2 T3)" 3.80/1.76 } 3.80/1.76 ], 3.80/1.76 "kb": { 3.80/1.76 "nonunifying": [], 3.80/1.76 "intvars": {}, 3.80/1.76 "arithmetic": { 3.80/1.76 "type": "PlainIntegerRelationState", 3.80/1.76 "relations": [] 3.80/1.76 }, 3.80/1.76 "ground": [ 3.80/1.76 "T1", 3.80/1.76 "T3" 3.80/1.76 ], 3.80/1.76 "free": [], 3.80/1.76 "exprvars": [] 3.80/1.76 } 3.80/1.76 } 3.80/1.76 }, 3.80/1.76 "edges": [ 3.80/1.76 { 3.80/1.76 "from": 9, 3.80/1.76 "to": 10, 3.80/1.76 "label": "CASE" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 10, 3.80/1.76 "to": 144, 3.80/1.76 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 10, 3.80/1.76 "to": 145, 3.80/1.76 "label": "EVAL-BACKTRACK" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 144, 3.80/1.76 "to": 150, 3.80/1.76 "label": "SUCCESS" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 145, 3.80/1.76 "to": 183, 3.80/1.76 "label": "EVAL with clause\nfl(.(X9, X10), X11, s(X12)) :- ','(append(X9, X13, X11), fl(X10, X13, X12)).\nand substitutionX9 -> T8,\nX10 -> T9,\nT1 -> .(T8, T9),\nT2 -> T12,\nX11 -> T12,\nX12 -> T11,\nT3 -> s(T11),\nT10 -> T12" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 145, 3.80/1.76 "to": 187, 3.80/1.76 "label": "EVAL-BACKTRACK" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 150, 3.80/1.76 "to": 155, 3.80/1.76 "label": "BACKTRACK\nfor clause: fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z))because of non-unification" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 183, 3.80/1.76 "to": 191, 3.80/1.76 "label": "CASE" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 191, 3.80/1.76 "to": 197, 3.80/1.76 "label": "PARALLEL" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 191, 3.80/1.76 "to": 199, 3.80/1.76 "label": "PARALLEL" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 197, 3.80/1.76 "to": 202, 3.80/1.76 "label": "EVAL with clause\nappend([], X22, X22).\nand substitutionT8 -> [],\nX13 -> T18,\nX22 -> T18,\nT12 -> T18,\nX23 -> T18,\nT17 -> T18" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 197, 3.80/1.76 "to": 203, 3.80/1.76 "label": "EVAL-BACKTRACK" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 199, 3.80/1.76 "to": 223, 3.80/1.76 "label": "EVAL with clause\nappend(.(X34, X35), X36, .(X34, X37)) :- append(X35, X36, X37).\nand substitutionX34 -> T25,\nX35 -> T26,\nT8 -> .(T25, T26),\nX13 -> X38,\nX36 -> X38,\nX37 -> T28,\nT12 -> .(T25, T28),\nT27 -> T28" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 199, 3.80/1.76 "to": 224, 3.80/1.76 "label": "EVAL-BACKTRACK" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 202, 3.80/1.76 "to": 9, 3.80/1.76 "label": "INSTANCE with matching:\nT1 -> T9\nT2 -> T18\nT3 -> T11" 3.80/1.76 }, 3.80/1.76 { 3.80/1.76 "from": 223, 3.80/1.76 "to": 183, 3.80/1.76 "label": "INSTANCE with matching:\nT8 -> T26\nX13 -> X38\nT12 -> T28" 3.80/1.76 } 3.80/1.76 ], 3.80/1.76 "type": "Graph" 3.80/1.76 } 3.80/1.76 } 3.80/1.76 3.80/1.76 ---------------------------------------- 3.80/1.76 3.80/1.76 (2) 3.80/1.76 Obligation: 3.80/1.76 Triples: 3.80/1.76 3.80/1.76 pB([], X1, X1, X2, X3) :- flA(X2, X1, X3). 3.80/1.76 pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). 3.80/1.76 flA(.(X1, X2), X3, s(X4)) :- pB(X1, X5, X3, X2, X4). 3.80/1.76 3.80/1.76 Clauses: 3.80/1.76 3.80/1.76 flcA([], [], 0). 3.80/1.76 flcA(.(X1, X2), X3, s(X4)) :- qcB(X1, X5, X3, X2, X4). 3.80/1.76 qcB([], X1, X1, X2, X3) :- flcA(X2, X1, X3). 3.80/1.76 qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). 3.80/1.76 3.80/1.76 Afs: 3.80/1.76 3.80/1.76 flA(x1, x2, x3) = flA(x1, x3) 3.80/1.76 3.80/1.76 3.80/1.76 ---------------------------------------- 3.80/1.76 3.80/1.76 (3) TriplesToPiDPProof (SOUND) 3.80/1.76 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.80/1.76 3.80/1.76 flA_in_3: (b,f,b) 3.80/1.76 3.80/1.76 pB_in_5: (b,f,f,b,b) 3.80/1.76 3.80/1.76 Transforming TRIPLES into the following Term Rewriting System: 3.80/1.76 3.80/1.76 Pi DP problem: 3.80/1.76 The TRS P consists of the following rules: 3.80/1.76 3.80/1.76 FLA_IN_GAG(.(X1, X2), X3, s(X4)) -> U3_GAG(X1, X2, X3, X4, pB_in_gaagg(X1, X5, X3, X2, X4)) 3.80/1.76 FLA_IN_GAG(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGG(X1, X5, X3, X2, X4) 3.80/1.76 PB_IN_GAAGG([], X1, X1, X2, X3) -> U1_GAAGG(X1, X2, X3, flA_in_gag(X2, X1, X3)) 3.80/1.76 PB_IN_GAAGG([], X1, X1, X2, X3) -> FLA_IN_GAG(X2, X1, X3) 3.80/1.76 PB_IN_GAAGG(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAAGG(X1, X2, X3, X4, X5, X6, pB_in_gaagg(X2, X3, X4, X5, X6)) 3.80/1.76 PB_IN_GAAGG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGG(X2, X3, X4, X5, X6) 3.80/1.76 3.80/1.76 R is empty. 3.80/1.76 The argument filtering Pi contains the following mapping: 3.80/1.76 flA_in_gag(x1, x2, x3) = flA_in_gag(x1, x3) 3.80/1.76 3.80/1.76 .(x1, x2) = .(x1, x2) 3.80/1.76 3.80/1.76 s(x1) = s(x1) 3.80/1.76 3.80/1.76 pB_in_gaagg(x1, x2, x3, x4, x5) = pB_in_gaagg(x1, x4, x5) 3.80/1.76 3.80/1.76 [] = [] 3.80/1.76 3.80/1.76 FLA_IN_GAG(x1, x2, x3) = FLA_IN_GAG(x1, x3) 3.80/1.76 3.80/1.76 U3_GAG(x1, x2, x3, x4, x5) = U3_GAG(x1, x2, x4, x5) 3.80/1.76 3.80/1.76 PB_IN_GAAGG(x1, x2, x3, x4, x5) = PB_IN_GAAGG(x1, x4, x5) 3.80/1.76 3.80/1.76 U1_GAAGG(x1, x2, x3, x4) = U1_GAAGG(x2, x3, x4) 3.80/1.76 3.80/1.76 U2_GAAGG(x1, x2, x3, x4, x5, x6, x7) = U2_GAAGG(x1, x2, x5, x6, x7) 3.80/1.76 3.80/1.76 3.80/1.76 We have to consider all (P,R,Pi)-chains 3.80/1.76 3.80/1.76 3.80/1.76 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 3.80/1.76 3.80/1.76 3.80/1.76 3.80/1.76 ---------------------------------------- 3.80/1.76 3.80/1.76 (4) 3.80/1.76 Obligation: 3.80/1.76 Pi DP problem: 3.80/1.76 The TRS P consists of the following rules: 3.80/1.76 3.80/1.76 FLA_IN_GAG(.(X1, X2), X3, s(X4)) -> U3_GAG(X1, X2, X3, X4, pB_in_gaagg(X1, X5, X3, X2, X4)) 3.80/1.76 FLA_IN_GAG(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGG(X1, X5, X3, X2, X4) 4.23/1.83 PB_IN_GAAGG([], X1, X1, X2, X3) -> U1_GAAGG(X1, X2, X3, flA_in_gag(X2, X1, X3)) 4.23/1.83 PB_IN_GAAGG([], X1, X1, X2, X3) -> FLA_IN_GAG(X2, X1, X3) 4.23/1.83 PB_IN_GAAGG(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAAGG(X1, X2, X3, X4, X5, X6, pB_in_gaagg(X2, X3, X4, X5, X6)) 4.23/1.83 PB_IN_GAAGG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGG(X2, X3, X4, X5, X6) 4.23/1.83 4.23/1.83 R is empty. 4.23/1.83 The argument filtering Pi contains the following mapping: 4.23/1.83 flA_in_gag(x1, x2, x3) = flA_in_gag(x1, x3) 4.23/1.83 4.23/1.83 .(x1, x2) = .(x1, x2) 4.23/1.83 4.23/1.83 s(x1) = s(x1) 4.23/1.83 4.23/1.83 pB_in_gaagg(x1, x2, x3, x4, x5) = pB_in_gaagg(x1, x4, x5) 4.23/1.83 4.23/1.83 [] = [] 4.23/1.83 4.23/1.83 FLA_IN_GAG(x1, x2, x3) = FLA_IN_GAG(x1, x3) 4.23/1.83 4.23/1.83 U3_GAG(x1, x2, x3, x4, x5) = U3_GAG(x1, x2, x4, x5) 4.23/1.83 4.23/1.83 PB_IN_GAAGG(x1, x2, x3, x4, x5) = PB_IN_GAAGG(x1, x4, x5) 4.23/1.83 4.23/1.83 U1_GAAGG(x1, x2, x3, x4) = U1_GAAGG(x2, x3, x4) 4.23/1.83 4.23/1.83 U2_GAAGG(x1, x2, x3, x4, x5, x6, x7) = U2_GAAGG(x1, x2, x5, x6, x7) 4.23/1.83 4.23/1.83 4.23/1.83 We have to consider all (P,R,Pi)-chains 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (5) DependencyGraphProof (EQUIVALENT) 4.23/1.83 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (6) 4.23/1.83 Obligation: 4.23/1.83 Pi DP problem: 4.23/1.83 The TRS P consists of the following rules: 4.23/1.83 4.23/1.83 FLA_IN_GAG(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGG(X1, X5, X3, X2, X4) 4.23/1.83 PB_IN_GAAGG([], X1, X1, X2, X3) -> FLA_IN_GAG(X2, X1, X3) 4.23/1.83 PB_IN_GAAGG(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGG(X2, X3, X4, X5, X6) 4.23/1.83 4.23/1.83 R is empty. 4.23/1.83 The argument filtering Pi contains the following mapping: 4.23/1.83 .(x1, x2) = .(x1, x2) 4.23/1.83 4.23/1.83 s(x1) = s(x1) 4.23/1.83 4.23/1.83 [] = [] 4.23/1.83 4.23/1.83 FLA_IN_GAG(x1, x2, x3) = FLA_IN_GAG(x1, x3) 4.23/1.83 4.23/1.83 PB_IN_GAAGG(x1, x2, x3, x4, x5) = PB_IN_GAAGG(x1, x4, x5) 4.23/1.83 4.23/1.83 4.23/1.83 We have to consider all (P,R,Pi)-chains 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (7) PiDPToQDPProof (SOUND) 4.23/1.83 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (8) 4.23/1.83 Obligation: 4.23/1.83 Q DP problem: 4.23/1.83 The TRS P consists of the following rules: 4.23/1.83 4.23/1.83 FLA_IN_GAG(.(X1, X2), s(X4)) -> PB_IN_GAAGG(X1, X2, X4) 4.23/1.83 PB_IN_GAAGG([], X2, X3) -> FLA_IN_GAG(X2, X3) 4.23/1.83 PB_IN_GAAGG(.(X1, X2), X5, X6) -> PB_IN_GAAGG(X2, X5, X6) 4.23/1.83 4.23/1.83 R is empty. 4.23/1.83 Q is empty. 4.23/1.83 We have to consider all (P,Q,R)-chains. 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (9) QDPSizeChangeProof (EQUIVALENT) 4.23/1.83 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.23/1.83 4.23/1.83 From the DPs we obtained the following set of size-change graphs: 4.23/1.83 *PB_IN_GAAGG([], X2, X3) -> FLA_IN_GAG(X2, X3) 4.23/1.83 The graph contains the following edges 2 >= 1, 3 >= 2 4.23/1.83 4.23/1.83 4.23/1.83 *PB_IN_GAAGG(.(X1, X2), X5, X6) -> PB_IN_GAAGG(X2, X5, X6) 4.23/1.83 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 4.23/1.83 4.23/1.83 4.23/1.83 *FLA_IN_GAG(.(X1, X2), s(X4)) -> PB_IN_GAAGG(X1, X2, X4) 4.23/1.83 The graph contains the following edges 1 > 1, 1 > 2, 2 > 3 4.23/1.83 4.23/1.83 4.23/1.83 ---------------------------------------- 4.23/1.83 4.23/1.83 (10) 4.23/1.83 YES 4.23/1.87 EOF