3.66/1.81	YES
3.80/1.84	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
3.80/1.84	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.80/1.84	
3.80/1.84	
3.80/1.84	Left Termination of the query pattern
3.80/1.84	
3.80/1.84	bin_tree(g)
3.80/1.84	
3.80/1.84	w.r.t. the given Prolog program could successfully be proven:
3.80/1.84	
3.80/1.84	(0) Prolog
3.80/1.84	(1) PrologToPiTRSProof [SOUND, 0 ms]
3.80/1.84	(2) PiTRS
3.80/1.84	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
3.80/1.84	(4) PiDP
3.80/1.84	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.80/1.84	(6) PiDP
3.80/1.84	(7) PiDPToQDPProof [SOUND, 4 ms]
3.80/1.84	(8) QDP
3.80/1.84	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.80/1.84	(10) YES
3.80/1.84	
3.80/1.84	
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(0)
3.80/1.84	Obligation:
3.80/1.84	Clauses:
3.80/1.84	
3.80/1.84	bin_tree(void).
3.80/1.84	bin_tree(tree(X1, Left, Right)) :- ','(bin_tree(Left), bin_tree(Right)).
3.80/1.84	
3.80/1.84	
3.80/1.84	Query: bin_tree(g)
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(1) PrologToPiTRSProof (SOUND)
3.80/1.84	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
3.80/1.84	
3.80/1.84	bin_tree_in_1: (b)
3.80/1.84	
3.80/1.84	Transforming Prolog into the following Term Rewriting System:
3.80/1.84	
3.80/1.84	Pi-finite rewrite system:
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g(void)
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(X1, Left, Right, bin_tree_out_g(Left)) -> U2_g(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U2_g(X1, Left, Right, bin_tree_out_g(Right)) -> bin_tree_out_g(tree(X1, Left, Right))
3.80/1.84	
3.80/1.84	The argument filtering Pi contains the following mapping:
3.80/1.84	bin_tree_in_g(x1)  =  bin_tree_in_g(x1)
3.80/1.84	
3.80/1.84	void  =  void
3.80/1.84	
3.80/1.84	bin_tree_out_g(x1)  =  bin_tree_out_g
3.80/1.84	
3.80/1.84	tree(x1, x2, x3)  =  tree(x1, x2, x3)
3.80/1.84	
3.80/1.84	U1_g(x1, x2, x3, x4)  =  U1_g(x3, x4)
3.80/1.84	
3.80/1.84	U2_g(x1, x2, x3, x4)  =  U2_g(x4)
3.80/1.84	
3.80/1.84	
3.80/1.84	
3.80/1.84	
3.80/1.84	
3.80/1.84	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
3.80/1.84	
3.80/1.84	
3.80/1.84	
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(2)
3.80/1.84	Obligation:
3.80/1.84	Pi-finite rewrite system:
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g(void)
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(X1, Left, Right, bin_tree_out_g(Left)) -> U2_g(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U2_g(X1, Left, Right, bin_tree_out_g(Right)) -> bin_tree_out_g(tree(X1, Left, Right))
3.80/1.84	
3.80/1.84	The argument filtering Pi contains the following mapping:
3.80/1.84	bin_tree_in_g(x1)  =  bin_tree_in_g(x1)
3.80/1.84	
3.80/1.84	void  =  void
3.80/1.84	
3.80/1.84	bin_tree_out_g(x1)  =  bin_tree_out_g
3.80/1.84	
3.80/1.84	tree(x1, x2, x3)  =  tree(x1, x2, x3)
3.80/1.84	
3.80/1.84	U1_g(x1, x2, x3, x4)  =  U1_g(x3, x4)
3.80/1.84	
3.80/1.84	U2_g(x1, x2, x3, x4)  =  U2_g(x4)
3.80/1.84	
3.80/1.84	
3.80/1.84	
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(3) DependencyPairsProof (EQUIVALENT)
3.80/1.84	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
3.80/1.84	Pi DP problem:
3.80/1.84	The TRS P consists of the following rules:
3.80/1.84	
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> U1_G(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> BIN_TREE_IN_G(Left)
3.80/1.84	   U1_G(X1, Left, Right, bin_tree_out_g(Left)) -> U2_G(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U1_G(X1, Left, Right, bin_tree_out_g(Left)) -> BIN_TREE_IN_G(Right)
3.80/1.84	
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g(void)
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(X1, Left, Right, bin_tree_out_g(Left)) -> U2_g(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U2_g(X1, Left, Right, bin_tree_out_g(Right)) -> bin_tree_out_g(tree(X1, Left, Right))
3.80/1.84	
3.80/1.84	The argument filtering Pi contains the following mapping:
3.80/1.84	bin_tree_in_g(x1)  =  bin_tree_in_g(x1)
3.80/1.84	
3.80/1.84	void  =  void
3.80/1.84	
3.80/1.84	bin_tree_out_g(x1)  =  bin_tree_out_g
3.80/1.84	
3.80/1.84	tree(x1, x2, x3)  =  tree(x1, x2, x3)
3.80/1.84	
3.80/1.84	U1_g(x1, x2, x3, x4)  =  U1_g(x3, x4)
3.80/1.84	
3.80/1.84	U2_g(x1, x2, x3, x4)  =  U2_g(x4)
3.80/1.84	
3.80/1.84	BIN_TREE_IN_G(x1)  =  BIN_TREE_IN_G(x1)
3.80/1.84	
3.80/1.84	U1_G(x1, x2, x3, x4)  =  U1_G(x3, x4)
3.80/1.84	
3.80/1.84	U2_G(x1, x2, x3, x4)  =  U2_G(x4)
3.80/1.84	
3.80/1.84	
3.80/1.84	We have to consider all (P,R,Pi)-chains
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(4)
3.80/1.84	Obligation:
3.80/1.84	Pi DP problem:
3.80/1.84	The TRS P consists of the following rules:
3.80/1.84	
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> U1_G(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> BIN_TREE_IN_G(Left)
3.80/1.84	   U1_G(X1, Left, Right, bin_tree_out_g(Left)) -> U2_G(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U1_G(X1, Left, Right, bin_tree_out_g(Left)) -> BIN_TREE_IN_G(Right)
3.80/1.84	
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g(void)
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(X1, Left, Right, bin_tree_out_g(Left)) -> U2_g(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U2_g(X1, Left, Right, bin_tree_out_g(Right)) -> bin_tree_out_g(tree(X1, Left, Right))
3.80/1.84	
3.80/1.84	The argument filtering Pi contains the following mapping:
3.80/1.84	bin_tree_in_g(x1)  =  bin_tree_in_g(x1)
3.80/1.84	
3.80/1.84	void  =  void
3.80/1.84	
3.80/1.84	bin_tree_out_g(x1)  =  bin_tree_out_g
3.80/1.84	
3.80/1.84	tree(x1, x2, x3)  =  tree(x1, x2, x3)
3.80/1.84	
3.80/1.84	U1_g(x1, x2, x3, x4)  =  U1_g(x3, x4)
3.80/1.84	
3.80/1.84	U2_g(x1, x2, x3, x4)  =  U2_g(x4)
3.80/1.84	
3.80/1.84	BIN_TREE_IN_G(x1)  =  BIN_TREE_IN_G(x1)
3.80/1.84	
3.80/1.84	U1_G(x1, x2, x3, x4)  =  U1_G(x3, x4)
3.80/1.84	
3.80/1.84	U2_G(x1, x2, x3, x4)  =  U2_G(x4)
3.80/1.84	
3.80/1.84	
3.80/1.84	We have to consider all (P,R,Pi)-chains
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(5) DependencyGraphProof (EQUIVALENT)
3.80/1.84	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node.
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(6)
3.80/1.84	Obligation:
3.80/1.84	Pi DP problem:
3.80/1.84	The TRS P consists of the following rules:
3.80/1.84	
3.80/1.84	   U1_G(X1, Left, Right, bin_tree_out_g(Left)) -> BIN_TREE_IN_G(Right)
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> U1_G(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> BIN_TREE_IN_G(Left)
3.80/1.84	
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g(void)
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(X1, Left, Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(X1, Left, Right, bin_tree_out_g(Left)) -> U2_g(X1, Left, Right, bin_tree_in_g(Right))
3.80/1.84	   U2_g(X1, Left, Right, bin_tree_out_g(Right)) -> bin_tree_out_g(tree(X1, Left, Right))
3.80/1.84	
3.80/1.84	The argument filtering Pi contains the following mapping:
3.80/1.84	bin_tree_in_g(x1)  =  bin_tree_in_g(x1)
3.80/1.84	
3.80/1.84	void  =  void
3.80/1.84	
3.80/1.84	bin_tree_out_g(x1)  =  bin_tree_out_g
3.80/1.84	
3.80/1.84	tree(x1, x2, x3)  =  tree(x1, x2, x3)
3.80/1.84	
3.80/1.84	U1_g(x1, x2, x3, x4)  =  U1_g(x3, x4)
3.80/1.84	
3.80/1.84	U2_g(x1, x2, x3, x4)  =  U2_g(x4)
3.80/1.84	
3.80/1.84	BIN_TREE_IN_G(x1)  =  BIN_TREE_IN_G(x1)
3.80/1.84	
3.80/1.84	U1_G(x1, x2, x3, x4)  =  U1_G(x3, x4)
3.80/1.84	
3.80/1.84	
3.80/1.84	We have to consider all (P,R,Pi)-chains
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(7) PiDPToQDPProof (SOUND)
3.80/1.84	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(8)
3.80/1.84	Obligation:
3.80/1.84	Q DP problem:
3.80/1.84	The TRS P consists of the following rules:
3.80/1.84	
3.80/1.84	   U1_G(Right, bin_tree_out_g) -> BIN_TREE_IN_G(Right)
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> U1_G(Right, bin_tree_in_g(Left))
3.80/1.84	   BIN_TREE_IN_G(tree(X1, Left, Right)) -> BIN_TREE_IN_G(Left)
3.80/1.84	
3.80/1.84	The TRS R consists of the following rules:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(void) -> bin_tree_out_g
3.80/1.84	   bin_tree_in_g(tree(X1, Left, Right)) -> U1_g(Right, bin_tree_in_g(Left))
3.80/1.84	   U1_g(Right, bin_tree_out_g) -> U2_g(bin_tree_in_g(Right))
3.80/1.84	   U2_g(bin_tree_out_g) -> bin_tree_out_g
3.80/1.84	
3.80/1.84	The set Q consists of the following terms:
3.80/1.84	
3.80/1.84	   bin_tree_in_g(x0)
3.80/1.84	   U1_g(x0, x1)
3.80/1.84	   U2_g(x0)
3.80/1.84	
3.80/1.84	We have to consider all (P,Q,R)-chains.
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(9) QDPSizeChangeProof (EQUIVALENT)
3.80/1.84	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.80/1.84	
3.80/1.84	From the DPs we obtained the following set of size-change graphs:
3.80/1.84	*BIN_TREE_IN_G(tree(X1, Left, Right)) -> U1_G(Right, bin_tree_in_g(Left))
3.80/1.84	The graph contains the following edges 1 > 1
3.80/1.84	
3.80/1.84	
3.80/1.84	*BIN_TREE_IN_G(tree(X1, Left, Right)) -> BIN_TREE_IN_G(Left)
3.80/1.84	The graph contains the following edges 1 > 1
3.80/1.84	
3.80/1.84	
3.80/1.84	*U1_G(Right, bin_tree_out_g) -> BIN_TREE_IN_G(Right)
3.80/1.84	The graph contains the following edges 1 >= 1
3.80/1.84	
3.80/1.84	
3.80/1.84	----------------------------------------
3.80/1.84	
3.80/1.84	(10)
3.80/1.84	YES
3.80/1.87	EOF