4.01/1.86 YES 4.01/1.88 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.01/1.88 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.01/1.88 4.01/1.88 4.01/1.88 Left Termination of the query pattern 4.01/1.88 4.01/1.88 fl(g,g,a) 4.01/1.88 4.01/1.88 w.r.t. the given Prolog program could successfully be proven: 4.01/1.88 4.01/1.88 (0) Prolog 4.01/1.88 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 4.01/1.88 (2) TRIPLES 4.01/1.88 (3) TriplesToPiDPProof [SOUND, 0 ms] 4.01/1.88 (4) PiDP 4.01/1.88 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.01/1.88 (6) PiDP 4.01/1.88 (7) PiDPToQDPProof [SOUND, 0 ms] 4.01/1.88 (8) QDP 4.01/1.88 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.01/1.88 (10) YES 4.01/1.88 4.01/1.88 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (0) 4.01/1.88 Obligation: 4.01/1.88 Clauses: 4.01/1.88 4.01/1.88 fl([], [], 0). 4.01/1.88 fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). 4.01/1.88 append([], X, X). 4.01/1.88 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 4.01/1.88 4.01/1.88 4.01/1.88 Query: fl(g,g,a) 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (1) PrologToDTProblemTransformerProof (SOUND) 4.01/1.88 Built DT problem from termination graph DT10. 4.01/1.88 4.01/1.88 { 4.01/1.88 "root": 1, 4.01/1.88 "program": { 4.01/1.88 "directives": [], 4.01/1.88 "clauses": [ 4.01/1.88 [ 4.01/1.88 "(fl ([]) ([]) (0))", 4.01/1.88 null 4.01/1.88 ], 4.01/1.88 [ 4.01/1.88 "(fl (. E X) R (s Z))", 4.01/1.88 "(',' (append E Y R) (fl X Y Z))" 4.01/1.88 ], 4.01/1.88 [ 4.01/1.88 "(append ([]) X X)", 4.01/1.88 null 4.01/1.88 ], 4.01/1.88 [ 4.01/1.88 "(append (. X Xs) Ys (. X Zs))", 4.01/1.88 "(append Xs Ys Zs)" 4.01/1.88 ] 4.01/1.88 ] 4.01/1.88 }, 4.01/1.88 "graph": { 4.01/1.88 "nodes": { 4.01/1.88 "190": { 4.01/1.88 "goal": [], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "180": { 4.01/1.88 "goal": [], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "182": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": -1, 4.01/1.88 "scope": -1, 4.01/1.88 "term": "(',' (append T8 X13 T10) (fl T9 X13 T12))" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T8", 4.01/1.88 "T9", 4.01/1.88 "T10" 4.01/1.88 ], 4.01/1.88 "free": ["X13"], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "type": "Nodes", 4.01/1.88 "151": { 4.01/1.88 "goal": [ 4.01/1.88 { 4.01/1.88 "clause": 0, 4.01/1.88 "scope": 1, 4.01/1.88 "term": "(fl T1 T2 T3)" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "clause": 1, 4.01/1.88 "scope": 1, 4.01/1.88 "term": "(fl T1 T2 T3)" 4.01/1.88 } 4.01/1.88 ], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T1", 4.01/1.88 "T2" 4.01/1.88 ], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "184": { 4.01/1.88 "goal": [], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "185": { 4.01/1.88 "goal": [ 4.01/1.88 { 4.01/1.88 "clause": 2, 4.01/1.88 "scope": 2, 4.01/1.88 "term": "(',' (append T8 X13 T10) (fl T9 X13 T12))" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "clause": 3, 4.01/1.88 "scope": 2, 4.01/1.88 "term": "(',' (append T8 X13 T10) (fl T9 X13 T12))" 4.01/1.88 } 4.01/1.88 ], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T8", 4.01/1.88 "T9", 4.01/1.88 "T10" 4.01/1.88 ], 4.01/1.88 "free": ["X13"], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "186": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": 2, 4.01/1.88 "scope": 2, 4.01/1.88 "term": "(',' (append T8 X13 T10) (fl T9 X13 T12))" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T8", 4.01/1.88 "T9", 4.01/1.88 "T10" 4.01/1.88 ], 4.01/1.88 "free": ["X13"], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "187": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": 3, 4.01/1.88 "scope": 2, 4.01/1.88 "term": "(',' (append T8 X13 T10) (fl T9 X13 T12))" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T8", 4.01/1.88 "T9", 4.01/1.88 "T10" 4.01/1.88 ], 4.01/1.88 "free": ["X13"], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "1": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": -1, 4.01/1.88 "scope": -1, 4.01/1.88 "term": "(fl T1 T2 T3)" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T1", 4.01/1.88 "T2" 4.01/1.88 ], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "177": { 4.01/1.88 "goal": [ 4.01/1.88 { 4.01/1.88 "clause": -1, 4.01/1.88 "scope": -1, 4.01/1.88 "term": "(true)" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "clause": 1, 4.01/1.88 "scope": 1, 4.01/1.88 "term": "(fl ([]) ([]) T3)" 4.01/1.88 } 4.01/1.88 ], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "178": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": 1, 4.01/1.88 "scope": 1, 4.01/1.88 "term": "(fl T1 T2 T3)" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [[ 4.01/1.88 "(fl T1 T2 T3)", 4.01/1.88 "(fl ([]) ([]) (0))" 4.01/1.88 ]], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T1", 4.01/1.88 "T2" 4.01/1.88 ], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "189": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": -1, 4.01/1.88 "scope": -1, 4.01/1.88 "term": "(fl T9 T17 T12)" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T9", 4.01/1.88 "T17" 4.01/1.88 ], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "179": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": 1, 4.01/1.88 "scope": 1, 4.01/1.88 "term": "(fl ([]) ([]) T3)" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "225": { 4.01/1.88 "goal": [{ 4.01/1.88 "clause": -1, 4.01/1.88 "scope": -1, 4.01/1.88 "term": "(',' (append T25 X38 T26) (fl T9 X38 T12))" 4.01/1.88 }], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [ 4.01/1.88 "T9", 4.01/1.88 "T25", 4.01/1.88 "T26" 4.01/1.88 ], 4.01/1.88 "free": ["X38"], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "226": { 4.01/1.88 "goal": [], 4.01/1.88 "kb": { 4.01/1.88 "nonunifying": [], 4.01/1.88 "intvars": {}, 4.01/1.88 "arithmetic": { 4.01/1.88 "type": "PlainIntegerRelationState", 4.01/1.88 "relations": [] 4.01/1.88 }, 4.01/1.88 "ground": [], 4.01/1.88 "free": [], 4.01/1.88 "exprvars": [] 4.01/1.88 } 4.01/1.88 } 4.01/1.88 }, 4.01/1.88 "edges": [ 4.01/1.88 { 4.01/1.88 "from": 1, 4.01/1.88 "to": 151, 4.01/1.88 "label": "CASE" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 151, 4.01/1.88 "to": 177, 4.01/1.88 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 151, 4.01/1.88 "to": 178, 4.01/1.88 "label": "EVAL-BACKTRACK" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 177, 4.01/1.88 "to": 179, 4.01/1.88 "label": "SUCCESS" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 178, 4.01/1.88 "to": 182, 4.01/1.88 "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 -> T10,\nX11 -> T10,\nX12 -> T12,\nT3 -> s(T12),\nT11 -> T12" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 178, 4.01/1.88 "to": 184, 4.01/1.88 "label": "EVAL-BACKTRACK" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 179, 4.01/1.88 "to": 180, 4.01/1.88 "label": "BACKTRACK\nfor clause: fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z))because of non-unification" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 182, 4.01/1.88 "to": 185, 4.01/1.88 "label": "CASE" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 185, 4.01/1.88 "to": 186, 4.01/1.88 "label": "PARALLEL" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 185, 4.01/1.88 "to": 187, 4.01/1.88 "label": "PARALLEL" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 186, 4.01/1.88 "to": 189, 4.01/1.88 "label": "EVAL with clause\nappend([], X22, X22).\nand substitutionT8 -> [],\nX13 -> T17,\nX22 -> T17,\nT10 -> T17,\nX23 -> T17" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 186, 4.01/1.88 "to": 190, 4.01/1.88 "label": "EVAL-BACKTRACK" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 187, 4.01/1.88 "to": 225, 4.01/1.88 "label": "EVAL with clause\nappend(.(X34, X35), X36, .(X34, X37)) :- append(X35, X36, X37).\nand substitutionX34 -> T24,\nX35 -> T25,\nT8 -> .(T24, T25),\nX13 -> X38,\nX36 -> X38,\nX37 -> T26,\nT10 -> .(T24, T26)" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 187, 4.01/1.88 "to": 226, 4.01/1.88 "label": "EVAL-BACKTRACK" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 189, 4.01/1.88 "to": 1, 4.01/1.88 "label": "INSTANCE with matching:\nT1 -> T9\nT2 -> T17\nT3 -> T12" 4.01/1.88 }, 4.01/1.88 { 4.01/1.88 "from": 225, 4.01/1.88 "to": 182, 4.01/1.88 "label": "INSTANCE with matching:\nT8 -> T25\nX13 -> X38\nT10 -> T26" 4.01/1.88 } 4.01/1.88 ], 4.01/1.88 "type": "Graph" 4.01/1.88 } 4.01/1.88 } 4.01/1.88 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (2) 4.01/1.88 Obligation: 4.01/1.88 Triples: 4.01/1.88 4.01/1.88 pB([], X1, X1, X2, X3) :- flA(X2, X1, X3). 4.01/1.88 pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). 4.01/1.88 flA(.(X1, X2), X3, s(X4)) :- pB(X1, X5, X3, X2, X4). 4.01/1.88 4.01/1.88 Clauses: 4.01/1.88 4.01/1.88 flcA([], [], 0). 4.01/1.88 flcA(.(X1, X2), X3, s(X4)) :- qcB(X1, X5, X3, X2, X4). 4.01/1.88 qcB([], X1, X1, X2, X3) :- flcA(X2, X1, X3). 4.01/1.88 qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). 4.01/1.88 4.01/1.88 Afs: 4.01/1.88 4.01/1.88 flA(x1, x2, x3) = flA(x1, x2) 4.01/1.88 4.01/1.88 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (3) TriplesToPiDPProof (SOUND) 4.01/1.88 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.01/1.88 4.01/1.88 flA_in_3: (b,b,f) 4.01/1.88 4.01/1.88 pB_in_5: (b,f,b,b,f) 4.01/1.88 4.01/1.88 Transforming TRIPLES into the following Term Rewriting System: 4.01/1.88 4.01/1.88 Pi DP problem: 4.01/1.88 The TRS P consists of the following rules: 4.01/1.88 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3, s(X4)) -> U3_GGA(X1, X2, X3, X4, pB_in_gagga(X1, X5, X3, X2, X4)) 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3, s(X4)) -> PB_IN_GAGGA(X1, X5, X3, X2, X4) 4.01/1.88 PB_IN_GAGGA([], X1, X1, X2, X3) -> U1_GAGGA(X1, X2, X3, flA_in_gga(X2, X1, X3)) 4.01/1.88 PB_IN_GAGGA([], X1, X1, X2, X3) -> FLA_IN_GGA(X2, X1, X3) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAGGA(X1, X2, X3, X4, X5, X6, pB_in_gagga(X2, X3, X4, X5, X6)) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAGGA(X2, X3, X4, X5, X6) 4.01/1.88 4.01/1.88 R is empty. 4.01/1.88 The argument filtering Pi contains the following mapping: 4.01/1.88 flA_in_gga(x1, x2, x3) = flA_in_gga(x1, x2) 4.01/1.88 4.01/1.88 .(x1, x2) = .(x1, x2) 4.01/1.88 4.01/1.88 pB_in_gagga(x1, x2, x3, x4, x5) = pB_in_gagga(x1, x3, x4) 4.01/1.88 4.01/1.88 [] = [] 4.01/1.88 4.01/1.88 s(x1) = s(x1) 4.01/1.88 4.01/1.88 FLA_IN_GGA(x1, x2, x3) = FLA_IN_GGA(x1, x2) 4.01/1.88 4.01/1.88 U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) 4.01/1.88 4.01/1.88 PB_IN_GAGGA(x1, x2, x3, x4, x5) = PB_IN_GAGGA(x1, x3, x4) 4.01/1.88 4.01/1.88 U1_GAGGA(x1, x2, x3, x4) = U1_GAGGA(x1, x2, x4) 4.01/1.88 4.01/1.88 U2_GAGGA(x1, x2, x3, x4, x5, x6, x7) = U2_GAGGA(x1, x2, x4, x5, x7) 4.01/1.88 4.01/1.88 4.01/1.88 We have to consider all (P,R,Pi)-chains 4.01/1.88 4.01/1.88 4.01/1.88 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 4.01/1.88 4.01/1.88 4.01/1.88 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (4) 4.01/1.88 Obligation: 4.01/1.88 Pi DP problem: 4.01/1.88 The TRS P consists of the following rules: 4.01/1.88 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3, s(X4)) -> U3_GGA(X1, X2, X3, X4, pB_in_gagga(X1, X5, X3, X2, X4)) 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3, s(X4)) -> PB_IN_GAGGA(X1, X5, X3, X2, X4) 4.01/1.88 PB_IN_GAGGA([], X1, X1, X2, X3) -> U1_GAGGA(X1, X2, X3, flA_in_gga(X2, X1, X3)) 4.01/1.88 PB_IN_GAGGA([], X1, X1, X2, X3) -> FLA_IN_GGA(X2, X1, X3) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAGGA(X1, X2, X3, X4, X5, X6, pB_in_gagga(X2, X3, X4, X5, X6)) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAGGA(X2, X3, X4, X5, X6) 4.01/1.88 4.01/1.88 R is empty. 4.01/1.88 The argument filtering Pi contains the following mapping: 4.01/1.88 flA_in_gga(x1, x2, x3) = flA_in_gga(x1, x2) 4.01/1.88 4.01/1.88 .(x1, x2) = .(x1, x2) 4.01/1.88 4.01/1.88 pB_in_gagga(x1, x2, x3, x4, x5) = pB_in_gagga(x1, x3, x4) 4.01/1.88 4.01/1.88 [] = [] 4.01/1.88 4.01/1.88 s(x1) = s(x1) 4.01/1.88 4.01/1.88 FLA_IN_GGA(x1, x2, x3) = FLA_IN_GGA(x1, x2) 4.01/1.88 4.01/1.88 U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) 4.01/1.88 4.01/1.88 PB_IN_GAGGA(x1, x2, x3, x4, x5) = PB_IN_GAGGA(x1, x3, x4) 4.01/1.88 4.01/1.88 U1_GAGGA(x1, x2, x3, x4) = U1_GAGGA(x1, x2, x4) 4.01/1.88 4.01/1.88 U2_GAGGA(x1, x2, x3, x4, x5, x6, x7) = U2_GAGGA(x1, x2, x4, x5, x7) 4.01/1.88 4.01/1.88 4.01/1.88 We have to consider all (P,R,Pi)-chains 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (5) DependencyGraphProof (EQUIVALENT) 4.01/1.88 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (6) 4.01/1.88 Obligation: 4.01/1.88 Pi DP problem: 4.01/1.88 The TRS P consists of the following rules: 4.01/1.88 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3, s(X4)) -> PB_IN_GAGGA(X1, X5, X3, X2, X4) 4.01/1.88 PB_IN_GAGGA([], X1, X1, X2, X3) -> FLA_IN_GGA(X2, X1, X3) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAGGA(X2, X3, X4, X5, X6) 4.01/1.88 4.01/1.88 R is empty. 4.01/1.88 The argument filtering Pi contains the following mapping: 4.01/1.88 .(x1, x2) = .(x1, x2) 4.01/1.88 4.01/1.88 [] = [] 4.01/1.88 4.01/1.88 s(x1) = s(x1) 4.01/1.88 4.01/1.88 FLA_IN_GGA(x1, x2, x3) = FLA_IN_GGA(x1, x2) 4.01/1.88 4.01/1.88 PB_IN_GAGGA(x1, x2, x3, x4, x5) = PB_IN_GAGGA(x1, x3, x4) 4.01/1.88 4.01/1.88 4.01/1.88 We have to consider all (P,R,Pi)-chains 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (7) PiDPToQDPProof (SOUND) 4.01/1.88 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (8) 4.01/1.88 Obligation: 4.01/1.88 Q DP problem: 4.01/1.88 The TRS P consists of the following rules: 4.01/1.88 4.01/1.88 FLA_IN_GGA(.(X1, X2), X3) -> PB_IN_GAGGA(X1, X3, X2) 4.01/1.88 PB_IN_GAGGA([], X1, X2) -> FLA_IN_GGA(X2, X1) 4.01/1.88 PB_IN_GAGGA(.(X1, X2), .(X1, X4), X5) -> PB_IN_GAGGA(X2, X4, X5) 4.01/1.88 4.01/1.88 R is empty. 4.01/1.88 Q is empty. 4.01/1.88 We have to consider all (P,Q,R)-chains. 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (9) QDPSizeChangeProof (EQUIVALENT) 4.01/1.88 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.01/1.88 4.01/1.88 From the DPs we obtained the following set of size-change graphs: 4.01/1.88 *PB_IN_GAGGA([], X1, X2) -> FLA_IN_GGA(X2, X1) 4.01/1.88 The graph contains the following edges 3 >= 1, 2 >= 2 4.01/1.88 4.01/1.88 4.01/1.88 *PB_IN_GAGGA(.(X1, X2), .(X1, X4), X5) -> PB_IN_GAGGA(X2, X4, X5) 4.01/1.88 The graph contains the following edges 1 > 1, 2 > 2, 3 >= 3 4.01/1.88 4.01/1.88 4.01/1.88 *FLA_IN_GGA(.(X1, X2), X3) -> PB_IN_GAGGA(X1, X3, X2) 4.01/1.88 The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3 4.01/1.88 4.01/1.88 4.01/1.88 ---------------------------------------- 4.01/1.88 4.01/1.88 (10) 4.01/1.88 YES 4.24/1.96 EOF