3.48/1.73	YES
3.48/1.74	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
3.48/1.74	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.48/1.74	
3.48/1.74	
3.48/1.74	Left Termination of the query pattern
3.48/1.74	
3.48/1.74	p1(g)
3.48/1.74	
3.48/1.74	w.r.t. the given Prolog program could successfully be proven:
3.48/1.74	
3.48/1.74	(0) Prolog
3.48/1.74	(1) PrologToDTProblemTransformerProof [SOUND, 0 ms]
3.48/1.74	(2) TRIPLES
3.48/1.74	(3) TriplesToPiDPProof [SOUND, 0 ms]
3.48/1.74	(4) PiDP
3.48/1.74	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.48/1.74	(6) PiDP
3.48/1.74	(7) PiDPToQDPProof [EQUIVALENT, 0 ms]
3.48/1.74	(8) QDP
3.48/1.74	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.48/1.74	(10) YES
3.48/1.74	
3.48/1.74	
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(0)
3.48/1.74	Obligation:
3.48/1.74	Clauses:
3.48/1.74	
3.48/1.74	p1(f(X)) :- p1(X).
3.48/1.74	p2(f(X)) :- p2(X).
3.48/1.74	
3.48/1.74	
3.48/1.74	Query: p1(g)
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(1) PrologToDTProblemTransformerProof (SOUND)
3.48/1.74	Built DT problem from termination graph DT10.
3.48/1.74	
3.48/1.74	{
3.48/1.74	    "root": 4,
3.48/1.74	    "program": {
3.48/1.74	        "directives": [],
3.48/1.74	        "clauses": [
3.48/1.74	            [
3.48/1.74	                "(p1 (f X))",
3.48/1.74	                "(p1 X)"
3.48/1.74	            ],
3.48/1.74	            [
3.48/1.74	                "(p2 (f X))",
3.48/1.74	                "(p2 X)"
3.48/1.74	            ]
3.48/1.74	        ]
3.48/1.74	    },
3.48/1.74	    "graph": {
3.48/1.74	        "nodes": {
3.48/1.74	            "33": {
3.48/1.74	                "goal": [{
3.48/1.74	                    "clause": 0,
3.48/1.74	                    "scope": 2,
3.48/1.74	                    "term": "(p1 T3)"
3.48/1.74	                }],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": ["T3"],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "34": {
3.48/1.74	                "goal": [{
3.48/1.74	                    "clause": -1,
3.48/1.74	                    "scope": -1,
3.48/1.74	                    "term": "(p1 T6)"
3.48/1.74	                }],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": ["T6"],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "35": {
3.48/1.74	                "goal": [],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": [],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "4": {
3.48/1.74	                "goal": [{
3.48/1.74	                    "clause": -1,
3.48/1.74	                    "scope": -1,
3.48/1.74	                    "term": "(p1 T1)"
3.48/1.74	                }],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": ["T1"],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "7": {
3.48/1.74	                "goal": [{
3.48/1.74	                    "clause": 0,
3.48/1.74	                    "scope": 1,
3.48/1.74	                    "term": "(p1 T1)"
3.48/1.74	                }],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": ["T1"],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "type": "Nodes",
3.48/1.74	            "31": {
3.48/1.74	                "goal": [{
3.48/1.74	                    "clause": -1,
3.48/1.74	                    "scope": -1,
3.48/1.74	                    "term": "(p1 T3)"
3.48/1.74	                }],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": ["T3"],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            },
3.48/1.74	            "32": {
3.48/1.74	                "goal": [],
3.48/1.74	                "kb": {
3.48/1.74	                    "nonunifying": [],
3.48/1.74	                    "intvars": {},
3.48/1.74	                    "arithmetic": {
3.48/1.74	                        "type": "PlainIntegerRelationState",
3.48/1.74	                        "relations": []
3.48/1.74	                    },
3.48/1.74	                    "ground": [],
3.48/1.74	                    "free": [],
3.48/1.74	                    "exprvars": []
3.48/1.74	                }
3.48/1.74	            }
3.48/1.74	        },
3.48/1.74	        "edges": [
3.48/1.74	            {
3.48/1.74	                "from": 4,
3.48/1.74	                "to": 7,
3.48/1.74	                "label": "CASE"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 7,
3.48/1.74	                "to": 31,
3.48/1.74	                "label": "EVAL with clause\np1(f(X2)) :- p1(X2).\nand substitutionX2 -> T3,\nT1 -> f(T3)"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 7,
3.48/1.74	                "to": 32,
3.48/1.74	                "label": "EVAL-BACKTRACK"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 31,
3.48/1.74	                "to": 33,
3.48/1.74	                "label": "CASE"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 33,
3.48/1.74	                "to": 34,
3.48/1.74	                "label": "EVAL with clause\np1(f(X5)) :- p1(X5).\nand substitutionX5 -> T6,\nT3 -> f(T6)"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 33,
3.48/1.74	                "to": 35,
3.48/1.74	                "label": "EVAL-BACKTRACK"
3.48/1.74	            },
3.48/1.74	            {
3.48/1.74	                "from": 34,
3.48/1.74	                "to": 4,
3.48/1.74	                "label": "INSTANCE with matching:\nT1 -> T6"
3.48/1.74	            }
3.48/1.74	        ],
3.48/1.74	        "type": "Graph"
3.48/1.74	    }
3.48/1.74	}
3.48/1.74	
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(2)
3.48/1.74	Obligation:
3.48/1.74	Triples:
3.48/1.74	
3.48/1.74	p1A(f(f(X1))) :- p1A(X1).
3.48/1.74	
3.48/1.74	Clauses:
3.48/1.74	
3.48/1.74	p1cA(f(f(X1))) :- p1cA(X1).
3.48/1.74	
3.48/1.74	Afs:
3.48/1.74	
3.48/1.74	p1A(x1)  =  p1A(x1)
3.48/1.74	
3.48/1.74	
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(3) TriplesToPiDPProof (SOUND)
3.48/1.74	We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
3.48/1.74	
3.48/1.74	p1A_in_1: (b)
3.48/1.74	
3.48/1.74	Transforming TRIPLES into the following Term Rewriting System:
3.48/1.74	
3.48/1.74	Pi DP problem:
3.48/1.74	The TRS P consists of the following rules:
3.48/1.74	
3.48/1.74	   P1A_IN_G(f(f(X1))) -> U1_G(X1, p1A_in_g(X1))
3.48/1.74	   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
3.48/1.74	
3.48/1.74	R is empty.
3.48/1.74	Pi is empty.
3.48/1.74	We have to consider all (P,R,Pi)-chains
3.48/1.74	
3.48/1.74	
3.48/1.74	Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES
3.48/1.74	
3.48/1.74	
3.48/1.74	
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(4)
3.48/1.74	Obligation:
3.48/1.74	Pi DP problem:
3.48/1.74	The TRS P consists of the following rules:
3.48/1.74	
3.48/1.74	   P1A_IN_G(f(f(X1))) -> U1_G(X1, p1A_in_g(X1))
3.48/1.74	   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
3.48/1.74	
3.48/1.74	R is empty.
3.48/1.74	Pi is empty.
3.48/1.74	We have to consider all (P,R,Pi)-chains
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(5) DependencyGraphProof (EQUIVALENT)
3.48/1.74	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(6)
3.48/1.74	Obligation:
3.48/1.74	Pi DP problem:
3.48/1.74	The TRS P consists of the following rules:
3.48/1.74	
3.48/1.74	   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
3.48/1.74	
3.48/1.74	R is empty.
3.48/1.74	Pi is empty.
3.48/1.74	We have to consider all (P,R,Pi)-chains
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(7) PiDPToQDPProof (EQUIVALENT)
3.48/1.74	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(8)
3.48/1.74	Obligation:
3.48/1.74	Q DP problem:
3.48/1.74	The TRS P consists of the following rules:
3.48/1.74	
3.48/1.74	   P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
3.48/1.74	
3.48/1.74	R is empty.
3.48/1.74	Q is empty.
3.48/1.74	We have to consider all (P,Q,R)-chains.
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(9) QDPSizeChangeProof (EQUIVALENT)
3.48/1.74	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.48/1.74	
3.48/1.74	From the DPs we obtained the following set of size-change graphs:
3.48/1.74	*P1A_IN_G(f(f(X1))) -> P1A_IN_G(X1)
3.48/1.74	The graph contains the following edges 1 > 1
3.48/1.74	
3.48/1.74	
3.48/1.74	----------------------------------------
3.48/1.74	
3.48/1.74	(10)
3.48/1.74	YES
3.70/1.76	EOF