/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 q(g,g) 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) PiDPToQDPProof [SOUND, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) PiDP (13) PiDPToQDPProof [SOUND, 0 ms] (14) QDP (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: q(X, Y) :- m(X, Y, Z). m(X, 0, X). m(0, Y, 0) :- !. m(X, Y, Z) :- ','(p(X, A), ','(p(Y, B), m(A, B, Z))). p(0, 0). p(s(X), X). Query: q(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(q X Y)", "(m X Y Z)" ], [ "(m X (0) X)", null ], [ "(m (0) Y (0))", "(!)" ], [ "(m X Y Z)", "(',' (p X A) (',' (p Y B) (m A B Z)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ] ] }, "graph": { "nodes": { "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(m T5 T6 X5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X5"], "exprvars": [] } }, "type": "Nodes", "130": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (p (0) X28) (m T15 X28 X29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X29", "X28" ], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(m T15 (0) X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X29"], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": 3, "scope": 2, "term": "(m T5 T6 X5)" }], "kb": { "nonunifying": [ [ "(m T5 T6 X5)", "(m X8 (0) X8)" ], [ "(m T5 T6 X5)", "(m (0) X42 (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X5", "X8", "X42" ], "exprvars": [] } }, "112": { "goal": [{ "clause": 5, "scope": 3, "term": "(',' (p T12 X27) (',' (p (0) X28) (m X27 X28 X29)))" }], "kb": { "nonunifying": [[ "(m T12 (0) X5)", "(m (0) X11 (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X5", "X11", "X29", "X27", "X28" ], "exprvars": [] } }, "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T27 X58) (',' (p T28 X59) (m X58 X59 X60)))" }], "kb": { "nonunifying": [ [ "(m T27 T28 X5)", "(m X8 (0) X8)" ], [ "(m T27 T28 X5)", "(m (0) X42 (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28" ], "free": [ "X5", "X8", "X42", "X60", "X58", "X59" ], "exprvars": [] } }, "212": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [ { "clause": 4, "scope": 5, "term": "(',' (p T27 X58) (',' (p T28 X59) (m X58 X59 X60)))" }, { "clause": 5, "scope": 5, "term": "(',' (p T27 X58) (',' (p T28 X59) (m X58 X59 X60)))" } ], "kb": { "nonunifying": [ [ "(m T27 T28 X5)", "(m X8 (0) X8)" ], [ "(m T27 T28 X5)", "(m (0) X42 (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28" ], "free": [ "X5", "X8", "X42", "X60", "X58", "X59" ], "exprvars": [] } }, "30": { "goal": [ { "clause": 1, "scope": 2, "term": "(m T5 T6 X5)" }, { "clause": 2, "scope": 2, "term": "(m T5 T6 X5)" }, { "clause": 3, "scope": 2, "term": "(m T5 T6 X5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X5"], "exprvars": [] } }, "96": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_2)" }, { "clause": 3, "scope": 2, "term": "(m (0) (0) X5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "31": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 2, "term": "(m T9 (0) X5)" }, { "clause": 3, "scope": 2, "term": "(m T9 (0) X5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X5"], "exprvars": [] } }, "56": { "goal": [ { "clause": 2, "scope": 2, "term": "(m T9 (0) X5)" }, { "clause": 3, "scope": 2, "term": "(m T9 (0) X5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X5"], "exprvars": [] } }, "38": { "goal": [ { "clause": 2, "scope": 2, "term": "(m T5 T6 X5)" }, { "clause": 3, "scope": 2, "term": "(m T5 T6 X5)" } ], "kb": { "nonunifying": [[ "(m T5 T6 X5)", "(m X8 (0) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X5", "X8" ], "exprvars": [] } }, "260": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (p T27 X58) (',' (p T28 X59) (m X58 X59 X60)))" }], "kb": { "nonunifying": [ [ "(m T27 T28 X5)", "(m X8 (0) X8)" ], [ "(m T27 T28 X5)", "(m (0) X42 (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28" ], "free": [ "X5", "X8", "X42", "X60", "X58", "X59" ], "exprvars": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T28 X59) (m T31 X59 X60))" }], "kb": { "nonunifying": [[ "(m (s T31) T28 X5)", "(m X8 (0) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T31" ], "free": [ "X5", "X8", "X60", "X59" ], "exprvars": [] } }, "262": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [ { "clause": 4, "scope": 6, "term": "(',' (p T28 X59) (m T31 X59 X60))" }, { "clause": 5, "scope": 6, "term": "(',' (p T28 X59) (m T31 X59 X60))" } ], "kb": { "nonunifying": [[ "(m (s T31) T28 X5)", "(m X8 (0) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T31" ], "free": [ "X5", "X8", "X60", "X59" ], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "100": { "goal": [{ "clause": 3, "scope": 2, "term": "(m T9 (0) X5)" }], "kb": { "nonunifying": [[ "(m T9 (0) X5)", "(m (0) X11 (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X5", "X11" ], "exprvars": [] } }, "265": { "goal": [{ "clause": 5, "scope": 6, "term": "(',' (p T28 X59) (m T31 X59 X60))" }], "kb": { "nonunifying": [[ "(m (s T31) T28 X5)", "(m X8 (0) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T31" ], "free": [ "X5", "X8", "X60", "X59" ], "exprvars": [] } }, "2": { "goal": [{ "clause": 0, "scope": 1, "term": "(q T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "101": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (0) X28) (m T15 X28 X29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X29", "X28" ], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(m T31 T35 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T35" ], "free": ["X60"], "exprvars": [] } }, "102": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T12 X27) (',' (p (0) X28) (m X27 X28 X29)))" }], "kb": { "nonunifying": [[ "(m T12 (0) X5)", "(m (0) X11 (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X5", "X11", "X29", "X27", "X28" ], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (p (0) X28) (m T15 X28 X29))" }, { "clause": 5, "scope": 4, "term": "(',' (p (0) X28) (m T15 X28 X29))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X29", "X28" ], "exprvars": [] } }, "107": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (p T12 X27) (',' (p (0) X28) (m X27 X28 X29)))" }, { "clause": 5, "scope": 3, "term": "(',' (p T12 X27) (',' (p (0) X28) (m X27 X28 X29)))" } ], "kb": { "nonunifying": [[ "(m T12 (0) X5)", "(m (0) X11 (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X5", "X11", "X29", "X27", "X28" ], "exprvars": [] } }, "129": { "goal": [{ "clause": 4, "scope": 4, "term": "(',' (p (0) X28) (m T15 X28 X29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X29", "X28" ], "exprvars": [] } }, "208": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_2)" }, { "clause": 3, "scope": 2, "term": "(m (0) T22 X5)" } ], "kb": { "nonunifying": [[ "(m (0) T22 X5)", "(m X8 (0) X8)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X5", "X8" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 29, "label": "ONLY EVAL with clause\nq(X3, X4) :- m(X3, X4, X5).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> T6,\nX4 -> T6" }, { "from": 29, "to": 30, "label": "CASE" }, { "from": 30, "to": 31, "label": "EVAL with clause\nm(X8, 0, X8).\nand substitutionT5 -> T9,\nX8 -> T9,\nT6 -> 0,\nX5 -> T9" }, { "from": 30, "to": 38, "label": "EVAL-BACKTRACK" }, { "from": 31, "to": 56, "label": "SUCCESS" }, { "from": 38, "to": 208, "label": "EVAL with clause\nm(0, X42, 0) :- !_2.\nand substitutionT5 -> 0,\nT6 -> T22,\nX42 -> T22,\nX5 -> 0" }, { "from": 38, "to": 210, "label": "EVAL-BACKTRACK" }, { "from": 56, "to": 96, "label": "EVAL with clause\nm(0, X11, 0) :- !_2.\nand substitutionT9 -> 0,\nX11 -> 0,\nX5 -> 0" }, { "from": 56, "to": 100, "label": "EVAL-BACKTRACK" }, { "from": 96, "to": 101, "label": "CUT" }, { "from": 100, "to": 103, "label": "ONLY EVAL with clause\nm(X24, X25, X26) :- ','(p(X24, X27), ','(p(X25, X28), m(X27, X28, X26))).\nand substitutionT9 -> T12,\nX24 -> T12,\nX25 -> 0,\nX5 -> X29,\nX26 -> X29" }, { "from": 101, "to": 102, "label": "SUCCESS" }, { "from": 103, "to": 107, "label": "CASE" }, { "from": 107, "to": 112, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(T12, 0, X5), m(0, X11, 0))" }, { "from": 112, "to": 123, "label": "EVAL with clause\np(s(X34), X34).\nand substitutionX34 -> T15,\nT12 -> s(T15),\nX27 -> T15" }, { "from": 112, "to": 125, "label": "EVAL-BACKTRACK" }, { "from": 123, "to": 128, "label": "CASE" }, { "from": 128, "to": 129, "label": "PARALLEL" }, { "from": 128, "to": 130, "label": "PARALLEL" }, { "from": 129, "to": 131, "label": "ONLY EVAL with clause\np(0, 0).\nand substitutionX28 -> 0" }, { "from": 130, "to": 204, "label": "BACKTRACK\nfor clause: p(s(X), X)because of non-unification" }, { "from": 131, "to": 29, "label": "INSTANCE with matching:\nT5 -> T15\nT6 -> 0\nX5 -> X29" }, { "from": 208, "to": 211, "label": "CUT" }, { "from": 210, "to": 255, "label": "ONLY EVAL with clause\nm(X55, X56, X57) :- ','(p(X55, X58), ','(p(X56, X59), m(X58, X59, X57))).\nand substitutionT5 -> T27,\nX55 -> T27,\nT6 -> T28,\nX56 -> T28,\nX5 -> X60,\nX57 -> X60" }, { "from": 211, "to": 212, "label": "SUCCESS" }, { "from": 255, "to": 259, "label": "CASE" }, { "from": 259, "to": 260, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(T27, T28, X5), m(0, X42, 0))" }, { "from": 260, "to": 261, "label": "EVAL with clause\np(s(X65), X65).\nand substitutionX65 -> T31,\nT27 -> s(T31),\nX58 -> T31" }, { "from": 260, "to": 262, "label": "EVAL-BACKTRACK" }, { "from": 261, "to": 264, "label": "CASE" }, { "from": 264, "to": 265, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(s(T31), T28, X5), m(X8, 0, X8))" }, { "from": 265, "to": 266, "label": "EVAL with clause\np(s(X69), X69).\nand substitutionX69 -> T35,\nT28 -> s(T35),\nX59 -> T35" }, { "from": 265, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 266, "to": 29, "label": "INSTANCE with matching:\nT5 -> T31\nT6 -> T35\nX5 -> X60" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: mA(s(X1), 0, X2) :- mA(X1, 0, X2). mA(s(X1), s(X2), X3) :- mA(X1, X2, X3). qB(X1, X2) :- mA(X1, X2, X3). Clauses: mcA(X1, 0, X1). mcA(0, 0, 0). mcA(s(X1), 0, X2) :- mcA(X1, 0, X2). mcA(0, X1, 0). mcA(s(X1), s(X2), X3) :- mcA(X1, X2, X3). Afs: qB(x1, x2) = qB(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: qB_in_2: (b,b) mA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: QB_IN_GG(X1, X2) -> U3_GG(X1, X2, mA_in_gga(X1, X2, X3)) QB_IN_GG(X1, X2) -> MA_IN_GGA(X1, X2, X3) MA_IN_GGA(s(X1), 0, X2) -> U1_GGA(X1, X2, mA_in_gga(X1, 0, X2)) MA_IN_GGA(s(X1), 0, X2) -> MA_IN_GGA(X1, 0, X2) MA_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: mA_in_gga(x1, x2, x3) = mA_in_gga(x1, x2) s(x1) = s(x1) 0 = 0 QB_IN_GG(x1, x2) = QB_IN_GG(x1, x2) U3_GG(x1, x2, x3) = U3_GG(x1, x2, x3) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3) = U1_GGA(x1, x3) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) 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: QB_IN_GG(X1, X2) -> U3_GG(X1, X2, mA_in_gga(X1, X2, X3)) QB_IN_GG(X1, X2) -> MA_IN_GGA(X1, X2, X3) MA_IN_GGA(s(X1), 0, X2) -> U1_GGA(X1, X2, mA_in_gga(X1, 0, X2)) MA_IN_GGA(s(X1), 0, X2) -> MA_IN_GGA(X1, 0, X2) MA_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: mA_in_gga(x1, x2, x3) = mA_in_gga(x1, x2) s(x1) = s(x1) 0 = 0 QB_IN_GG(x1, x2) = QB_IN_GG(x1, x2) U3_GG(x1, x2, x3) = U3_GG(x1, x2, x3) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3) = U1_GGA(x1, x3) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), 0, X2) -> MA_IN_GGA(X1, 0, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), 0) -> MA_IN_GGA(X1, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (10) 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: *MA_IN_GGA(s(X1), 0) -> MA_IN_GGA(X1, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Pi DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (13) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), s(X2)) -> MA_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) 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: *MA_IN_GGA(s(X1), s(X2)) -> MA_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (16) YES