/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Left Termination of the query pattern

sum(a,a,g)

w.r.t. the given Prolog program could successfully be proven:

(0) Prolog
(1) PrologToDTProblemTransformerProof [SOUND, 0 ms]
(2) TRIPLES
(3) TPisEmptyProof [EQUIVALENT, 0 ms]
(4) YES


----------------------------------------

(0)
Obligation:
Clauses:

sum(X, Y, Z) :- is(Z, +(X, Y)).
sum(X, Y, Z) :- is(Z, sum(X, Y, Z)).


Query: sum(a,a,g)
----------------------------------------

(1) PrologToDTProblemTransformerProof (SOUND)
Built DT problem from termination graph DT10.

{
    "root": 3,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(sum X Y Z)",
                "(is Z (+ X Y))"
            ],
            [
                "(sum X Y Z)",
                "(is Z (sum X Y Z))"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "23": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(sum T1 T2 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": [{
                            "lhs": {
                                "name": "T12",
                                "type": "PlainIntegerVariable"
                            },
                            "type": "PlainIntegerRelation",
                            "rhs": {
                                "arguments": [
                                    {
                                        "name": "T10",
                                        "type": "PlainIntegerVariable"
                                    },
                                    {
                                        "name": "T11",
                                        "type": "PlainIntegerVariable"
                                    }
                                ],
                                "type": "PlainIntegerOperation",
                                "operation": "+"
                            },
                            "operation": "="
                        }]
                    },
                    "ground": ["T12"],
                    "free": [],
                    "exprvars": [
                        "T12",
                        "T11",
                        "T10"
                    ]
                }
            },
            "3": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(sum T1 T2 T3)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T3"],
                    "free": [],
                    "exprvars": []
                }
            },
            "4": {
                "goal": [
                    {
                        "clause": 0,
                        "scope": 1,
                        "term": "(sum T1 T2 T3)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(sum T1 T2 T3)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T3"],
                    "free": [],
                    "exprvars": []
                }
            },
            "26": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(is T18 (sum T19 T20 T18))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": [
                            {
                                "lhs": {
                                    "name": "T12",
                                    "type": "PlainIntegerVariable"
                                },
                                "type": "PlainIntegerRelation",
                                "rhs": {
                                    "arguments": [
                                        {
                                            "name": "T10",
                                            "type": "PlainIntegerVariable"
                                        },
                                        {
                                            "name": "T11",
                                            "type": "PlainIntegerVariable"
                                        }
                                    ],
                                    "type": "PlainIntegerOperation",
                                    "operation": "+"
                                },
                                "operation": "="
                            },
                            {
                                "lhs": {
                                    "arguments": [
                                        {
                                            "name": "T10",
                                            "type": "PlainIntegerVariable"
                                        },
                                        {
                                            "name": "T11",
                                            "type": "PlainIntegerVariable"
                                        }
                                    ],
                                    "type": "PlainIntegerOperation",
                                    "operation": "+"
                                },
                                "type": "PlainIntegerRelation",
                                "rhs": {
                                    "arguments": [
                                        {
                                            "name": "T10",
                                            "type": "PlainIntegerVariable"
                                        },
                                        {
                                            "name": "T11",
                                            "type": "PlainIntegerVariable"
                                        }
                                    ],
                                    "type": "PlainIntegerOperation",
                                    "operation": "+"
                                },
                                "operation": "="
                            }
                        ]
                    },
                    "ground": ["T18"],
                    "free": [],
                    "exprvars": [
                        "T18",
                        "T12",
                        "T11",
                        "T10"
                    ]
                }
            },
            "27": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "6": {
                "goal": [
                    {
                        "clause": -1,
                        "scope": -1,
                        "term": "(is T9 (+ T10 T11))"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(sum T1 T2 T9)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T9"],
                    "free": [],
                    "exprvars": []
                }
            },
            "28": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(is T26 (sum T27 T28 T26))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T26"],
                    "free": [],
                    "exprvars": [
                        "T11",
                        "T10"
                    ]
                }
            },
            "7": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "29": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "19": {
                "goal": [
                    {
                        "clause": -1,
                        "scope": -1,
                        "term": "(true)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(sum T1 T2 T12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": [{
                            "lhs": {
                                "name": "T12",
                                "type": "PlainIntegerVariable"
                            },
                            "type": "PlainIntegerRelation",
                            "rhs": {
                                "arguments": [
                                    {
                                        "name": "T10",
                                        "type": "PlainIntegerVariable"
                                    },
                                    {
                                        "name": "T11",
                                        "type": "PlainIntegerVariable"
                                    }
                                ],
                                "type": "PlainIntegerOperation",
                                "operation": "+"
                            },
                            "operation": "="
                        }]
                    },
                    "ground": [
                        "T12",
                        "T11",
                        "T10",
                        "T9"
                    ],
                    "free": [],
                    "exprvars": [
                        "T12",
                        "T11",
                        "T10"
                    ]
                }
            },
            "type": "Nodes",
            "21": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(sum T1 T2 T9)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T11",
                        "T10",
                        "T9"
                    ],
                    "free": [],
                    "exprvars": [
                        "T11",
                        "T10"
                    ]
                }
            }
        },
        "edges": [
            {
                "from": 3,
                "to": 4,
                "label": "CASE"
            },
            {
                "from": 4,
                "to": 6,
                "label": "ONLY EVAL with clause\nsum(X4, X5, X6) :- is(X6, +(X4, X5)).\nand substitutionT1 -> T10,\nX4 -> T10,\nT2 -> T11,\nX5 -> T11,\nT3 -> T9,\nX6 -> T9,\nT7 -> T10,\nT8 -> T11"
            },
            {
                "from": 6,
                "to": 7,
                "label": "IS ERROR"
            },
            {
                "from": 6,
                "to": 19,
                "label": "\nT9 -> T12"
            },
            {
                "from": 6,
                "to": 21,
                "label": "IS FAIL"
            },
            {
                "from": 19,
                "to": 23,
                "label": "SUCCESS"
            },
            {
                "from": 21,
                "to": 28,
                "label": "ONLY EVAL with clause\nsum(X16, X17, X18) :- is(X18, sum(X16, X17, X18)).\nand substitutionT1 -> T27,\nX16 -> T27,\nT2 -> T28,\nX17 -> T28,\nT9 -> T26,\nX18 -> T26,\nT24 -> T27,\nT25 -> T28"
            },
            {
                "from": 23,
                "to": 26,
                "label": "ONLY EVAL with clause\nsum(X10, X11, X12) :- is(X12, sum(X10, X11, X12)).\nand substitutionT1 -> T19,\nX10 -> T19,\nT2 -> T20,\nX11 -> T20,\nT12 -> T18,\nX12 -> T18,\nT16 -> T19,\nT17 -> T20"
            },
            {
                "from": 26,
                "to": 27,
                "label": "IS ERROR"
            },
            {
                "from": 28,
                "to": 29,
                "label": "IS ERROR"
            }
        ],
        "type": "Graph"
    }
}

----------------------------------------

(2)
Obligation:
Triples:


Clauses:


Afs:


----------------------------------------

(3) TPisEmptyProof (EQUIVALENT)
There are no more dependency triples. Hence, the dependency triple problem trivially terminates.
----------------------------------------

(4)
YES