/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern perm(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: perm([], []). perm(.(X, L), Z) :- ','(perm(L, Y), insert(X, Y, Z)). insert(X, [], .(X, [])). insert(X, L, .(X, L)). insert(X, .(H, L1), .(H, L2)) :- insert(X, L1, L2). Query: perm(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(perm ([]) ([]))", null ], [ "(perm (. X L) Z)", "(',' (perm L Y) (insert X Y Z))" ], [ "(insert X ([]) (. X ([])))", null ], [ "(insert X L (. X L))", null ], [ "(insert X (. H L1) (. H L2))", "(insert X L1 L2)" ] ] }, "graph": { "nodes": { "44": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "67": { "goal": [ { "clause": 2, "scope": 3, "term": "(insert T6 ([]) T9)" }, { "clause": 3, "scope": 3, "term": "(insert T6 ([]) T9)" }, { "clause": 4, "scope": 3, "term": "(insert T6 ([]) T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "26": { "goal": [ { "clause": 0, "scope": 1, "term": "(perm T1 T2)" }, { "clause": 1, "scope": 1, "term": "(perm T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "27": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(perm ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [[ "(perm T1 T2)", "(perm ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "type": "Nodes", "230": { "goal": [ { "clause": 2, "scope": 4, "term": "(insert T6 T32 T9)" }, { "clause": 3, "scope": 4, "term": "(insert T6 T32 T9)" }, { "clause": 4, "scope": 4, "term": "(insert T6 T32 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": 2, "scope": 4, "term": "(insert T6 T32 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "111": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [ { "clause": 3, "scope": 4, "term": "(insert T6 T32 T9)" }, { "clause": 4, "scope": 4, "term": "(insert T6 T32 T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "112": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "233": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "113": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": 3, "scope": 3, "term": "(insert T6 ([]) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "235": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "115": { "goal": [{ "clause": 4, "scope": 3, "term": "(insert T6 ([]) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 3, "scope": 4, "term": "(insert T6 T32 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "116": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": 4, "scope": 4, "term": "(insert T6 T32 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "117": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "118": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "239": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T28 X44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T28"], "free": ["X44"], "exprvars": [] } }, "93": { "goal": [{ "clause": 2, "scope": 3, "term": "(insert T6 ([]) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "95": { "goal": [ { "clause": 3, "scope": 3, "term": "(insert T6 ([]) T9)" }, { "clause": 4, "scope": 3, "term": "(insert T6 ([]) T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": 1, "scope": 1, "term": "(perm ([]) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (perm T7 X10) (insert T6 X10 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X10"], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "164": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (perm T28 X44) (insert T27 X44 X45)) (insert T6 X45 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T27", "T28" ], "free": [ "X45", "X44" ], "exprvars": [] } }, "241": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T60 T62 T64)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T62" ], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (insert T27 T29 X45) (insert T6 X45 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T27", "T29" ], "free": ["X45"], "exprvars": [] } }, "242": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "168": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T27 T29 X45)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T29" ], "free": ["X45"], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T6 T32 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T32" ], "free": [], "exprvars": [] } }, "40": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (perm T7 X10) (insert T6 X10 T9))" }, { "clause": 1, "scope": 2, "term": "(',' (perm T7 X10) (insert T6 X10 T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X10"], "exprvars": [] } }, "41": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (perm T7 X10) (insert T6 X10 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X10"], "exprvars": [] } }, "42": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (perm T7 X10) (insert T6 X10 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X10"], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(insert T6 ([]) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 26, "label": "CASE" }, { "from": 26, "to": 27, "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 26, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 27, "to": 31, "label": "SUCCESS" }, { "from": 28, "to": 37, "label": "EVAL with clause\nperm(.(X7, X8), X9) :- ','(perm(X8, X10), insert(X7, X10, X9)).\nand substitutionX7 -> T6,\nX8 -> T7,\nT1 -> .(T6, T7),\nT2 -> T9,\nX9 -> T9,\nT8 -> T9" }, { "from": 28, "to": 39, "label": "EVAL-BACKTRACK" }, { "from": 31, "to": 35, "label": "BACKTRACK\nfor clause: perm(.(X, L), Z) :- ','(perm(L, Y), insert(X, Y, Z))because of non-unification" }, { "from": 37, "to": 40, "label": "CASE" }, { "from": 40, "to": 41, "label": "PARALLEL" }, { "from": 40, "to": 42, "label": "PARALLEL" }, { "from": 41, "to": 43, "label": "EVAL with clause\nperm([], []).\nand substitutionT7 -> [],\nX10 -> []" }, { "from": 41, "to": 44, "label": "EVAL-BACKTRACK" }, { "from": 42, "to": 164, "label": "EVAL with clause\nperm(.(X41, X42), X43) :- ','(perm(X42, X44), insert(X41, X44, X43)).\nand substitutionX41 -> T27,\nX42 -> T28,\nT7 -> .(T27, T28),\nX10 -> X45,\nX43 -> X45" }, { "from": 42, "to": 168, "label": "EVAL-BACKTRACK" }, { "from": 43, "to": 67, "label": "CASE" }, { "from": 67, "to": 93, "label": "PARALLEL" }, { "from": 67, "to": 95, "label": "PARALLEL" }, { "from": 93, "to": 111, "label": "EVAL with clause\ninsert(X17, [], .(X17, [])).\nand substitutionT6 -> T16,\nX17 -> T16,\nT9 -> .(T16, [])" }, { "from": 93, "to": 112, "label": "EVAL-BACKTRACK" }, { "from": 95, "to": 114, "label": "PARALLEL" }, { "from": 95, "to": 115, "label": "PARALLEL" }, { "from": 111, "to": 113, "label": "SUCCESS" }, { "from": 114, "to": 116, "label": "EVAL with clause\ninsert(X26, X27, .(X26, X27)).\nand substitutionT6 -> T21,\nX26 -> T21,\nX27 -> [],\nT9 -> .(T21, [])" }, { "from": 114, "to": 117, "label": "EVAL-BACKTRACK" }, { "from": 115, "to": 119, "label": "BACKTRACK\nfor clause: insert(X, .(H, L1), .(H, L2)) :- insert(X, L1, L2)because of non-unification" }, { "from": 116, "to": 118, "label": "SUCCESS" }, { "from": 164, "to": 218, "label": "SPLIT 1" }, { "from": 164, "to": 220, "label": "SPLIT 2\nnew knowledge:\nT28 is ground\nT29 is ground\nreplacements:X44 -> T29" }, { "from": 218, "to": 2, "label": "INSTANCE with matching:\nT1 -> T28\nT2 -> X44" }, { "from": 220, "to": 226, "label": "SPLIT 1" }, { "from": 220, "to": 227, "label": "SPLIT 2\nnew knowledge:\nT27 is ground\nT29 is ground\nT32 is ground\nreplacements:X45 -> T32" }, { "from": 226, "to": 227, "label": "INSTANCE with matching:\nT6 -> T27\nT32 -> T29\nT9 -> X45" }, { "from": 227, "to": 230, "label": "CASE" }, { "from": 230, "to": 231, "label": "PARALLEL" }, { "from": 230, "to": 232, "label": "PARALLEL" }, { "from": 231, "to": 233, "label": "EVAL with clause\ninsert(X56, [], .(X56, [])).\nand substitutionT6 -> T41,\nX56 -> T41,\nT32 -> [],\nT9 -> .(T41, [])" }, { "from": 231, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 232, "to": 236, "label": "PARALLEL" }, { "from": 232, "to": 237, "label": "PARALLEL" }, { "from": 233, "to": 235, "label": "SUCCESS" }, { "from": 236, "to": 238, "label": "EVAL with clause\ninsert(X65, X66, .(X65, X66)).\nand substitutionT6 -> T50,\nX65 -> T50,\nT32 -> T51,\nX66 -> T51,\nT9 -> .(T50, T51)" }, { "from": 236, "to": 239, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 241, "label": "EVAL with clause\ninsert(X75, .(X76, X77), .(X76, X78)) :- insert(X75, X77, X78).\nand substitutionT6 -> T60,\nX75 -> T60,\nX76 -> T61,\nX77 -> T62,\nT32 -> .(T61, T62),\nX78 -> T64,\nT9 -> .(T61, T64),\nT63 -> T64" }, { "from": 237, "to": 242, "label": "EVAL-BACKTRACK" }, { "from": 238, "to": 240, "label": "SUCCESS" }, { "from": 241, "to": 227, "label": "INSTANCE with matching:\nT6 -> T60\nT32 -> T62\nT9 -> T64" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: insertB(X1, .(X2, X3), .(X2, X4)) :- insertB(X1, X3, X4). permA(.(X1, .(X2, X3)), X4) :- permA(X3, X5). permA(.(X1, .(X2, X3)), X4) :- ','(permcA(X3, X5), insertB(X2, X5, X6)). permA(.(X1, .(X2, X3)), X4) :- ','(permcA(X3, X5), ','(insertcB(X2, X5, X6), insertB(X1, X6, X4))). Clauses: permcA([], []). permcA(.(X1, []), .(X1, [])). permcA(.(X1, []), .(X1, [])). permcA(.(X1, .(X2, X3)), X4) :- ','(permcA(X3, X5), ','(insertcB(X2, X5, X6), insertcB(X1, X6, X4))). insertcB(X1, [], .(X1, [])). insertcB(X1, X2, .(X1, X2)). insertcB(X1, .(X2, X3), .(X2, X4)) :- insertcB(X1, X3, X4). Afs: permA(x1, x2) = permA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: permA_in_2: (b,f) permcA_in_2: (b,f) insertcB_in_3: (b,b,f) insertB_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> U2_GA(X1, X2, X3, X4, permA_in_ga(X3, X5)) PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> PERMA_IN_GA(X3, X5) PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> U3_GA(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U4_GA(X1, X2, X3, X4, insertB_in_gga(X2, X5, X6)) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> INSERTB_IN_GGA(X2, X5, X6) INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> U1_GGA(X1, X2, X3, X4, insertB_in_gga(X1, X3, X4)) INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> INSERTB_IN_GGA(X1, X3, X4) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U5_GA(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) U5_GA(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U6_GA(X1, X2, X3, X4, insertB_in_gga(X1, X6, X4)) U5_GA(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> INSERTB_IN_GGA(X1, X6, X4) The TRS R consists of the following rules: permcA_in_ga([], []) -> permcA_out_ga([], []) permcA_in_ga(.(X1, []), .(X1, [])) -> permcA_out_ga(.(X1, []), .(X1, [])) permcA_in_ga(.(X1, .(X2, X3)), X4) -> U8_ga(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U8_ga(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U9_ga(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) insertcB_in_gga(X1, [], .(X1, [])) -> insertcB_out_gga(X1, [], .(X1, [])) insertcB_in_gga(X1, X2, .(X1, X2)) -> insertcB_out_gga(X1, X2, .(X1, X2)) insertcB_in_gga(X1, .(X2, X3), .(X2, X4)) -> U11_gga(X1, X2, X3, X4, insertcB_in_gga(X1, X3, X4)) U11_gga(X1, X2, X3, X4, insertcB_out_gga(X1, X3, X4)) -> insertcB_out_gga(X1, .(X2, X3), .(X2, X4)) U9_ga(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U10_ga(X1, X2, X3, X4, insertcB_in_gga(X1, X6, X4)) U10_ga(X1, X2, X3, X4, insertcB_out_gga(X1, X6, X4)) -> permcA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: permA_in_ga(x1, x2) = permA_in_ga(x1) .(x1, x2) = .(x1, x2) permcA_in_ga(x1, x2) = permcA_in_ga(x1) [] = [] permcA_out_ga(x1, x2) = permcA_out_ga(x1, x2) U8_ga(x1, x2, x3, x4, x5) = U8_ga(x1, x2, x3, x5) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) insertcB_in_gga(x1, x2, x3) = insertcB_in_gga(x1, x2) insertcB_out_gga(x1, x2, x3) = insertcB_out_gga(x1, x2, x3) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x1, x2, x3, x5) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) insertB_in_gga(x1, x2, x3) = insertB_in_gga'(x1, x2) PERMA_IN_GA(x1, x2) = PERMA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x3, x5) INSERTB_IN_GGA(x1, x2, x3) = INSERTB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x3, x5) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> U2_GA(X1, X2, X3, X4, permA_in_ga(X3, X5)) PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> PERMA_IN_GA(X3, X5) PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> U3_GA(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U4_GA(X1, X2, X3, X4, insertB_in_gga(X2, X5, X6)) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> INSERTB_IN_GGA(X2, X5, X6) INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> U1_GGA(X1, X2, X3, X4, insertB_in_gga(X1, X3, X4)) INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> INSERTB_IN_GGA(X1, X3, X4) U3_GA(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U5_GA(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) U5_GA(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U6_GA(X1, X2, X3, X4, insertB_in_gga(X1, X6, X4)) U5_GA(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> INSERTB_IN_GGA(X1, X6, X4) The TRS R consists of the following rules: permcA_in_ga([], []) -> permcA_out_ga([], []) permcA_in_ga(.(X1, []), .(X1, [])) -> permcA_out_ga(.(X1, []), .(X1, [])) permcA_in_ga(.(X1, .(X2, X3)), X4) -> U8_ga(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U8_ga(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U9_ga(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) insertcB_in_gga(X1, [], .(X1, [])) -> insertcB_out_gga(X1, [], .(X1, [])) insertcB_in_gga(X1, X2, .(X1, X2)) -> insertcB_out_gga(X1, X2, .(X1, X2)) insertcB_in_gga(X1, .(X2, X3), .(X2, X4)) -> U11_gga(X1, X2, X3, X4, insertcB_in_gga(X1, X3, X4)) U11_gga(X1, X2, X3, X4, insertcB_out_gga(X1, X3, X4)) -> insertcB_out_gga(X1, .(X2, X3), .(X2, X4)) U9_ga(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U10_ga(X1, X2, X3, X4, insertcB_in_gga(X1, X6, X4)) U10_ga(X1, X2, X3, X4, insertcB_out_gga(X1, X6, X4)) -> permcA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: permA_in_ga(x1, x2) = permA_in_ga(x1) .(x1, x2) = .(x1, x2) permcA_in_ga(x1, x2) = permcA_in_ga(x1) [] = [] permcA_out_ga(x1, x2) = permcA_out_ga(x1, x2) U8_ga(x1, x2, x3, x4, x5) = U8_ga(x1, x2, x3, x5) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) insertcB_in_gga(x1, x2, x3) = insertcB_in_gga(x1, x2) insertcB_out_gga(x1, x2, x3) = insertcB_out_gga(x1, x2, x3) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x1, x2, x3, x5) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) insertB_in_gga(x1, x2, x3) = insertB_in_gga(x1, x2) PERMA_IN_GA(x1, x2) = PERMA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x3, x5) INSERTB_IN_GGA(x1, x2, x3) = INSERTB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x3, x5) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> INSERTB_IN_GGA(X1, X3, X4) The TRS R consists of the following rules: permcA_in_ga([], []) -> permcA_out_ga([], []) permcA_in_ga(.(X1, []), .(X1, [])) -> permcA_out_ga(.(X1, []), .(X1, [])) permcA_in_ga(.(X1, .(X2, X3)), X4) -> U8_ga(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U8_ga(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U9_ga(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) insertcB_in_gga(X1, [], .(X1, [])) -> insertcB_out_gga(X1, [], .(X1, [])) insertcB_in_gga(X1, X2, .(X1, X2)) -> insertcB_out_gga(X1, X2, .(X1, X2)) insertcB_in_gga(X1, .(X2, X3), .(X2, X4)) -> U11_gga(X1, X2, X3, X4, insertcB_in_gga(X1, X3, X4)) U11_gga(X1, X2, X3, X4, insertcB_out_gga(X1, X3, X4)) -> insertcB_out_gga(X1, .(X2, X3), .(X2, X4)) U9_ga(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U10_ga(X1, X2, X3, X4, insertcB_in_gga(X1, X6, X4)) U10_ga(X1, X2, X3, X4, insertcB_out_gga(X1, X6, X4)) -> permcA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) permcA_in_ga(x1, x2) = permcA_in_ga(x1) [] = [] permcA_out_ga(x1, x2) = permcA_out_ga(x1, x2) U8_ga(x1, x2, x3, x4, x5) = U8_ga(x1, x2, x3, x5) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) insertcB_in_gga(x1, x2, x3) = insertcB_in_gga(x1, x2) insertcB_out_gga(x1, x2, x3) = insertcB_out_gga(x1, x2, x3) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x1, x2, x3, x5) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) INSERTB_IN_GGA(x1, x2, x3) = INSERTB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: INSERTB_IN_GGA(X1, .(X2, X3), .(X2, X4)) -> INSERTB_IN_GGA(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) INSERTB_IN_GGA(x1, x2, x3) = INSERTB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: INSERTB_IN_GGA(X1, .(X2, X3)) -> INSERTB_IN_GGA(X1, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *INSERTB_IN_GGA(X1, .(X2, X3)) -> INSERTB_IN_GGA(X1, X3) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> PERMA_IN_GA(X3, X5) The TRS R consists of the following rules: permcA_in_ga([], []) -> permcA_out_ga([], []) permcA_in_ga(.(X1, []), .(X1, [])) -> permcA_out_ga(.(X1, []), .(X1, [])) permcA_in_ga(.(X1, .(X2, X3)), X4) -> U8_ga(X1, X2, X3, X4, permcA_in_ga(X3, X5)) U8_ga(X1, X2, X3, X4, permcA_out_ga(X3, X5)) -> U9_ga(X1, X2, X3, X4, insertcB_in_gga(X2, X5, X6)) insertcB_in_gga(X1, [], .(X1, [])) -> insertcB_out_gga(X1, [], .(X1, [])) insertcB_in_gga(X1, X2, .(X1, X2)) -> insertcB_out_gga(X1, X2, .(X1, X2)) insertcB_in_gga(X1, .(X2, X3), .(X2, X4)) -> U11_gga(X1, X2, X3, X4, insertcB_in_gga(X1, X3, X4)) U11_gga(X1, X2, X3, X4, insertcB_out_gga(X1, X3, X4)) -> insertcB_out_gga(X1, .(X2, X3), .(X2, X4)) U9_ga(X1, X2, X3, X4, insertcB_out_gga(X2, X5, X6)) -> U10_ga(X1, X2, X3, X4, insertcB_in_gga(X1, X6, X4)) U10_ga(X1, X2, X3, X4, insertcB_out_gga(X1, X6, X4)) -> permcA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) permcA_in_ga(x1, x2) = permcA_in_ga(x1) [] = [] permcA_out_ga(x1, x2) = permcA_out_ga(x1, x2) U8_ga(x1, x2, x3, x4, x5) = U8_ga(x1, x2, x3, x5) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) insertcB_in_gga(x1, x2, x3) = insertcB_in_gga(x1, x2) insertcB_out_gga(x1, x2, x3) = insertcB_out_gga(x1, x2, x3) U11_gga(x1, x2, x3, x4, x5) = U11_gga(x1, x2, x3, x5) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) PERMA_IN_GA(x1, x2) = PERMA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: PERMA_IN_GA(.(X1, .(X2, X3)), X4) -> PERMA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) PERMA_IN_GA(x1, x2) = PERMA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: PERMA_IN_GA(.(X1, .(X2, X3))) -> PERMA_IN_GA(X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *PERMA_IN_GA(.(X1, .(X2, X3))) -> PERMA_IN_GA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES