3.69/1.69	YES
3.69/1.71	proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl
3.69/1.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.69/1.71	
3.69/1.71	
3.69/1.71	Left Termination of the query pattern
3.69/1.71	
3.69/1.71	p(g)
3.69/1.71	
3.69/1.71	w.r.t. the given Prolog program could successfully be proven:
3.69/1.71	
3.69/1.71	(0) Prolog
3.69/1.71	(1) PrologToDTProblemTransformerProof [SOUND, 0 ms]
3.69/1.71	(2) TRIPLES
3.69/1.71	(3) TriplesToPiDPProof [SOUND, 0 ms]
3.69/1.71	(4) PiDP
3.69/1.71	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.69/1.71	(6) PiDP
3.69/1.71	(7) PiDPToQDPProof [EQUIVALENT, 0 ms]
3.69/1.71	(8) QDP
3.69/1.71	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.69/1.71	(10) YES
3.69/1.71	
3.69/1.71	
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(0)
3.69/1.71	Obligation:
3.69/1.71	Clauses:
3.69/1.71	
3.69/1.71	p(X) :- ','(q(f(Y)), p(Y)).
3.69/1.71	p(g(X)) :- p(X).
3.69/1.71	q(g(Y)).
3.69/1.71	
3.69/1.71	
3.69/1.71	Query: p(g)
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(1) PrologToDTProblemTransformerProof (SOUND)
3.69/1.71	Built DT problem from termination graph DT10.
3.69/1.71	
3.69/1.71	{
3.69/1.71	    "root": 12,
3.69/1.71	    "program": {
3.69/1.71	        "directives": [],
3.69/1.71	        "clauses": [
3.69/1.71	            [
3.69/1.71	                "(p X)",
3.69/1.71	                "(',' (q (f Y)) (p Y))"
3.69/1.71	            ],
3.69/1.71	            [
3.69/1.71	                "(p (g X))",
3.69/1.71	                "(p X)"
3.69/1.71	            ],
3.69/1.71	            [
3.69/1.71	                "(q (g Y))",
3.69/1.71	                null
3.69/1.71	            ]
3.69/1.71	        ]
3.69/1.71	    },
3.69/1.71	    "graph": {
3.69/1.71	        "nodes": {
3.69/1.71	            "121": {
3.69/1.71	                "goal": [
3.69/1.71	                    {
3.69/1.71	                        "clause": 2,
3.69/1.71	                        "scope": 2,
3.69/1.71	                        "term": "(',' (q (f X3)) (p X3))"
3.69/1.71	                    },
3.69/1.71	                    {
3.69/1.71	                        "clause": -1,
3.69/1.71	                        "scope": 2,
3.69/1.71	                        "term": null
3.69/1.71	                    },
3.69/1.71	                    {
3.69/1.71	                        "clause": 1,
3.69/1.71	                        "scope": 1,
3.69/1.71	                        "term": "(p T3)"
3.69/1.71	                    }
3.69/1.71	                ],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T3"],
3.69/1.71	                    "free": ["X3"],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "132": {
3.69/1.71	                "goal": [],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": [],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "12": {
3.69/1.71	                "goal": [{
3.69/1.71	                    "clause": -1,
3.69/1.71	                    "scope": -1,
3.69/1.71	                    "term": "(p T1)"
3.69/1.71	                }],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T1"],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "122": {
3.69/1.71	                "goal": [
3.69/1.71	                    {
3.69/1.71	                        "clause": -1,
3.69/1.71	                        "scope": 2,
3.69/1.71	                        "term": null
3.69/1.71	                    },
3.69/1.71	                    {
3.69/1.71	                        "clause": 1,
3.69/1.71	                        "scope": 1,
3.69/1.71	                        "term": "(p T3)"
3.69/1.71	                    }
3.69/1.71	                ],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T3"],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "13": {
3.69/1.71	                "goal": [
3.69/1.71	                    {
3.69/1.71	                        "clause": 0,
3.69/1.71	                        "scope": 1,
3.69/1.71	                        "term": "(p T1)"
3.69/1.71	                    },
3.69/1.71	                    {
3.69/1.71	                        "clause": 1,
3.69/1.71	                        "scope": 1,
3.69/1.71	                        "term": "(p T1)"
3.69/1.71	                    }
3.69/1.71	                ],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T1"],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "123": {
3.69/1.71	                "goal": [{
3.69/1.71	                    "clause": 1,
3.69/1.71	                    "scope": 1,
3.69/1.71	                    "term": "(p T3)"
3.69/1.71	                }],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T3"],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "118": {
3.69/1.71	                "goal": [
3.69/1.71	                    {
3.69/1.71	                        "clause": -1,
3.69/1.71	                        "scope": -1,
3.69/1.71	                        "term": "(',' (q (f X3)) (p X3))"
3.69/1.71	                    },
3.69/1.71	                    {
3.69/1.71	                        "clause": 1,
3.69/1.71	                        "scope": 1,
3.69/1.71	                        "term": "(p T3)"
3.69/1.71	                    }
3.69/1.71	                ],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T3"],
3.69/1.71	                    "free": ["X3"],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "129": {
3.69/1.71	                "goal": [{
3.69/1.71	                    "clause": -1,
3.69/1.71	                    "scope": -1,
3.69/1.71	                    "term": "(p T6)"
3.69/1.71	                }],
3.69/1.71	                "kb": {
3.69/1.71	                    "nonunifying": [],
3.69/1.71	                    "intvars": {},
3.69/1.71	                    "arithmetic": {
3.69/1.71	                        "type": "PlainIntegerRelationState",
3.69/1.71	                        "relations": []
3.69/1.71	                    },
3.69/1.71	                    "ground": ["T6"],
3.69/1.71	                    "free": [],
3.69/1.71	                    "exprvars": []
3.69/1.71	                }
3.69/1.71	            },
3.69/1.71	            "type": "Nodes"
3.69/1.71	        },
3.69/1.71	        "edges": [
3.69/1.71	            {
3.69/1.71	                "from": 12,
3.69/1.71	                "to": 13,
3.69/1.71	                "label": "CASE"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 13,
3.69/1.71	                "to": 118,
3.69/1.71	                "label": "ONLY EVAL with clause\np(X2) :- ','(q(f(X3)), p(X3)).\nand substitutionT1 -> T3,\nX2 -> T3"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 118,
3.69/1.71	                "to": 121,
3.69/1.71	                "label": "CASE"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 121,
3.69/1.71	                "to": 122,
3.69/1.71	                "label": "BACKTRACK\nfor clause: q(g(Y))because of non-unification"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 122,
3.69/1.71	                "to": 123,
3.69/1.71	                "label": "FAILURE"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 123,
3.69/1.71	                "to": 129,
3.69/1.71	                "label": "EVAL with clause\np(g(X7)) :- p(X7).\nand substitutionX7 -> T6,\nT3 -> g(T6)"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 123,
3.69/1.71	                "to": 132,
3.69/1.71	                "label": "EVAL-BACKTRACK"
3.69/1.71	            },
3.69/1.71	            {
3.69/1.71	                "from": 129,
3.69/1.71	                "to": 12,
3.69/1.71	                "label": "INSTANCE with matching:\nT1 -> T6"
3.69/1.71	            }
3.69/1.71	        ],
3.69/1.71	        "type": "Graph"
3.69/1.71	    }
3.69/1.71	}
3.69/1.71	
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(2)
3.69/1.71	Obligation:
3.69/1.71	Triples:
3.69/1.71	
3.69/1.71	pA(g(X1)) :- pA(X1).
3.69/1.71	
3.69/1.71	Clauses:
3.69/1.71	
3.69/1.71	pcA(g(X1)) :- pcA(X1).
3.69/1.71	
3.69/1.71	Afs:
3.69/1.71	
3.69/1.71	pA(x1)  =  pA(x1)
3.69/1.71	
3.69/1.71	
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(3) TriplesToPiDPProof (SOUND)
3.69/1.71	We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
3.69/1.71	
3.69/1.71	pA_in_1: (b)
3.69/1.71	
3.69/1.71	Transforming TRIPLES into the following Term Rewriting System:
3.69/1.71	
3.69/1.71	Pi DP problem:
3.69/1.71	The TRS P consists of the following rules:
3.69/1.71	
3.69/1.71	   PA_IN_G(g(X1)) -> U1_G(X1, pA_in_g(X1))
3.69/1.71	   PA_IN_G(g(X1)) -> PA_IN_G(X1)
3.69/1.71	
3.69/1.71	R is empty.
3.69/1.71	Pi is empty.
3.69/1.71	We have to consider all (P,R,Pi)-chains
3.69/1.71	
3.69/1.71	
3.69/1.71	Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES
3.69/1.71	
3.69/1.71	
3.69/1.71	
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(4)
3.69/1.71	Obligation:
3.69/1.71	Pi DP problem:
3.69/1.71	The TRS P consists of the following rules:
3.69/1.71	
3.69/1.71	   PA_IN_G(g(X1)) -> U1_G(X1, pA_in_g(X1))
3.69/1.71	   PA_IN_G(g(X1)) -> PA_IN_G(X1)
3.69/1.71	
3.69/1.71	R is empty.
3.69/1.71	Pi is empty.
3.69/1.71	We have to consider all (P,R,Pi)-chains
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(5) DependencyGraphProof (EQUIVALENT)
3.69/1.71	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(6)
3.69/1.71	Obligation:
3.69/1.71	Pi DP problem:
3.69/1.71	The TRS P consists of the following rules:
3.69/1.71	
3.69/1.71	   PA_IN_G(g(X1)) -> PA_IN_G(X1)
3.69/1.71	
3.69/1.71	R is empty.
3.69/1.71	Pi is empty.
3.69/1.71	We have to consider all (P,R,Pi)-chains
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(7) PiDPToQDPProof (EQUIVALENT)
3.69/1.71	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(8)
3.69/1.71	Obligation:
3.69/1.71	Q DP problem:
3.69/1.71	The TRS P consists of the following rules:
3.69/1.71	
3.69/1.71	   PA_IN_G(g(X1)) -> PA_IN_G(X1)
3.69/1.71	
3.69/1.71	R is empty.
3.69/1.71	Q is empty.
3.69/1.71	We have to consider all (P,Q,R)-chains.
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(9) QDPSizeChangeProof (EQUIVALENT)
3.69/1.71	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. 
3.69/1.71	
3.69/1.71	From the DPs we obtained the following set of size-change graphs:
3.69/1.71	*PA_IN_G(g(X1)) -> PA_IN_G(X1)
3.69/1.71	The graph contains the following edges 1 > 1
3.69/1.71	
3.69/1.71	
3.69/1.71	----------------------------------------
3.69/1.71	
3.69/1.71	(10)
3.69/1.71	YES
3.69/1.73	EOF