3.69/1.69 YES 3.84/1.71 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.84/1.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.84/1.71 3.84/1.71 3.84/1.71 Left Termination of the query pattern 3.84/1.71 3.84/1.71 fl(g,a,a) 3.84/1.71 3.84/1.71 w.r.t. the given Prolog program could successfully be proven: 3.84/1.71 3.84/1.71 (0) Prolog 3.84/1.71 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.84/1.71 (2) TRIPLES 3.84/1.71 (3) TriplesToPiDPProof [SOUND, 0 ms] 3.84/1.71 (4) PiDP 3.84/1.71 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.84/1.71 (6) PiDP 3.84/1.71 (7) PiDPToQDPProof [SOUND, 0 ms] 3.84/1.71 (8) QDP 3.84/1.71 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.84/1.71 (10) YES 3.84/1.71 3.84/1.71 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (0) 3.84/1.71 Obligation: 3.84/1.71 Clauses: 3.84/1.71 3.84/1.71 fl([], [], 0). 3.84/1.71 fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). 3.84/1.71 append([], X, X). 3.84/1.71 append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). 3.84/1.71 3.84/1.71 3.84/1.71 Query: fl(g,a,a) 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (1) PrologToDTProblemTransformerProof (SOUND) 3.84/1.71 Built DT problem from termination graph DT10. 3.84/1.71 3.84/1.71 { 3.84/1.71 "root": 17, 3.84/1.71 "program": { 3.84/1.71 "directives": [], 3.84/1.71 "clauses": [ 3.84/1.71 [ 3.84/1.71 "(fl ([]) ([]) (0))", 3.84/1.71 null 3.84/1.71 ], 3.84/1.71 [ 3.84/1.71 "(fl (. E X) R (s Z))", 3.84/1.71 "(',' (append E Y R) (fl X Y Z))" 3.84/1.71 ], 3.84/1.71 [ 3.84/1.71 "(append ([]) X X)", 3.84/1.71 null 3.84/1.71 ], 3.84/1.71 [ 3.84/1.71 "(append (. X Xs) Ys (. X Zs))", 3.84/1.71 "(append Xs Ys Zs)" 3.84/1.71 ] 3.84/1.71 ] 3.84/1.71 }, 3.84/1.71 "graph": { 3.84/1.71 "nodes": { 3.84/1.71 "17": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": -1, 3.84/1.71 "scope": -1, 3.84/1.71 "term": "(fl T1 T2 T3)" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": ["T1"], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "18": { 3.84/1.71 "goal": [ 3.84/1.71 { 3.84/1.71 "clause": 0, 3.84/1.71 "scope": 1, 3.84/1.71 "term": "(fl T1 T2 T3)" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "clause": 1, 3.84/1.71 "scope": 1, 3.84/1.71 "term": "(fl T1 T2 T3)" 3.84/1.71 } 3.84/1.71 ], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": ["T1"], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "type": "Nodes", 3.84/1.71 "211": { 3.84/1.71 "goal": [], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "212": { 3.84/1.71 "goal": [ 3.84/1.71 { 3.84/1.71 "clause": 2, 3.84/1.71 "scope": 2, 3.84/1.71 "term": "(',' (append T8 X13 T12) (fl T9 X13 T13))" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "clause": 3, 3.84/1.71 "scope": 2, 3.84/1.71 "term": "(',' (append T8 X13 T12) (fl T9 X13 T13))" 3.84/1.71 } 3.84/1.71 ], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [ 3.84/1.71 "T8", 3.84/1.71 "T9" 3.84/1.71 ], 3.84/1.71 "free": ["X13"], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "213": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": 2, 3.84/1.71 "scope": 2, 3.84/1.71 "term": "(',' (append T8 X13 T12) (fl T9 X13 T13))" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [ 3.84/1.71 "T8", 3.84/1.71 "T9" 3.84/1.71 ], 3.84/1.71 "free": ["X13"], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "214": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": 3, 3.84/1.71 "scope": 2, 3.84/1.71 "term": "(',' (append T8 X13 T12) (fl T9 X13 T13))" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [ 3.84/1.71 "T8", 3.84/1.71 "T9" 3.84/1.71 ], 3.84/1.71 "free": ["X13"], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "215": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": -1, 3.84/1.71 "scope": -1, 3.84/1.71 "term": "(fl T9 T19 T20)" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": ["T9"], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "106": { 3.84/1.71 "goal": [ 3.84/1.71 { 3.84/1.71 "clause": -1, 3.84/1.71 "scope": -1, 3.84/1.71 "term": "(true)" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "clause": 1, 3.84/1.71 "scope": 1, 3.84/1.71 "term": "(fl ([]) T2 T3)" 3.84/1.71 } 3.84/1.71 ], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "216": { 3.84/1.71 "goal": [], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "227": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": -1, 3.84/1.71 "scope": -1, 3.84/1.71 "term": "(',' (append T28 X38 T30) (fl T9 X38 T31))" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [ 3.84/1.71 "T9", 3.84/1.71 "T28" 3.84/1.71 ], 3.84/1.71 "free": ["X38"], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "107": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": 1, 3.84/1.71 "scope": 1, 3.84/1.71 "term": "(fl T1 T2 T3)" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [[ 3.84/1.71 "(fl T1 T2 T3)", 3.84/1.71 "(fl ([]) ([]) (0))" 3.84/1.71 ]], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": ["T1"], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "228": { 3.84/1.71 "goal": [], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "108": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": 1, 3.84/1.71 "scope": 1, 3.84/1.71 "term": "(fl ([]) T2 T3)" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "109": { 3.84/1.71 "goal": [], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [], 3.84/1.71 "free": [], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "208": { 3.84/1.71 "goal": [{ 3.84/1.71 "clause": -1, 3.84/1.71 "scope": -1, 3.84/1.71 "term": "(',' (append T8 X13 T12) (fl T9 X13 T13))" 3.84/1.71 }], 3.84/1.71 "kb": { 3.84/1.71 "nonunifying": [], 3.84/1.71 "intvars": {}, 3.84/1.71 "arithmetic": { 3.84/1.71 "type": "PlainIntegerRelationState", 3.84/1.71 "relations": [] 3.84/1.71 }, 3.84/1.71 "ground": [ 3.84/1.71 "T8", 3.84/1.71 "T9" 3.84/1.71 ], 3.84/1.71 "free": ["X13"], 3.84/1.71 "exprvars": [] 3.84/1.71 } 3.84/1.71 } 3.84/1.71 }, 3.84/1.71 "edges": [ 3.84/1.71 { 3.84/1.71 "from": 17, 3.84/1.71 "to": 18, 3.84/1.71 "label": "CASE" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 18, 3.84/1.71 "to": 106, 3.84/1.71 "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 18, 3.84/1.71 "to": 107, 3.84/1.71 "label": "EVAL-BACKTRACK" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 106, 3.84/1.71 "to": 108, 3.84/1.71 "label": "SUCCESS" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 107, 3.84/1.71 "to": 208, 3.84/1.71 "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 -> T13,\nT3 -> s(T13),\nT10 -> T12,\nT11 -> T13" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 107, 3.84/1.71 "to": 211, 3.84/1.71 "label": "EVAL-BACKTRACK" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 108, 3.84/1.71 "to": 109, 3.84/1.71 "label": "BACKTRACK\nfor clause: fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z))because of non-unification" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 208, 3.84/1.71 "to": 212, 3.84/1.71 "label": "CASE" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 212, 3.84/1.71 "to": 213, 3.84/1.71 "label": "PARALLEL" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 212, 3.84/1.71 "to": 214, 3.84/1.71 "label": "PARALLEL" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 213, 3.84/1.71 "to": 215, 3.84/1.71 "label": "EVAL with clause\nappend([], X22, X22).\nand substitutionT8 -> [],\nX13 -> T19,\nX22 -> T19,\nT12 -> T19,\nX23 -> T19,\nT18 -> T19,\nT13 -> T20" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 213, 3.84/1.71 "to": 216, 3.84/1.71 "label": "EVAL-BACKTRACK" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 214, 3.84/1.71 "to": 227, 3.84/1.71 "label": "EVAL with clause\nappend(.(X34, X35), X36, .(X34, X37)) :- append(X35, X36, X37).\nand substitutionX34 -> T27,\nX35 -> T28,\nT8 -> .(T27, T28),\nX13 -> X38,\nX36 -> X38,\nX37 -> T30,\nT12 -> .(T27, T30),\nT29 -> T30,\nT13 -> T31" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 214, 3.84/1.71 "to": 228, 3.84/1.71 "label": "EVAL-BACKTRACK" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 215, 3.84/1.71 "to": 17, 3.84/1.71 "label": "INSTANCE with matching:\nT1 -> T9\nT2 -> T19\nT3 -> T20" 3.84/1.71 }, 3.84/1.71 { 3.84/1.71 "from": 227, 3.84/1.71 "to": 208, 3.84/1.71 "label": "INSTANCE with matching:\nT8 -> T28\nX13 -> X38\nT12 -> T30\nT13 -> T31" 3.84/1.71 } 3.84/1.71 ], 3.84/1.71 "type": "Graph" 3.84/1.71 } 3.84/1.71 } 3.84/1.71 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (2) 3.84/1.71 Obligation: 3.84/1.71 Triples: 3.84/1.71 3.84/1.71 pB([], X1, X1, X2, X3) :- flA(X2, X1, X3). 3.84/1.71 pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). 3.84/1.71 flA(.(X1, X2), X3, s(X4)) :- pB(X1, X5, X3, X2, X4). 3.84/1.71 3.84/1.71 Clauses: 3.84/1.71 3.84/1.71 flcA([], [], 0). 3.84/1.71 flcA(.(X1, X2), X3, s(X4)) :- qcB(X1, X5, X3, X2, X4). 3.84/1.71 qcB([], X1, X1, X2, X3) :- flcA(X2, X1, X3). 3.84/1.71 qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). 3.84/1.71 3.84/1.71 Afs: 3.84/1.71 3.84/1.71 flA(x1, x2, x3) = flA(x1) 3.84/1.71 3.84/1.71 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (3) TriplesToPiDPProof (SOUND) 3.84/1.71 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.84/1.71 3.84/1.71 flA_in_3: (b,f,f) 3.84/1.71 3.84/1.71 pB_in_5: (b,f,f,b,f) 3.84/1.71 3.84/1.71 Transforming TRIPLES into the following Term Rewriting System: 3.84/1.71 3.84/1.71 Pi DP problem: 3.84/1.71 The TRS P consists of the following rules: 3.84/1.71 3.84/1.71 FLA_IN_GAA(.(X1, X2), X3, s(X4)) -> U3_GAA(X1, X2, X3, X4, pB_in_gaaga(X1, X5, X3, X2, X4)) 3.84/1.71 FLA_IN_GAA(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGA(X1, X5, X3, X2, X4) 3.84/1.71 PB_IN_GAAGA([], X1, X1, X2, X3) -> U1_GAAGA(X1, X2, X3, flA_in_gaa(X2, X1, X3)) 3.84/1.71 PB_IN_GAAGA([], X1, X1, X2, X3) -> FLA_IN_GAA(X2, X1, X3) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAAGA(X1, X2, X3, X4, X5, X6, pB_in_gaaga(X2, X3, X4, X5, X6)) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGA(X2, X3, X4, X5, X6) 3.84/1.71 3.84/1.71 R is empty. 3.84/1.71 The argument filtering Pi contains the following mapping: 3.84/1.71 flA_in_gaa(x1, x2, x3) = flA_in_gaa(x1) 3.84/1.71 3.84/1.71 .(x1, x2) = .(x1, x2) 3.84/1.71 3.84/1.71 pB_in_gaaga(x1, x2, x3, x4, x5) = pB_in_gaaga(x1, x4) 3.84/1.71 3.84/1.71 [] = [] 3.84/1.71 3.84/1.71 s(x1) = s(x1) 3.84/1.71 3.84/1.71 FLA_IN_GAA(x1, x2, x3) = FLA_IN_GAA(x1) 3.84/1.71 3.84/1.71 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x1, x2, x5) 3.84/1.71 3.84/1.71 PB_IN_GAAGA(x1, x2, x3, x4, x5) = PB_IN_GAAGA(x1, x4) 3.84/1.71 3.84/1.71 U1_GAAGA(x1, x2, x3, x4) = U1_GAAGA(x2, x4) 3.84/1.71 3.84/1.71 U2_GAAGA(x1, x2, x3, x4, x5, x6, x7) = U2_GAAGA(x1, x2, x5, x7) 3.84/1.71 3.84/1.71 3.84/1.71 We have to consider all (P,R,Pi)-chains 3.84/1.71 3.84/1.71 3.84/1.71 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 3.84/1.71 3.84/1.71 3.84/1.71 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (4) 3.84/1.71 Obligation: 3.84/1.71 Pi DP problem: 3.84/1.71 The TRS P consists of the following rules: 3.84/1.71 3.84/1.71 FLA_IN_GAA(.(X1, X2), X3, s(X4)) -> U3_GAA(X1, X2, X3, X4, pB_in_gaaga(X1, X5, X3, X2, X4)) 3.84/1.71 FLA_IN_GAA(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGA(X1, X5, X3, X2, X4) 3.84/1.71 PB_IN_GAAGA([], X1, X1, X2, X3) -> U1_GAAGA(X1, X2, X3, flA_in_gaa(X2, X1, X3)) 3.84/1.71 PB_IN_GAAGA([], X1, X1, X2, X3) -> FLA_IN_GAA(X2, X1, X3) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U2_GAAGA(X1, X2, X3, X4, X5, X6, pB_in_gaaga(X2, X3, X4, X5, X6)) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGA(X2, X3, X4, X5, X6) 3.84/1.71 3.84/1.71 R is empty. 3.84/1.71 The argument filtering Pi contains the following mapping: 3.84/1.71 flA_in_gaa(x1, x2, x3) = flA_in_gaa(x1) 3.84/1.71 3.84/1.71 .(x1, x2) = .(x1, x2) 3.84/1.71 3.84/1.71 pB_in_gaaga(x1, x2, x3, x4, x5) = pB_in_gaaga(x1, x4) 3.84/1.71 3.84/1.71 [] = [] 3.84/1.71 3.84/1.71 s(x1) = s(x1) 3.84/1.71 3.84/1.71 FLA_IN_GAA(x1, x2, x3) = FLA_IN_GAA(x1) 3.84/1.71 3.84/1.71 U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x1, x2, x5) 3.84/1.71 3.84/1.71 PB_IN_GAAGA(x1, x2, x3, x4, x5) = PB_IN_GAAGA(x1, x4) 3.84/1.71 3.84/1.71 U1_GAAGA(x1, x2, x3, x4) = U1_GAAGA(x2, x4) 3.84/1.71 3.84/1.71 U2_GAAGA(x1, x2, x3, x4, x5, x6, x7) = U2_GAAGA(x1, x2, x5, x7) 3.84/1.71 3.84/1.71 3.84/1.71 We have to consider all (P,R,Pi)-chains 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (5) DependencyGraphProof (EQUIVALENT) 3.84/1.71 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (6) 3.84/1.71 Obligation: 3.84/1.71 Pi DP problem: 3.84/1.71 The TRS P consists of the following rules: 3.84/1.71 3.84/1.71 FLA_IN_GAA(.(X1, X2), X3, s(X4)) -> PB_IN_GAAGA(X1, X5, X3, X2, X4) 3.84/1.71 PB_IN_GAAGA([], X1, X1, X2, X3) -> FLA_IN_GAA(X2, X1, X3) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_GAAGA(X2, X3, X4, X5, X6) 3.84/1.71 3.84/1.71 R is empty. 3.84/1.71 The argument filtering Pi contains the following mapping: 3.84/1.71 .(x1, x2) = .(x1, x2) 3.84/1.71 3.84/1.71 [] = [] 3.84/1.71 3.84/1.71 s(x1) = s(x1) 3.84/1.71 3.84/1.71 FLA_IN_GAA(x1, x2, x3) = FLA_IN_GAA(x1) 3.84/1.71 3.84/1.71 PB_IN_GAAGA(x1, x2, x3, x4, x5) = PB_IN_GAAGA(x1, x4) 3.84/1.71 3.84/1.71 3.84/1.71 We have to consider all (P,R,Pi)-chains 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (7) PiDPToQDPProof (SOUND) 3.84/1.71 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (8) 3.84/1.71 Obligation: 3.84/1.71 Q DP problem: 3.84/1.71 The TRS P consists of the following rules: 3.84/1.71 3.84/1.71 FLA_IN_GAA(.(X1, X2)) -> PB_IN_GAAGA(X1, X2) 3.84/1.71 PB_IN_GAAGA([], X2) -> FLA_IN_GAA(X2) 3.84/1.71 PB_IN_GAAGA(.(X1, X2), X5) -> PB_IN_GAAGA(X2, X5) 3.84/1.71 3.84/1.71 R is empty. 3.84/1.71 Q is empty. 3.84/1.71 We have to consider all (P,Q,R)-chains. 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (9) QDPSizeChangeProof (EQUIVALENT) 3.84/1.71 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. 3.84/1.71 3.84/1.71 From the DPs we obtained the following set of size-change graphs: 3.84/1.71 *PB_IN_GAAGA([], X2) -> FLA_IN_GAA(X2) 3.84/1.71 The graph contains the following edges 2 >= 1 3.84/1.71 3.84/1.71 3.84/1.71 *PB_IN_GAAGA(.(X1, X2), X5) -> PB_IN_GAAGA(X2, X5) 3.84/1.71 The graph contains the following edges 1 > 1, 2 >= 2 3.84/1.71 3.84/1.71 3.84/1.71 *FLA_IN_GAA(.(X1, X2)) -> PB_IN_GAAGA(X1, X2) 3.84/1.71 The graph contains the following edges 1 > 1, 1 > 2 3.84/1.71 3.84/1.71 3.84/1.71 ---------------------------------------- 3.84/1.71 3.84/1.71 (10) 3.84/1.71 YES 3.84/1.73 EOF