3.03/1.56	YES
3.41/1.57	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
3.41/1.57	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.41/1.57	
3.41/1.57	
3.41/1.57	Left Termination of the query pattern
3.41/1.57	
3.41/1.57	p(g,a)
3.41/1.57	
3.41/1.57	w.r.t. the given Prolog program could successfully be proven:
3.41/1.57	
3.41/1.57	(0) Prolog
3.41/1.57	(1) PrologToDTProblemTransformerProof [SOUND, 0 ms]
3.41/1.57	(2) TRIPLES
3.41/1.57	(3) TriplesToPiDPProof [SOUND, 0 ms]
3.41/1.57	(4) PiDP
3.41/1.57	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.41/1.57	(6) TRUE
3.41/1.57	
3.41/1.57	
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(0)
3.41/1.57	Obligation:
3.41/1.57	Clauses:
3.41/1.57	
3.41/1.57	p(X, Z) :- ','(q(X, Y), p(Y, Z)).
3.41/1.57	p(X, X).
3.41/1.57	q(a, b).
3.41/1.57	
3.41/1.57	
3.41/1.57	Query: p(g,a)
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(1) PrologToDTProblemTransformerProof (SOUND)
3.41/1.57	Built DT problem from termination graph DT10.
3.41/1.57	
3.41/1.57	{
3.41/1.57	    "root": 81,
3.41/1.57	    "program": {
3.41/1.57	        "directives": [],
3.41/1.57	        "clauses": [
3.41/1.57	            [
3.41/1.57	                "(p X Z)",
3.41/1.57	                "(',' (q X Y) (p Y Z))"
3.41/1.57	            ],
3.41/1.57	            [
3.41/1.57	                "(p X X)",
3.41/1.57	                null
3.41/1.57	            ],
3.41/1.57	            [
3.41/1.57	                "(q (a) (b))",
3.41/1.57	                null
3.41/1.57	            ]
3.41/1.57	        ]
3.41/1.57	    },
3.41/1.57	    "graph": {
3.41/1.57	        "nodes": {
3.41/1.57	            "type": "Nodes",
3.41/1.57	            "112": {
3.41/1.57	                "goal": [{
3.41/1.57	                    "clause": -1,
3.41/1.57	                    "scope": -1,
3.41/1.57	                    "term": "(true)"
3.41/1.57	                }],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": [],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "113": {
3.41/1.57	                "goal": [],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": [],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "114": {
3.41/1.57	                "goal": [],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": [],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "90": {
3.41/1.57	                "goal": [{
3.41/1.57	                    "clause": 2,
3.41/1.57	                    "scope": 2,
3.41/1.57	                    "term": "(',' (q T5 X5) (p X5 T7))"
3.41/1.57	                }],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T5"],
3.41/1.57	                    "free": ["X5"],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "106": {
3.41/1.57	                "goal": [{
3.41/1.57	                    "clause": -1,
3.41/1.57	                    "scope": -1,
3.41/1.57	                    "term": "(p (b) T7)"
3.41/1.57	                }],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": [],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "91": {
3.41/1.57	                "goal": [
3.41/1.57	                    {
3.41/1.57	                        "clause": -1,
3.41/1.57	                        "scope": 2,
3.41/1.57	                        "term": null
3.41/1.57	                    },
3.41/1.57	                    {
3.41/1.57	                        "clause": 1,
3.41/1.57	                        "scope": 1,
3.41/1.57	                        "term": "(p T5 T2)"
3.41/1.57	                    }
3.41/1.57	                ],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T5"],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "107": {
3.41/1.57	                "goal": [],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": [],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "81": {
3.41/1.57	                "goal": [{
3.41/1.57	                    "clause": -1,
3.41/1.57	                    "scope": -1,
3.41/1.57	                    "term": "(p T1 T2)"
3.41/1.57	                }],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T1"],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "108": {
3.41/1.57	                "goal": [{
3.41/1.57	                    "clause": 1,
3.41/1.57	                    "scope": 1,
3.41/1.57	                    "term": "(p T5 T2)"
3.41/1.57	                }],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T5"],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "82": {
3.41/1.57	                "goal": [
3.41/1.57	                    {
3.41/1.57	                        "clause": 0,
3.41/1.57	                        "scope": 1,
3.41/1.57	                        "term": "(p T1 T2)"
3.41/1.57	                    },
3.41/1.57	                    {
3.41/1.57	                        "clause": 1,
3.41/1.57	                        "scope": 1,
3.41/1.57	                        "term": "(p T1 T2)"
3.41/1.57	                    }
3.41/1.57	                ],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T1"],
3.41/1.57	                    "free": [],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "83": {
3.41/1.57	                "goal": [
3.41/1.57	                    {
3.41/1.57	                        "clause": -1,
3.41/1.57	                        "scope": -1,
3.41/1.57	                        "term": "(',' (q T5 X5) (p X5 T7))"
3.41/1.57	                    },
3.41/1.57	                    {
3.41/1.57	                        "clause": 1,
3.41/1.57	                        "scope": 1,
3.41/1.57	                        "term": "(p T5 T2)"
3.41/1.57	                    }
3.41/1.57	                ],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T5"],
3.41/1.57	                    "free": ["X5"],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            },
3.41/1.57	            "86": {
3.41/1.57	                "goal": [
3.41/1.57	                    {
3.41/1.57	                        "clause": 2,
3.41/1.57	                        "scope": 2,
3.41/1.57	                        "term": "(',' (q T5 X5) (p X5 T7))"
3.41/1.57	                    },
3.41/1.57	                    {
3.41/1.57	                        "clause": -1,
3.41/1.57	                        "scope": 2,
3.41/1.57	                        "term": null
3.41/1.57	                    },
3.41/1.57	                    {
3.41/1.57	                        "clause": 1,
3.41/1.57	                        "scope": 1,
3.41/1.57	                        "term": "(p T5 T2)"
3.41/1.57	                    }
3.41/1.57	                ],
3.41/1.57	                "kb": {
3.41/1.57	                    "nonunifying": [],
3.41/1.57	                    "intvars": {},
3.41/1.57	                    "arithmetic": {
3.41/1.57	                        "type": "PlainIntegerRelationState",
3.41/1.57	                        "relations": []
3.41/1.57	                    },
3.41/1.57	                    "ground": ["T5"],
3.41/1.57	                    "free": ["X5"],
3.41/1.57	                    "exprvars": []
3.41/1.57	                }
3.41/1.57	            }
3.41/1.57	        },
3.41/1.57	        "edges": [
3.41/1.57	            {
3.41/1.57	                "from": 81,
3.41/1.57	                "to": 82,
3.41/1.57	                "label": "CASE"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 82,
3.41/1.57	                "to": 83,
3.41/1.57	                "label": "ONLY EVAL with clause\np(X3, X4) :- ','(q(X3, X5), p(X5, X4)).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> T7,\nX4 -> T7,\nT6 -> T7"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 83,
3.41/1.57	                "to": 86,
3.41/1.57	                "label": "CASE"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 86,
3.41/1.57	                "to": 90,
3.41/1.57	                "label": "PARALLEL"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 86,
3.41/1.57	                "to": 91,
3.41/1.57	                "label": "PARALLEL"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 90,
3.41/1.57	                "to": 106,
3.41/1.57	                "label": "EVAL with clause\nq(a, b).\nand substitutionT5 -> a,\nX5 -> b"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 90,
3.41/1.57	                "to": 107,
3.41/1.57	                "label": "EVAL-BACKTRACK"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 91,
3.41/1.57	                "to": 108,
3.41/1.57	                "label": "FAILURE"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 106,
3.41/1.57	                "to": 81,
3.41/1.57	                "label": "INSTANCE with matching:\nT1 -> b\nT2 -> T7"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 108,
3.41/1.57	                "to": 112,
3.41/1.57	                "label": "EVAL with clause\np(X11, X11).\nand substitutionT5 -> T11,\nX11 -> T11,\nT2 -> T11"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 108,
3.41/1.57	                "to": 113,
3.41/1.57	                "label": "EVAL-BACKTRACK"
3.41/1.57	            },
3.41/1.57	            {
3.41/1.57	                "from": 112,
3.41/1.57	                "to": 114,
3.41/1.57	                "label": "SUCCESS"
3.41/1.57	            }
3.41/1.57	        ],
3.41/1.57	        "type": "Graph"
3.41/1.57	    }
3.41/1.57	}
3.41/1.57	
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(2)
3.41/1.57	Obligation:
3.41/1.57	Triples:
3.41/1.57	
3.41/1.57	pA(a, X1) :- pA(b, X1).
3.41/1.57	
3.41/1.57	Clauses:
3.41/1.57	
3.41/1.57	pcA(a, X1) :- pcA(b, X1).
3.41/1.57	pcA(X1, X1).
3.41/1.57	
3.41/1.57	Afs:
3.41/1.57	
3.41/1.57	pA(x1, x2)  =  pA(x1)
3.41/1.57	
3.41/1.57	
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(3) TriplesToPiDPProof (SOUND)
3.41/1.57	We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
3.41/1.57	
3.41/1.57	pA_in_2: (b,f)
3.41/1.57	
3.41/1.57	Transforming TRIPLES into the following Term Rewriting System:
3.41/1.57	
3.41/1.57	Pi DP problem:
3.41/1.57	The TRS P consists of the following rules:
3.41/1.57	
3.41/1.57	   PA_IN_GA(a, X1) -> U1_GA(X1, pA_in_ga(b, X1))
3.41/1.57	   PA_IN_GA(a, X1) -> PA_IN_GA(b, X1)
3.41/1.57	
3.41/1.57	R is empty.
3.41/1.57	The argument filtering Pi contains the following mapping:
3.41/1.57	pA_in_ga(x1, x2)  =  pA_in_ga(x1)
3.41/1.57	
3.41/1.57	a  =  a
3.41/1.57	
3.41/1.57	b  =  b
3.41/1.57	
3.41/1.57	PA_IN_GA(x1, x2)  =  PA_IN_GA(x1)
3.41/1.57	
3.41/1.57	U1_GA(x1, x2)  =  U1_GA(x2)
3.41/1.57	
3.41/1.57	
3.41/1.57	We have to consider all (P,R,Pi)-chains
3.41/1.57	
3.41/1.57	
3.41/1.57	Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES
3.41/1.57	
3.41/1.57	
3.41/1.57	
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(4)
3.41/1.57	Obligation:
3.41/1.57	Pi DP problem:
3.41/1.57	The TRS P consists of the following rules:
3.41/1.57	
3.41/1.57	   PA_IN_GA(a, X1) -> U1_GA(X1, pA_in_ga(b, X1))
3.41/1.57	   PA_IN_GA(a, X1) -> PA_IN_GA(b, X1)
3.41/1.57	
3.41/1.57	R is empty.
3.41/1.57	The argument filtering Pi contains the following mapping:
3.41/1.57	pA_in_ga(x1, x2)  =  pA_in_ga(x1)
3.41/1.57	
3.41/1.57	a  =  a
3.41/1.57	
3.41/1.57	b  =  b
3.41/1.57	
3.41/1.57	PA_IN_GA(x1, x2)  =  PA_IN_GA(x1)
3.41/1.57	
3.41/1.57	U1_GA(x1, x2)  =  U1_GA(x2)
3.41/1.57	
3.41/1.57	
3.41/1.57	We have to consider all (P,R,Pi)-chains
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(5) DependencyGraphProof (EQUIVALENT)
3.41/1.57	The approximation of the Dependency Graph [LOPSTR] contains 0 SCCs with 2 less nodes.
3.41/1.57	----------------------------------------
3.41/1.57	
3.41/1.57	(6)
3.41/1.57	TRUE
3.44/1.61	EOF