4.37/2.04	YES
4.60/2.05	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
4.60/2.05	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.60/2.05	
4.60/2.05	
4.60/2.05	Left Termination of the query pattern
4.60/2.05	
4.60/2.05	f(g,a,a)
4.60/2.05	
4.60/2.05	w.r.t. the given Prolog program could successfully be proven:
4.60/2.05	
4.60/2.05	(0) Prolog
4.60/2.05	(1) PrologToPiTRSProof [SOUND, 0 ms]
4.60/2.05	(2) PiTRS
4.60/2.05	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
4.60/2.05	(4) PiDP
4.60/2.05	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
4.60/2.05	(6) PiDP
4.60/2.05	(7) PiDPToQDPProof [SOUND, 0 ms]
4.60/2.05	(8) QDP
4.60/2.05	(9) UsableRulesReductionPairsProof [EQUIVALENT, 14 ms]
4.60/2.05	(10) QDP
4.60/2.05	(11) DependencyGraphProof [EQUIVALENT, 0 ms]
4.60/2.05	(12) TRUE
4.60/2.05	
4.60/2.05	
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(0)
4.60/2.05	Obligation:
4.60/2.05	Clauses:
4.60/2.05	
4.60/2.05	f(0, Y, 0).
4.60/2.05	f(s(X), Y, Z) :- ','(f(X, Y, U), f(U, Y, Z)).
4.60/2.05	
4.60/2.05	
4.60/2.05	Query: f(g,a,a)
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(1) PrologToPiTRSProof (SOUND)
4.60/2.05	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
4.60/2.05	
4.60/2.05	f_in_3: (b,f,f)
4.60/2.05	
4.60/2.05	Transforming Prolog into the following Term Rewriting System:
4.60/2.05	
4.60/2.05	Pi-finite rewrite system:
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0, Y, 0) -> f_out_gaa(0, Y, 0)
4.60/2.05	   f_in_gaa(s(X), Y, Z) -> U1_gaa(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   U1_gaa(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_gaa(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U2_gaa(X, Y, Z, U, f_out_gaa(U, Y, Z)) -> f_out_gaa(s(X), Y, Z)
4.60/2.05	
4.60/2.05	The argument filtering Pi contains the following mapping:
4.60/2.05	f_in_gaa(x1, x2, x3)  =  f_in_gaa(x1)
4.60/2.05	
4.60/2.05	0  =  0
4.60/2.05	
4.60/2.05	f_out_gaa(x1, x2, x3)  =  f_out_gaa(x3)
4.60/2.05	
4.60/2.05	s(x1)  =  s(x1)
4.60/2.05	
4.60/2.05	U1_gaa(x1, x2, x3, x4)  =  U1_gaa(x4)
4.60/2.05	
4.60/2.05	U2_gaa(x1, x2, x3, x4, x5)  =  U2_gaa(x5)
4.60/2.05	
4.60/2.05	
4.60/2.05	
4.60/2.05	
4.60/2.05	
4.60/2.05	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
4.60/2.05	
4.60/2.05	
4.60/2.05	
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(2)
4.60/2.05	Obligation:
4.60/2.05	Pi-finite rewrite system:
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0, Y, 0) -> f_out_gaa(0, Y, 0)
4.60/2.05	   f_in_gaa(s(X), Y, Z) -> U1_gaa(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   U1_gaa(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_gaa(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U2_gaa(X, Y, Z, U, f_out_gaa(U, Y, Z)) -> f_out_gaa(s(X), Y, Z)
4.60/2.05	
4.60/2.05	The argument filtering Pi contains the following mapping:
4.60/2.05	f_in_gaa(x1, x2, x3)  =  f_in_gaa(x1)
4.60/2.05	
4.60/2.05	0  =  0
4.60/2.05	
4.60/2.05	f_out_gaa(x1, x2, x3)  =  f_out_gaa(x3)
4.60/2.05	
4.60/2.05	s(x1)  =  s(x1)
4.60/2.05	
4.60/2.05	U1_gaa(x1, x2, x3, x4)  =  U1_gaa(x4)
4.60/2.05	
4.60/2.05	U2_gaa(x1, x2, x3, x4, x5)  =  U2_gaa(x5)
4.60/2.05	
4.60/2.05	
4.60/2.05	
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(3) DependencyPairsProof (EQUIVALENT)
4.60/2.05	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
4.60/2.05	Pi DP problem:
4.60/2.05	The TRS P consists of the following rules:
4.60/2.05	
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> U1_GAA(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> F_IN_GAA(X, Y, U)
4.60/2.05	   U1_GAA(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_GAA(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U1_GAA(X, Y, Z, f_out_gaa(X, Y, U)) -> F_IN_GAA(U, Y, Z)
4.60/2.05	
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0, Y, 0) -> f_out_gaa(0, Y, 0)
4.60/2.05	   f_in_gaa(s(X), Y, Z) -> U1_gaa(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   U1_gaa(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_gaa(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U2_gaa(X, Y, Z, U, f_out_gaa(U, Y, Z)) -> f_out_gaa(s(X), Y, Z)
4.60/2.05	
4.60/2.05	The argument filtering Pi contains the following mapping:
4.60/2.05	f_in_gaa(x1, x2, x3)  =  f_in_gaa(x1)
4.60/2.05	
4.60/2.05	0  =  0
4.60/2.05	
4.60/2.05	f_out_gaa(x1, x2, x3)  =  f_out_gaa(x3)
4.60/2.05	
4.60/2.05	s(x1)  =  s(x1)
4.60/2.05	
4.60/2.05	U1_gaa(x1, x2, x3, x4)  =  U1_gaa(x4)
4.60/2.05	
4.60/2.05	U2_gaa(x1, x2, x3, x4, x5)  =  U2_gaa(x5)
4.60/2.05	
4.60/2.05	F_IN_GAA(x1, x2, x3)  =  F_IN_GAA(x1)
4.60/2.05	
4.60/2.05	U1_GAA(x1, x2, x3, x4)  =  U1_GAA(x4)
4.60/2.05	
4.60/2.05	U2_GAA(x1, x2, x3, x4, x5)  =  U2_GAA(x5)
4.60/2.05	
4.60/2.05	
4.60/2.05	We have to consider all (P,R,Pi)-chains
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(4)
4.60/2.05	Obligation:
4.60/2.05	Pi DP problem:
4.60/2.05	The TRS P consists of the following rules:
4.60/2.05	
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> U1_GAA(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> F_IN_GAA(X, Y, U)
4.60/2.05	   U1_GAA(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_GAA(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U1_GAA(X, Y, Z, f_out_gaa(X, Y, U)) -> F_IN_GAA(U, Y, Z)
4.60/2.05	
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0, Y, 0) -> f_out_gaa(0, Y, 0)
4.60/2.05	   f_in_gaa(s(X), Y, Z) -> U1_gaa(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   U1_gaa(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_gaa(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U2_gaa(X, Y, Z, U, f_out_gaa(U, Y, Z)) -> f_out_gaa(s(X), Y, Z)
4.60/2.05	
4.60/2.05	The argument filtering Pi contains the following mapping:
4.60/2.05	f_in_gaa(x1, x2, x3)  =  f_in_gaa(x1)
4.60/2.05	
4.60/2.05	0  =  0
4.60/2.05	
4.60/2.05	f_out_gaa(x1, x2, x3)  =  f_out_gaa(x3)
4.60/2.05	
4.60/2.05	s(x1)  =  s(x1)
4.60/2.05	
4.60/2.05	U1_gaa(x1, x2, x3, x4)  =  U1_gaa(x4)
4.60/2.05	
4.60/2.05	U2_gaa(x1, x2, x3, x4, x5)  =  U2_gaa(x5)
4.60/2.05	
4.60/2.05	F_IN_GAA(x1, x2, x3)  =  F_IN_GAA(x1)
4.60/2.05	
4.60/2.05	U1_GAA(x1, x2, x3, x4)  =  U1_GAA(x4)
4.60/2.05	
4.60/2.05	U2_GAA(x1, x2, x3, x4, x5)  =  U2_GAA(x5)
4.60/2.05	
4.60/2.05	
4.60/2.05	We have to consider all (P,R,Pi)-chains
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(5) DependencyGraphProof (EQUIVALENT)
4.60/2.05	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(6)
4.60/2.05	Obligation:
4.60/2.05	Pi DP problem:
4.60/2.05	The TRS P consists of the following rules:
4.60/2.05	
4.60/2.05	   U1_GAA(X, Y, Z, f_out_gaa(X, Y, U)) -> F_IN_GAA(U, Y, Z)
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> U1_GAA(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   F_IN_GAA(s(X), Y, Z) -> F_IN_GAA(X, Y, U)
4.60/2.05	
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0, Y, 0) -> f_out_gaa(0, Y, 0)
4.60/2.05	   f_in_gaa(s(X), Y, Z) -> U1_gaa(X, Y, Z, f_in_gaa(X, Y, U))
4.60/2.05	   U1_gaa(X, Y, Z, f_out_gaa(X, Y, U)) -> U2_gaa(X, Y, Z, U, f_in_gaa(U, Y, Z))
4.60/2.05	   U2_gaa(X, Y, Z, U, f_out_gaa(U, Y, Z)) -> f_out_gaa(s(X), Y, Z)
4.60/2.05	
4.60/2.05	The argument filtering Pi contains the following mapping:
4.60/2.05	f_in_gaa(x1, x2, x3)  =  f_in_gaa(x1)
4.60/2.05	
4.60/2.05	0  =  0
4.60/2.05	
4.60/2.05	f_out_gaa(x1, x2, x3)  =  f_out_gaa(x3)
4.60/2.05	
4.60/2.05	s(x1)  =  s(x1)
4.60/2.05	
4.60/2.05	U1_gaa(x1, x2, x3, x4)  =  U1_gaa(x4)
4.60/2.05	
4.60/2.05	U2_gaa(x1, x2, x3, x4, x5)  =  U2_gaa(x5)
4.60/2.05	
4.60/2.05	F_IN_GAA(x1, x2, x3)  =  F_IN_GAA(x1)
4.60/2.05	
4.60/2.05	U1_GAA(x1, x2, x3, x4)  =  U1_GAA(x4)
4.60/2.05	
4.60/2.05	
4.60/2.05	We have to consider all (P,R,Pi)-chains
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(7) PiDPToQDPProof (SOUND)
4.60/2.05	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(8)
4.60/2.05	Obligation:
4.60/2.05	Q DP problem:
4.60/2.05	The TRS P consists of the following rules:
4.60/2.05	
4.60/2.05	   U1_GAA(f_out_gaa(U)) -> F_IN_GAA(U)
4.60/2.05	   F_IN_GAA(s(X)) -> U1_GAA(f_in_gaa(X))
4.60/2.05	   F_IN_GAA(s(X)) -> F_IN_GAA(X)
4.60/2.05	
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0) -> f_out_gaa(0)
4.60/2.05	   f_in_gaa(s(X)) -> U1_gaa(f_in_gaa(X))
4.60/2.05	   U1_gaa(f_out_gaa(U)) -> U2_gaa(f_in_gaa(U))
4.60/2.05	   U2_gaa(f_out_gaa(Z)) -> f_out_gaa(Z)
4.60/2.05	
4.60/2.05	The set Q consists of the following terms:
4.60/2.05	
4.60/2.05	   f_in_gaa(x0)
4.60/2.05	   U1_gaa(x0)
4.60/2.05	   U2_gaa(x0)
4.60/2.05	
4.60/2.05	We have to consider all (P,Q,R)-chains.
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(9) UsableRulesReductionPairsProof (EQUIVALENT)
4.60/2.05	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
4.60/2.05	
4.60/2.05	The following dependency pairs can be deleted:
4.60/2.05	
4.60/2.05	   F_IN_GAA(s(X)) -> U1_GAA(f_in_gaa(X))
4.60/2.05	   F_IN_GAA(s(X)) -> F_IN_GAA(X)
4.60/2.05	The following rules are removed from R:
4.60/2.05	
4.60/2.05	   f_in_gaa(s(X)) -> U1_gaa(f_in_gaa(X))
4.60/2.05	Used ordering: POLO with Polynomial interpretation [POLO]:
4.60/2.05	
4.60/2.05	   POL(0) = 0
4.60/2.05	   POL(F_IN_GAA(x_1)) = 2*x_1
4.60/2.05	   POL(U1_GAA(x_1)) = x_1
4.60/2.05	   POL(U1_gaa(x_1)) = 2*x_1
4.60/2.05	   POL(U2_gaa(x_1)) = x_1
4.60/2.05	   POL(f_in_gaa(x_1)) = 2*x_1
4.60/2.05	   POL(f_out_gaa(x_1)) = 2*x_1
4.60/2.05	   POL(s(x_1)) = 2*x_1
4.60/2.05	
4.60/2.05	
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(10)
4.60/2.05	Obligation:
4.60/2.05	Q DP problem:
4.60/2.05	The TRS P consists of the following rules:
4.60/2.05	
4.60/2.05	   U1_GAA(f_out_gaa(U)) -> F_IN_GAA(U)
4.60/2.05	
4.60/2.05	The TRS R consists of the following rules:
4.60/2.05	
4.60/2.05	   f_in_gaa(0) -> f_out_gaa(0)
4.60/2.05	   U1_gaa(f_out_gaa(U)) -> U2_gaa(f_in_gaa(U))
4.60/2.05	   U2_gaa(f_out_gaa(Z)) -> f_out_gaa(Z)
4.60/2.05	
4.60/2.05	The set Q consists of the following terms:
4.60/2.05	
4.60/2.05	   f_in_gaa(x0)
4.60/2.05	   U1_gaa(x0)
4.60/2.05	   U2_gaa(x0)
4.60/2.05	
4.60/2.05	We have to consider all (P,Q,R)-chains.
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(11) DependencyGraphProof (EQUIVALENT)
4.60/2.05	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
4.60/2.05	----------------------------------------
4.60/2.05	
4.60/2.05	(12)
4.60/2.05	TRUE
4.66/2.08	EOF