4.64/2.00	YES
4.64/2.00	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
4.64/2.00	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.64/2.00	
4.64/2.00	
4.64/2.00	Left Termination of the query pattern
4.64/2.00	
4.64/2.00	avg(g,g,a)
4.64/2.00	
4.64/2.00	w.r.t. the given Prolog program could successfully be proven:
4.64/2.00	
4.64/2.00	(0) Prolog
4.64/2.00	(1) PrologToPiTRSProof [SOUND, 0 ms]
4.64/2.00	(2) PiTRS
4.64/2.00	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
4.64/2.00	(4) PiDP
4.64/2.00	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
4.64/2.00	(6) PiDP
4.64/2.00	(7) UsableRulesProof [EQUIVALENT, 0 ms]
4.64/2.00	(8) PiDP
4.64/2.00	(9) PiDPToQDPProof [SOUND, 0 ms]
4.64/2.00	(10) QDP
4.64/2.00	(11) MRRProof [EQUIVALENT, 17 ms]
4.64/2.00	(12) QDP
4.64/2.00	(13) PisEmptyProof [EQUIVALENT, 0 ms]
4.64/2.00	(14) YES
4.64/2.00	
4.64/2.00	
4.64/2.00	----------------------------------------
4.64/2.00	
4.64/2.00	(0)
4.64/2.00	Obligation:
4.64/2.00	Clauses:
4.64/2.00	
4.64/2.00	avg(s(X), Y, Z) :- avg(X, s(Y), Z).
4.64/2.00	avg(X, s(s(s(Y))), s(Z)) :- avg(s(X), Y, Z).
4.64/2.00	avg(0, 0, 0).
4.64/2.00	avg(0, s(0), 0).
4.64/2.00	avg(0, s(s(0)), s(0)).
4.64/2.00	
4.64/2.00	
4.64/2.00	Query: avg(g,g,a)
4.64/2.00	----------------------------------------
4.64/2.00	
4.64/2.00	(1) PrologToPiTRSProof (SOUND)
4.64/2.00	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
4.64/2.00	
4.64/2.00	avg_in_3: (b,b,f)
4.64/2.00	
4.64/2.00	Transforming Prolog into the following Term Rewriting System:
4.64/2.00	
4.64/2.00	Pi-finite rewrite system:
4.64/2.00	The TRS R consists of the following rules:
4.64/2.00	
4.64/2.00	   avg_in_gga(s(X), Y, Z) -> U1_gga(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.00	   avg_in_gga(X, s(s(s(Y))), s(Z)) -> U2_gga(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.00	   avg_in_gga(0, 0, 0) -> avg_out_gga(0, 0, 0)
4.64/2.00	   avg_in_gga(0, s(0), 0) -> avg_out_gga(0, s(0), 0)
4.64/2.00	   avg_in_gga(0, s(s(0)), s(0)) -> avg_out_gga(0, s(s(0)), s(0))
4.64/2.00	   U2_gga(X, Y, Z, avg_out_gga(s(X), Y, Z)) -> avg_out_gga(X, s(s(s(Y))), s(Z))
4.64/2.00	   U1_gga(X, Y, Z, avg_out_gga(X, s(Y), Z)) -> avg_out_gga(s(X), Y, Z)
4.64/2.00	
4.64/2.00	The argument filtering Pi contains the following mapping:
4.64/2.00	avg_in_gga(x1, x2, x3)  =  avg_in_gga(x1, x2)
4.64/2.00	
4.64/2.00	s(x1)  =  s(x1)
4.64/2.00	
4.64/2.00	U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
4.64/2.00	
4.64/2.00	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
4.64/2.00	
4.64/2.00	0  =  0
4.64/2.00	
4.64/2.00	avg_out_gga(x1, x2, x3)  =  avg_out_gga(x3)
4.64/2.00	
4.64/2.00	
4.64/2.00	
4.64/2.00	
4.64/2.00	
4.64/2.00	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
4.64/2.00	
4.64/2.00	
4.64/2.00	
4.64/2.00	----------------------------------------
4.64/2.00	
4.64/2.01	(2)
4.64/2.01	Obligation:
4.64/2.01	Pi-finite rewrite system:
4.64/2.01	The TRS R consists of the following rules:
4.64/2.01	
4.64/2.01	   avg_in_gga(s(X), Y, Z) -> U1_gga(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   avg_in_gga(X, s(s(s(Y))), s(Z)) -> U2_gga(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   avg_in_gga(0, 0, 0) -> avg_out_gga(0, 0, 0)
4.64/2.01	   avg_in_gga(0, s(0), 0) -> avg_out_gga(0, s(0), 0)
4.64/2.01	   avg_in_gga(0, s(s(0)), s(0)) -> avg_out_gga(0, s(s(0)), s(0))
4.64/2.01	   U2_gga(X, Y, Z, avg_out_gga(s(X), Y, Z)) -> avg_out_gga(X, s(s(s(Y))), s(Z))
4.64/2.01	   U1_gga(X, Y, Z, avg_out_gga(X, s(Y), Z)) -> avg_out_gga(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The argument filtering Pi contains the following mapping:
4.64/2.01	avg_in_gga(x1, x2, x3)  =  avg_in_gga(x1, x2)
4.64/2.01	
4.64/2.01	s(x1)  =  s(x1)
4.64/2.01	
4.64/2.01	U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
4.64/2.01	
4.64/2.01	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
4.64/2.01	
4.64/2.01	0  =  0
4.64/2.01	
4.64/2.01	avg_out_gga(x1, x2, x3)  =  avg_out_gga(x3)
4.64/2.01	
4.64/2.01	
4.64/2.01	
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(3) DependencyPairsProof (EQUIVALENT)
4.64/2.01	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
4.64/2.01	Pi DP problem:
4.64/2.01	The TRS P consists of the following rules:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> U1_GGA(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> AVG_IN_GGA(X, s(Y), Z)
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> U2_GGA(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> AVG_IN_GGA(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The TRS R consists of the following rules:
4.64/2.01	
4.64/2.01	   avg_in_gga(s(X), Y, Z) -> U1_gga(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   avg_in_gga(X, s(s(s(Y))), s(Z)) -> U2_gga(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   avg_in_gga(0, 0, 0) -> avg_out_gga(0, 0, 0)
4.64/2.01	   avg_in_gga(0, s(0), 0) -> avg_out_gga(0, s(0), 0)
4.64/2.01	   avg_in_gga(0, s(s(0)), s(0)) -> avg_out_gga(0, s(s(0)), s(0))
4.64/2.01	   U2_gga(X, Y, Z, avg_out_gga(s(X), Y, Z)) -> avg_out_gga(X, s(s(s(Y))), s(Z))
4.64/2.01	   U1_gga(X, Y, Z, avg_out_gga(X, s(Y), Z)) -> avg_out_gga(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The argument filtering Pi contains the following mapping:
4.64/2.01	avg_in_gga(x1, x2, x3)  =  avg_in_gga(x1, x2)
4.64/2.01	
4.64/2.01	s(x1)  =  s(x1)
4.64/2.01	
4.64/2.01	U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
4.64/2.01	
4.64/2.01	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
4.64/2.01	
4.64/2.01	0  =  0
4.64/2.01	
4.64/2.01	avg_out_gga(x1, x2, x3)  =  avg_out_gga(x3)
4.64/2.01	
4.64/2.01	AVG_IN_GGA(x1, x2, x3)  =  AVG_IN_GGA(x1, x2)
4.64/2.01	
4.64/2.01	U1_GGA(x1, x2, x3, x4)  =  U1_GGA(x4)
4.64/2.01	
4.64/2.01	U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
4.64/2.01	
4.64/2.01	
4.64/2.01	We have to consider all (P,R,Pi)-chains
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(4)
4.64/2.01	Obligation:
4.64/2.01	Pi DP problem:
4.64/2.01	The TRS P consists of the following rules:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> U1_GGA(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> AVG_IN_GGA(X, s(Y), Z)
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> U2_GGA(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> AVG_IN_GGA(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The TRS R consists of the following rules:
4.64/2.01	
4.64/2.01	   avg_in_gga(s(X), Y, Z) -> U1_gga(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   avg_in_gga(X, s(s(s(Y))), s(Z)) -> U2_gga(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   avg_in_gga(0, 0, 0) -> avg_out_gga(0, 0, 0)
4.64/2.01	   avg_in_gga(0, s(0), 0) -> avg_out_gga(0, s(0), 0)
4.64/2.01	   avg_in_gga(0, s(s(0)), s(0)) -> avg_out_gga(0, s(s(0)), s(0))
4.64/2.01	   U2_gga(X, Y, Z, avg_out_gga(s(X), Y, Z)) -> avg_out_gga(X, s(s(s(Y))), s(Z))
4.64/2.01	   U1_gga(X, Y, Z, avg_out_gga(X, s(Y), Z)) -> avg_out_gga(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The argument filtering Pi contains the following mapping:
4.64/2.01	avg_in_gga(x1, x2, x3)  =  avg_in_gga(x1, x2)
4.64/2.01	
4.64/2.01	s(x1)  =  s(x1)
4.64/2.01	
4.64/2.01	U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
4.64/2.01	
4.64/2.01	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
4.64/2.01	
4.64/2.01	0  =  0
4.64/2.01	
4.64/2.01	avg_out_gga(x1, x2, x3)  =  avg_out_gga(x3)
4.64/2.01	
4.64/2.01	AVG_IN_GGA(x1, x2, x3)  =  AVG_IN_GGA(x1, x2)
4.64/2.01	
4.64/2.01	U1_GGA(x1, x2, x3, x4)  =  U1_GGA(x4)
4.64/2.01	
4.64/2.01	U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
4.64/2.01	
4.64/2.01	
4.64/2.01	We have to consider all (P,R,Pi)-chains
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(5) DependencyGraphProof (EQUIVALENT)
4.64/2.01	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(6)
4.64/2.01	Obligation:
4.64/2.01	Pi DP problem:
4.64/2.01	The TRS P consists of the following rules:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> AVG_IN_GGA(s(X), Y, Z)
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> AVG_IN_GGA(X, s(Y), Z)
4.64/2.01	
4.64/2.01	The TRS R consists of the following rules:
4.64/2.01	
4.64/2.01	   avg_in_gga(s(X), Y, Z) -> U1_gga(X, Y, Z, avg_in_gga(X, s(Y), Z))
4.64/2.01	   avg_in_gga(X, s(s(s(Y))), s(Z)) -> U2_gga(X, Y, Z, avg_in_gga(s(X), Y, Z))
4.64/2.01	   avg_in_gga(0, 0, 0) -> avg_out_gga(0, 0, 0)
4.64/2.01	   avg_in_gga(0, s(0), 0) -> avg_out_gga(0, s(0), 0)
4.64/2.01	   avg_in_gga(0, s(s(0)), s(0)) -> avg_out_gga(0, s(s(0)), s(0))
4.64/2.01	   U2_gga(X, Y, Z, avg_out_gga(s(X), Y, Z)) -> avg_out_gga(X, s(s(s(Y))), s(Z))
4.64/2.01	   U1_gga(X, Y, Z, avg_out_gga(X, s(Y), Z)) -> avg_out_gga(s(X), Y, Z)
4.64/2.01	
4.64/2.01	The argument filtering Pi contains the following mapping:
4.64/2.01	avg_in_gga(x1, x2, x3)  =  avg_in_gga(x1, x2)
4.64/2.01	
4.64/2.01	s(x1)  =  s(x1)
4.64/2.01	
4.64/2.01	U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
4.64/2.01	
4.64/2.01	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
4.64/2.01	
4.64/2.01	0  =  0
4.64/2.01	
4.64/2.01	avg_out_gga(x1, x2, x3)  =  avg_out_gga(x3)
4.64/2.01	
4.64/2.01	AVG_IN_GGA(x1, x2, x3)  =  AVG_IN_GGA(x1, x2)
4.64/2.01	
4.64/2.01	
4.64/2.01	We have to consider all (P,R,Pi)-chains
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(7) UsableRulesProof (EQUIVALENT)
4.64/2.01	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(8)
4.64/2.01	Obligation:
4.64/2.01	Pi DP problem:
4.64/2.01	The TRS P consists of the following rules:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y))), s(Z)) -> AVG_IN_GGA(s(X), Y, Z)
4.64/2.01	   AVG_IN_GGA(s(X), Y, Z) -> AVG_IN_GGA(X, s(Y), Z)
4.64/2.01	
4.64/2.01	R is empty.
4.64/2.01	The argument filtering Pi contains the following mapping:
4.64/2.01	s(x1)  =  s(x1)
4.64/2.01	
4.64/2.01	AVG_IN_GGA(x1, x2, x3)  =  AVG_IN_GGA(x1, x2)
4.64/2.01	
4.64/2.01	
4.64/2.01	We have to consider all (P,R,Pi)-chains
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(9) PiDPToQDPProof (SOUND)
4.64/2.01	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(10)
4.64/2.01	Obligation:
4.64/2.01	Q DP problem:
4.64/2.01	The TRS P consists of the following rules:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y)))) -> AVG_IN_GGA(s(X), Y)
4.64/2.01	   AVG_IN_GGA(s(X), Y) -> AVG_IN_GGA(X, s(Y))
4.64/2.01	
4.64/2.01	R is empty.
4.64/2.01	Q is empty.
4.64/2.01	We have to consider all (P,Q,R)-chains.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(11) MRRProof (EQUIVALENT)
4.64/2.01	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
4.64/2.01	
4.64/2.01	Strictly oriented dependency pairs:
4.64/2.01	
4.64/2.01	   AVG_IN_GGA(X, s(s(s(Y)))) -> AVG_IN_GGA(s(X), Y)
4.64/2.01	   AVG_IN_GGA(s(X), Y) -> AVG_IN_GGA(X, s(Y))
4.64/2.01	
4.64/2.01	
4.64/2.01	Used ordering: Polynomial interpretation [POLO]:
4.64/2.01	
4.64/2.01	   POL(AVG_IN_GGA(x_1, x_2)) = 2*x_1 + x_2
4.64/2.01	   POL(s(x_1)) = 1 + x_1
4.64/2.01	
4.64/2.01	
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(12)
4.64/2.01	Obligation:
4.64/2.01	Q DP problem:
4.64/2.01	P is empty.
4.64/2.01	R is empty.
4.64/2.01	Q is empty.
4.64/2.01	We have to consider all (P,Q,R)-chains.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(13) PisEmptyProof (EQUIVALENT)
4.64/2.01	The TRS P is empty. Hence, there is no (P,Q,R) chain.
4.64/2.01	----------------------------------------
4.64/2.01	
4.64/2.01	(14)
4.64/2.01	YES
4.64/2.02	EOF