/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Left Termination of the query pattern

p1(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) PiDP
(7) PiDPToQDPProof [EQUIVALENT, 0 ms]
(8) QDP
(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
(10) YES


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

(0)
Obligation:
Clauses:

p1(f(X)) :- p1(X).
p2(f(X)) :- p2(X).


Query: p1(g)
----------------------------------------

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

{
    "root": 2,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(p1 (f X))",
                "(p1 X)"
            ],
            [
                "(p2 (f X))",
                "(p2 X)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "23": {
                "goal": [{
                    "clause": 0,
                    "scope": 2,
                    "term": "(p1 T3)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T3"],
                    "free": [],
                    "exprvars": []
                }
            },
            "2": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(p1 T1)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            },
            "24": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(p1 T6)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T6"],
                    "free": [],
                    "exprvars": []
                }
            },
            "3": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(p1 T1)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            },
            "25": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "16": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(p1 T3)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T3"],
                    "free": [],
                    "exprvars": []
                }
            },
            "17": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "type": "Nodes"
        },
        "edges": [
            {
                "from": 2,
                "to": 3,
                "label": "CASE"
            },
            {
                "from": 3,
                "to": 16,
                "label": "EVAL with clause\np1(f(X2)) :- p1(X2).\nand substitutionX2 -> T3,\nT1 -> f(T3)"
            },
            {
                "from": 3,
                "to": 17,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 16,
                "to": 23,
                "label": "CASE"
            },
            {
                "from": 23,
                "to": 24,
                "label": "EVAL with clause\np1(f(X5)) :- p1(X5).\nand substitutionX5 -> T6,\nT3 -> f(T6)"
            },
            {
                "from": 23,
                "to": 25,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 24,
                "to": 2,
                "label": "INSTANCE with matching:\nT1 -> T6"
            }
        ],
        "type": "Graph"
    }
}

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

(2)
Obligation:
Triples:

p1A(f(f(X1))) :- p1A(X1).

Clauses:

p1cA(f(f(X1))) :- p1cA(X1).

Afs:

p1A(x1)  =  p1A(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:

p1A_in_1: (b)

Transforming TRIPLES into the following Term Rewriting System:

Pi DP problem:
The TRS P consists of the following rules:

   P1A_IN_G(f(f(X1))) -> U1_G(X1, p1A_in_g(X1))
   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)

R is empty.
Pi is empty.
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:

   P1A_IN_G(f(f(X1))) -> U1_G(X1, p1A_in_g(X1))
   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains
----------------------------------------

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
----------------------------------------

(6)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains
----------------------------------------

(7) PiDPToQDPProof (EQUIVALENT)
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:

   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)

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:
*P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
The graph contains the following edges 1 > 1


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

(10)
YES