/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern dupli(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 64 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: dupli(L1, N, L2) :- dupli(L1, N, L2, N). dupli([], X1, [], X2). dupli(.(X3, Xs), N, Ys, 0) :- dupli(Xs, N, Ys, N). dupli(.(X, Xs), N, .(X, Ys), K) :- ','(>(K, 0), ','(is(K1, -(K, 1)), dupli(.(X, Xs), N, Ys, K1))). Query: dupli(g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(dupli L1 N L2)", "(dupli L1 N L2 N)" ], [ "(dupli ([]) X1 ([]) X2)", null ], [ "(dupli (. X3 Xs) N Ys (0))", "(dupli Xs N Ys N)" ], [ "(dupli (. X Xs) N (. X Ys) K)", "(',' (> K (0)) (',' (is K1 (- K (1))) (dupli (. X Xs) N Ys K1)))" ] ] }, "graph": { "nodes": { "46": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T47 (0)) (',' (is X60 (- T47 (1))) (dupli (. T45 T46) T47 T49 X60)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46", "T47" ], "free": ["X60"], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1380": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T47", "T46", "T45" ], "free": ["X60"], "exprvars": ["T47"] } }, "1436": { "goal": [ { "clause": 2, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" }, { "clause": 3, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T47", "T46", "T45", "T50" ], "free": [], "exprvars": [ "T47", "T50" ] } }, "1435": { "goal": [ { "clause": 1, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" }, { "clause": 2, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" }, { "clause": 3, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T47", "T46", "T45", "T50" ], "free": [], "exprvars": [ "T47", "T50" ] } }, "1379": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X60 (- T47 (1))) (dupli (. T45 T46) T47 T49 X60))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T47", "T46", "T45" ], "free": ["X60"], "exprvars": ["T47"] } }, "10": { "goal": [{ "clause": 1, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "1416": { "goal": [{ "clause": -1, "scope": -1, "term": "(dupli (. T45 T46) T47 T49 T50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T47", "T46", "T45", "T50" ], "free": ["X60"], "exprvars": [ "T47", "T50" ] } }, "11": { "goal": [ { "clause": 2, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }, { "clause": 3, "scope": 2, "term": "(dupli T7 T8 T10 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": 2, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(dupli T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1446": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T47", "T50" ] } }, "1445": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T88 (0)) (',' (is X107 (- T88 (1))) (dupli (. T84 T85) T86 T89 X107)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T86", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T86", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T85", "T86", "T88" ], "free": ["X107"], "exprvars": [ "T86", "T47", "T50", "T88" ] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(dupli T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1444": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T47", "T50" ] } }, "1443": { "goal": [{ "clause": -1, "scope": -1, "term": "(dupli T68 T69 T71 T69)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T69", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T69", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T68", "T69" ], "free": [], "exprvars": [ "T47", "T69", "T50" ] } }, "1442": { "goal": [{ "clause": 3, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T47", "T46", "T45", "T50" ], "free": [], "exprvars": [ "T47", "T50" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(dupli T7 T8 T10 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "1441": { "goal": [{ "clause": 2, "scope": 3, "term": "(dupli (. T45 T46) T47 T49 T50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T50", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T47", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T47", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T47", "T46", "T45", "T50" ], "free": [], "exprvars": [ "T47", "T50" ] } }, "8": { "goal": [ { "clause": 1, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }, { "clause": 2, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }, { "clause": 3, "scope": 2, "term": "(dupli T7 T8 T10 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 3, "scope": 2, "term": "(dupli T7 T8 T10 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(dupli T33 (0) T36 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [], "exprvars": [] } }, "43": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "ONLY EVAL with clause\ndupli(X7, X8, X9) :- dupli(X7, X8, X9, X8).\nand substitutionT1 -> T7,\nX7 -> T7,\nT2 -> T8,\nX8 -> T8,\nT3 -> T10,\nX9 -> T10,\nT9 -> T10" }, { "from": 7, "to": 8, "label": "CASE" }, { "from": 8, "to": 10, "label": "PARALLEL" }, { "from": 8, "to": 11, "label": "PARALLEL" }, { "from": 10, "to": 13, "label": "EVAL with clause\ndupli([], X18, [], X19).\nand substitutionT7 -> [],\nT8 -> T15,\nX18 -> T15,\nT10 -> [],\nX19 -> T15" }, { "from": 10, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 39, "label": "PARALLEL" }, { "from": 11, "to": 40, "label": "PARALLEL" }, { "from": 13, "to": 25, "label": "SUCCESS" }, { "from": 39, "to": 41, "label": "EVAL with clause\ndupli(.(X36, X37), X38, X39, 0) :- dupli(X37, X38, X39, X38).\nand substitutionX36 -> T32,\nX37 -> T33,\nT7 -> .(T32, T33),\nT8 -> 0,\nX38 -> 0,\nT10 -> T36,\nX39 -> T36,\nT34 -> 0,\nT35 -> T36" }, { "from": 39, "to": 43, "label": "EVAL-BACKTRACK" }, { "from": 40, "to": 46, "label": "EVAL with clause\ndupli(.(X55, X56), X57, .(X55, X58), X59) :- ','(>(X59, 0), ','(is(X60, -(X59, 1)), dupli(.(X55, X56), X57, X58, X60))).\nand substitutionX55 -> T45,\nX56 -> T46,\nT7 -> .(T45, T46),\nT8 -> T47,\nX57 -> T47,\nX58 -> T49,\nT10 -> .(T45, T49),\nX59 -> T47,\nT48 -> T49" }, { "from": 40, "to": 47, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 7, "label": "INSTANCE with matching:\nT7 -> T33\nT8 -> 0\nT10 -> T36" }, { "from": 46, "to": 48, "label": "IS ERROR" }, { "from": 46, "to": 1379, "label": "ARITHCOMP SUCCESS" }, { "from": 46, "to": 1380, "label": "ARITHCOMP FAIL" }, { "from": 1379, "to": 1416, "label": "\nX60 -> T50" }, { "from": 1416, "to": 1435, "label": "CASE" }, { "from": 1435, "to": 1436, "label": "BACKTRACK\nfor clause: dupli([], X1, [], X2)because of non-unification" }, { "from": 1436, "to": 1441, "label": "PARALLEL" }, { "from": 1436, "to": 1442, "label": "PARALLEL" }, { "from": 1441, "to": 1443, "label": "EVAL with clause\ndupli(.(X83, X84), X85, X86, 0) :- dupli(X84, X85, X86, X85).\nand substitutionT45 -> T67,\nX83 -> T67,\nT46 -> T68,\nX84 -> T68,\nT47 -> T69,\nX85 -> T69,\nT49 -> T71,\nX86 -> T71,\nT50 -> 0,\nT70 -> T71" }, { "from": 1441, "to": 1444, "label": "EVAL-BACKTRACK" }, { "from": 1442, "to": 1445, "label": "EVAL with clause\ndupli(.(X102, X103), X104, .(X102, X105), X106) :- ','(>(X106, 0), ','(is(X107, -(X106, 1)), dupli(.(X102, X103), X104, X105, X107))).\nand substitutionT45 -> T84,\nX102 -> T84,\nT46 -> T85,\nX103 -> T85,\nT47 -> T86,\nX104 -> T86,\nX105 -> T89,\nT49 -> .(T84, T89),\nT50 -> T88,\nX106 -> T88,\nT87 -> T89" }, { "from": 1442, "to": 1446, "label": "EVAL-BACKTRACK" }, { "from": 1443, "to": 7, "label": "INSTANCE with matching:\nT7 -> T68\nT8 -> T69\nT10 -> T71" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: dupliA(.(X1, X2), 0, X3) :- dupliA(X2, 0, X3). dupliA(.(X1, X2), X3, .(X1, X4)) :- dupliA(X2, X3, X4). dupliB(X1, X2, X3) :- dupliA(X1, X2, X3). Clauses: duplicA([], X1, []). duplicA(.(X1, X2), 0, X3) :- duplicA(X2, 0, X3). duplicA(.(X1, X2), X3, .(X1, X4)) :- duplicA(X2, X3, X4). Afs: dupliB(x1, x2, x3) = dupliB(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: dupliB_in_3: (b,b,f) dupliA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: DUPLIB_IN_GGA(X1, X2, X3) -> U3_GGA(X1, X2, X3, dupliA_in_gga(X1, X2, X3)) DUPLIB_IN_GGA(X1, X2, X3) -> DUPLIA_IN_GGA(X1, X2, X3) DUPLIA_IN_GGA(.(X1, X2), 0, X3) -> U1_GGA(X1, X2, X3, dupliA_in_gga(X2, 0, X3)) DUPLIA_IN_GGA(.(X1, X2), 0, X3) -> DUPLIA_IN_GGA(X2, 0, X3) DUPLIA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U2_GGA(X1, X2, X3, X4, dupliA_in_gga(X2, X3, X4)) DUPLIA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> DUPLIA_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: dupliA_in_gga(x1, x2, x3) = dupliA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) 0 = 0 DUPLIB_IN_GGA(x1, x2, x3) = DUPLIB_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) DUPLIA_IN_GGA(x1, x2, x3) = DUPLIA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(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: DUPLIB_IN_GGA(X1, X2, X3) -> U3_GGA(X1, X2, X3, dupliA_in_gga(X1, X2, X3)) DUPLIB_IN_GGA(X1, X2, X3) -> DUPLIA_IN_GGA(X1, X2, X3) DUPLIA_IN_GGA(.(X1, X2), 0, X3) -> U1_GGA(X1, X2, X3, dupliA_in_gga(X2, 0, X3)) DUPLIA_IN_GGA(.(X1, X2), 0, X3) -> DUPLIA_IN_GGA(X2, 0, X3) DUPLIA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U2_GGA(X1, X2, X3, X4, dupliA_in_gga(X2, X3, X4)) DUPLIA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> DUPLIA_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: dupliA_in_gga(x1, x2, x3) = dupliA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) 0 = 0 DUPLIB_IN_GGA(x1, x2, x3) = DUPLIB_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) DUPLIA_IN_GGA(x1, x2, x3) = DUPLIA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: DUPLIA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> DUPLIA_IN_GGA(X2, X3, X4) DUPLIA_IN_GGA(.(X1, X2), 0, X3) -> DUPLIA_IN_GGA(X2, 0, X3) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) 0 = 0 DUPLIA_IN_GGA(x1, x2, x3) = DUPLIA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: DUPLIA_IN_GGA(.(X1, X2), X3) -> DUPLIA_IN_GGA(X2, X3) DUPLIA_IN_GGA(.(X1, X2), 0) -> DUPLIA_IN_GGA(X2, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) 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: *DUPLIA_IN_GGA(.(X1, X2), X3) -> DUPLIA_IN_GGA(X2, X3) The graph contains the following edges 1 > 1, 2 >= 2 *DUPLIA_IN_GGA(.(X1, X2), 0) -> DUPLIA_IN_GGA(X2, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (10) YES