3.59/1.71	YES
3.59/1.73	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
3.59/1.73	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.59/1.73	
3.59/1.73	
3.59/1.73	Left Termination of the query pattern
3.59/1.73	
3.59/1.73	f(g)
3.59/1.73	
3.59/1.73	w.r.t. the given Prolog program could successfully be proven:
3.59/1.73	
3.59/1.73	(0) Prolog
3.59/1.73	(1) PrologToDTProblemTransformerProof [SOUND, 0 ms]
3.59/1.73	(2) TRIPLES
3.59/1.73	(3) TriplesToPiDPProof [SOUND, 0 ms]
3.59/1.73	(4) PiDP
3.59/1.73	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.59/1.73	(6) PiDP
3.59/1.73	(7) PiDPToQDPProof [EQUIVALENT, 0 ms]
3.59/1.73	(8) QDP
3.59/1.73	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.59/1.73	(10) YES
3.59/1.73	
3.59/1.73	
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(0)
3.59/1.73	Obligation:
3.59/1.73	Clauses:
3.59/1.73	
3.59/1.73	f(X) :- g(s(s(s(X)))).
3.59/1.73	f(s(X)) :- f(X).
3.59/1.73	g(s(s(s(s(X))))) :- f(X).
3.59/1.73	
3.59/1.73	
3.59/1.73	Query: f(g)
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(1) PrologToDTProblemTransformerProof (SOUND)
3.59/1.73	Built DT problem from termination graph DT10.
3.59/1.73	
3.59/1.73	{
3.59/1.73	    "root": 9,
3.59/1.73	    "program": {
3.59/1.73	        "directives": [],
3.59/1.73	        "clauses": [
3.59/1.73	            [
3.59/1.73	                "(f X)",
3.59/1.73	                "(g (s (s (s X))))"
3.59/1.73	            ],
3.59/1.73	            [
3.59/1.73	                "(f (s X))",
3.59/1.73	                "(f X)"
3.59/1.73	            ],
3.59/1.73	            [
3.59/1.73	                "(g (s (s (s (s X)))))",
3.59/1.73	                "(f X)"
3.59/1.73	            ]
3.59/1.73	        ]
3.59/1.73	    },
3.59/1.73	    "graph": {
3.59/1.73	        "nodes": {
3.59/1.73	            "99": {
3.59/1.73	                "goal": [{
3.59/1.73	                    "clause": 1,
3.59/1.73	                    "scope": 1,
3.59/1.73	                    "term": "(f T3)"
3.59/1.73	                }],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T3"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "100": {
3.59/1.73	                "goal": [{
3.59/1.73	                    "clause": -1,
3.59/1.73	                    "scope": -1,
3.59/1.73	                    "term": "(f T12)"
3.59/1.73	                }],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T12"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "101": {
3.59/1.73	                "goal": [],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": [],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "36": {
3.59/1.73	                "goal": [
3.59/1.73	                    {
3.59/1.73	                        "clause": -1,
3.59/1.73	                        "scope": -1,
3.59/1.73	                        "term": "(g (s (s (s T3))))"
3.59/1.73	                    },
3.59/1.73	                    {
3.59/1.73	                        "clause": 1,
3.59/1.73	                        "scope": 1,
3.59/1.73	                        "term": "(f T3)"
3.59/1.73	                    }
3.59/1.73	                ],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T3"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "38": {
3.59/1.73	                "goal": [
3.59/1.73	                    {
3.59/1.73	                        "clause": 2,
3.59/1.73	                        "scope": 2,
3.59/1.73	                        "term": "(g (s (s (s T3))))"
3.59/1.73	                    },
3.59/1.73	                    {
3.59/1.73	                        "clause": -1,
3.59/1.73	                        "scope": 2,
3.59/1.73	                        "term": null
3.59/1.73	                    },
3.59/1.73	                    {
3.59/1.73	                        "clause": 1,
3.59/1.73	                        "scope": 1,
3.59/1.73	                        "term": "(f T3)"
3.59/1.73	                    }
3.59/1.73	                ],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T3"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "9": {
3.59/1.73	                "goal": [{
3.59/1.73	                    "clause": -1,
3.59/1.73	                    "scope": -1,
3.59/1.73	                    "term": "(f T1)"
3.59/1.73	                }],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T1"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "type": "Nodes",
3.59/1.73	            "95": {
3.59/1.73	                "goal": [{
3.59/1.73	                    "clause": 2,
3.59/1.73	                    "scope": 2,
3.59/1.73	                    "term": "(g (s (s (s T3))))"
3.59/1.73	                }],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T3"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "96": {
3.59/1.73	                "goal": [
3.59/1.73	                    {
3.59/1.73	                        "clause": -1,
3.59/1.73	                        "scope": 2,
3.59/1.73	                        "term": null
3.59/1.73	                    },
3.59/1.73	                    {
3.59/1.73	                        "clause": 1,
3.59/1.73	                        "scope": 1,
3.59/1.73	                        "term": "(f T3)"
3.59/1.73	                    }
3.59/1.73	                ],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T3"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "97": {
3.59/1.73	                "goal": [{
3.59/1.73	                    "clause": -1,
3.59/1.73	                    "scope": -1,
3.59/1.73	                    "term": "(f T8)"
3.59/1.73	                }],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T8"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "10": {
3.59/1.73	                "goal": [
3.59/1.73	                    {
3.59/1.73	                        "clause": 0,
3.59/1.73	                        "scope": 1,
3.59/1.73	                        "term": "(f T1)"
3.59/1.73	                    },
3.59/1.73	                    {
3.59/1.73	                        "clause": 1,
3.59/1.73	                        "scope": 1,
3.59/1.73	                        "term": "(f T1)"
3.59/1.73	                    }
3.59/1.73	                ],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": ["T1"],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            },
3.59/1.73	            "98": {
3.59/1.73	                "goal": [],
3.59/1.73	                "kb": {
3.59/1.73	                    "nonunifying": [],
3.59/1.73	                    "intvars": {},
3.59/1.73	                    "arithmetic": {
3.59/1.73	                        "type": "PlainIntegerRelationState",
3.59/1.73	                        "relations": []
3.59/1.73	                    },
3.59/1.73	                    "ground": [],
3.59/1.73	                    "free": [],
3.59/1.73	                    "exprvars": []
3.59/1.73	                }
3.59/1.73	            }
3.59/1.73	        },
3.59/1.73	        "edges": [
3.59/1.73	            {
3.59/1.73	                "from": 9,
3.59/1.73	                "to": 10,
3.59/1.73	                "label": "CASE"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 10,
3.59/1.73	                "to": 36,
3.59/1.73	                "label": "ONLY EVAL with clause\nf(X2) :- g(s(s(s(X2)))).\nand substitutionT1 -> T3,\nX2 -> T3"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 36,
3.59/1.73	                "to": 38,
3.59/1.73	                "label": "CASE"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 38,
3.59/1.73	                "to": 95,
3.59/1.73	                "label": "PARALLEL"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 38,
3.59/1.73	                "to": 96,
3.59/1.73	                "label": "PARALLEL"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 95,
3.59/1.73	                "to": 97,
3.59/1.73	                "label": "EVAL with clause\ng(s(s(s(s(X7))))) :- f(X7).\nand substitutionX7 -> T8,\nT3 -> s(T8)"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 95,
3.59/1.73	                "to": 98,
3.59/1.73	                "label": "EVAL-BACKTRACK"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 96,
3.59/1.73	                "to": 99,
3.59/1.73	                "label": "FAILURE"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 97,
3.59/1.73	                "to": 9,
3.59/1.73	                "label": "INSTANCE with matching:\nT1 -> T8"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 99,
3.59/1.73	                "to": 100,
3.59/1.73	                "label": "EVAL with clause\nf(s(X11)) :- f(X11).\nand substitutionX11 -> T12,\nT3 -> s(T12)"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 99,
3.59/1.73	                "to": 101,
3.59/1.73	                "label": "EVAL-BACKTRACK"
3.59/1.73	            },
3.59/1.73	            {
3.59/1.73	                "from": 100,
3.59/1.73	                "to": 9,
3.59/1.73	                "label": "INSTANCE with matching:\nT1 -> T12"
3.59/1.73	            }
3.59/1.73	        ],
3.59/1.73	        "type": "Graph"
3.59/1.73	    }
3.59/1.73	}
3.59/1.73	
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(2)
3.59/1.73	Obligation:
3.59/1.73	Triples:
3.59/1.73	
3.59/1.73	fA(s(X1)) :- fA(X1).
3.59/1.73	fA(s(X1)) :- fA(X1).
3.59/1.73	
3.59/1.73	Clauses:
3.59/1.73	
3.59/1.73	fcA(s(X1)) :- fcA(X1).
3.59/1.73	fcA(s(X1)) :- fcA(X1).
3.59/1.73	
3.59/1.73	Afs:
3.59/1.73	
3.59/1.73	fA(x1)  =  fA(x1)
3.59/1.73	
3.59/1.73	
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(3) TriplesToPiDPProof (SOUND)
3.59/1.73	We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
3.59/1.73	
3.59/1.73	fA_in_1: (b)
3.59/1.73	
3.59/1.73	Transforming TRIPLES into the following Term Rewriting System:
3.59/1.73	
3.59/1.73	Pi DP problem:
3.59/1.73	The TRS P consists of the following rules:
3.59/1.73	
3.59/1.73	   FA_IN_G(s(X1)) -> U1_G(X1, fA_in_g(X1))
3.59/1.73	   FA_IN_G(s(X1)) -> FA_IN_G(X1)
3.59/1.73	
3.59/1.73	R is empty.
3.59/1.73	Pi is empty.
3.59/1.73	We have to consider all (P,R,Pi)-chains
3.59/1.73	
3.59/1.73	
3.59/1.73	Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES
3.59/1.73	
3.59/1.73	
3.59/1.73	
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(4)
3.59/1.73	Obligation:
3.59/1.73	Pi DP problem:
3.59/1.73	The TRS P consists of the following rules:
3.59/1.73	
3.59/1.73	   FA_IN_G(s(X1)) -> U1_G(X1, fA_in_g(X1))
3.59/1.73	   FA_IN_G(s(X1)) -> FA_IN_G(X1)
3.59/1.73	
3.59/1.73	R is empty.
3.59/1.73	Pi is empty.
3.59/1.73	We have to consider all (P,R,Pi)-chains
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(5) DependencyGraphProof (EQUIVALENT)
3.59/1.73	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(6)
3.59/1.73	Obligation:
3.59/1.73	Pi DP problem:
3.59/1.73	The TRS P consists of the following rules:
3.59/1.73	
3.59/1.73	   FA_IN_G(s(X1)) -> FA_IN_G(X1)
3.59/1.73	
3.59/1.73	R is empty.
3.59/1.73	Pi is empty.
3.59/1.73	We have to consider all (P,R,Pi)-chains
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(7) PiDPToQDPProof (EQUIVALENT)
3.59/1.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(8)
3.59/1.73	Obligation:
3.59/1.73	Q DP problem:
3.59/1.73	The TRS P consists of the following rules:
3.59/1.73	
3.59/1.73	   FA_IN_G(s(X1)) -> FA_IN_G(X1)
3.59/1.73	
3.59/1.73	R is empty.
3.59/1.73	Q is empty.
3.59/1.73	We have to consider all (P,Q,R)-chains.
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(9) QDPSizeChangeProof (EQUIVALENT)
3.59/1.73	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.59/1.73	
3.59/1.73	From the DPs we obtained the following set of size-change graphs:
3.59/1.73	*FA_IN_G(s(X1)) -> FA_IN_G(X1)
3.59/1.73	The graph contains the following edges 1 > 1
3.59/1.73	
3.59/1.73	
3.59/1.73	----------------------------------------
3.59/1.73	
3.59/1.73	(10)
3.59/1.73	YES
3.59/1.76	EOF