4.32/1.87	YES
4.32/1.89	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
4.32/1.89	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.32/1.89	
4.32/1.89	
4.32/1.89	Left Termination of the query pattern
4.32/1.89	
4.32/1.89	balance(g,a)
4.32/1.89	
4.32/1.89	w.r.t. the given Prolog program could successfully be proven:
4.32/1.89	
4.32/1.89	(0) Prolog
4.32/1.89	(1) PrologToPiTRSProof [SOUND, 0 ms]
4.32/1.89	(2) PiTRS
4.32/1.89	(3) DependencyPairsProof [EQUIVALENT, 2 ms]
4.32/1.89	(4) PiDP
4.32/1.89	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
4.32/1.89	(6) PiDP
4.32/1.89	(7) UsableRulesProof [EQUIVALENT, 0 ms]
4.32/1.89	(8) PiDP
4.32/1.89	(9) PiDPToQDPProof [SOUND, 0 ms]
4.32/1.89	(10) QDP
4.32/1.89	(11) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.32/1.89	(12) YES
4.32/1.89	
4.32/1.89	
4.32/1.89	----------------------------------------
4.32/1.89	
4.32/1.89	(0)
4.32/1.89	Obligation:
4.32/1.89	Clauses:
4.32/1.89	
4.32/1.89	balance(T, TB) :- balance(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])).
4.32/1.89	balance(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)).
4.32/1.89	balance(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) :- ','(balance(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)), balance(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))).
4.32/1.89	
4.32/1.89	
4.32/1.89	Query: balance(g,a)
4.32/1.89	----------------------------------------
4.32/1.89	
4.32/1.89	(1) PrologToPiTRSProof (SOUND)
4.32/1.89	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
4.32/1.89	
4.32/1.89	balance_in_2: (b,f)
4.32/1.89	
4.32/1.89	balance_in_5: (b,f,f,f,f)
4.32/1.89	
4.32/1.89	Transforming Prolog into the following Term Rewriting System:
4.32/1.89	
4.32/1.89	Pi-finite rewrite system:
4.32/1.89	The TRS R consists of the following rules:
4.32/1.89	
4.32/1.89	   balance_in_ga(T, TB) -> U1_ga(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.89	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.89	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.89	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.89	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.89	   U1_ga(T, TB, balance_out_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ga(T, TB)
4.32/1.89	
4.32/1.89	The argument filtering Pi contains the following mapping:
4.32/1.89	balance_in_ga(x1, x2)  =  balance_in_ga(x1)
4.32/1.89	
4.32/1.89	U1_ga(x1, x2, x3)  =  U1_ga(x3)
4.32/1.89	
4.32/1.89	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.89	
4.32/1.89	nil  =  nil
4.32/1.89	
4.32/1.89	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.89	
4.32/1.89	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.89	
4.32/1.89	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.89	
4.32/1.89	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.89	
4.32/1.89	balance_out_ga(x1, x2)  =  balance_out_ga
4.32/1.89	
4.32/1.89	
4.32/1.89	
4.32/1.89	
4.32/1.89	
4.32/1.89	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
4.32/1.89	
4.32/1.89	
4.32/1.89	
4.32/1.89	----------------------------------------
4.32/1.89	
4.32/1.89	(2)
4.32/1.89	Obligation:
4.32/1.89	Pi-finite rewrite system:
4.32/1.89	The TRS R consists of the following rules:
4.32/1.89	
4.32/1.89	   balance_in_ga(T, TB) -> U1_ga(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.89	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.89	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.89	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.89	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.89	   U1_ga(T, TB, balance_out_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ga(T, TB)
4.32/1.89	
4.32/1.89	The argument filtering Pi contains the following mapping:
4.32/1.89	balance_in_ga(x1, x2)  =  balance_in_ga(x1)
4.32/1.89	
4.32/1.89	U1_ga(x1, x2, x3)  =  U1_ga(x3)
4.32/1.89	
4.32/1.89	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.89	
4.32/1.89	nil  =  nil
4.32/1.89	
4.32/1.89	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.89	
4.32/1.89	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.89	
4.32/1.89	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.89	
4.32/1.89	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.89	
4.32/1.89	balance_out_ga(x1, x2)  =  balance_out_ga
4.32/1.89	
4.32/1.89	
4.32/1.89	
4.32/1.89	----------------------------------------
4.32/1.89	
4.32/1.89	(3) DependencyPairsProof (EQUIVALENT)
4.32/1.89	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
4.32/1.89	Pi DP problem:
4.32/1.89	The TRS P consists of the following rules:
4.32/1.89	
4.32/1.89	   BALANCE_IN_GA(T, TB) -> U1_GA(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.89	   BALANCE_IN_GA(T, TB) -> BALANCE_IN_GAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))
4.32/1.89	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.89	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_GAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))
4.32/1.89	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.89	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_GAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))
4.32/1.89	
4.32/1.89	The TRS R consists of the following rules:
4.32/1.89	
4.32/1.89	   balance_in_ga(T, TB) -> U1_ga(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.89	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.89	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.89	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.89	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.90	   U1_ga(T, TB, balance_out_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ga(T, TB)
4.32/1.90	
4.32/1.90	The argument filtering Pi contains the following mapping:
4.32/1.90	balance_in_ga(x1, x2)  =  balance_in_ga(x1)
4.32/1.90	
4.32/1.90	U1_ga(x1, x2, x3)  =  U1_ga(x3)
4.32/1.90	
4.32/1.90	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.90	
4.32/1.90	nil  =  nil
4.32/1.90	
4.32/1.90	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.90	
4.32/1.90	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.90	
4.32/1.90	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.90	
4.32/1.90	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.90	
4.32/1.90	balance_out_ga(x1, x2)  =  balance_out_ga
4.32/1.90	
4.32/1.90	BALANCE_IN_GA(x1, x2)  =  BALANCE_IN_GA(x1)
4.32/1.90	
4.32/1.90	U1_GA(x1, x2, x3)  =  U1_GA(x3)
4.32/1.90	
4.32/1.90	BALANCE_IN_GAAAA(x1, x2, x3, x4, x5)  =  BALANCE_IN_GAAAA(x1)
4.32/1.90	
4.32/1.90	U2_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_GAAAA(x3, x18)
4.32/1.90	
4.32/1.90	U3_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_GAAAA(x18)
4.32/1.90	
4.32/1.90	
4.32/1.90	We have to consider all (P,R,Pi)-chains
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(4)
4.32/1.90	Obligation:
4.32/1.90	Pi DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   BALANCE_IN_GA(T, TB) -> U1_GA(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.90	   BALANCE_IN_GA(T, TB) -> BALANCE_IN_GAAAA(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_GAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))
4.32/1.90	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.90	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_GAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   balance_in_ga(T, TB) -> U1_ga(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.90	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.90	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.90	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.90	   U1_ga(T, TB, balance_out_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ga(T, TB)
4.32/1.90	
4.32/1.90	The argument filtering Pi contains the following mapping:
4.32/1.90	balance_in_ga(x1, x2)  =  balance_in_ga(x1)
4.32/1.90	
4.32/1.90	U1_ga(x1, x2, x3)  =  U1_ga(x3)
4.32/1.90	
4.32/1.90	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.90	
4.32/1.90	nil  =  nil
4.32/1.90	
4.32/1.90	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.90	
4.32/1.90	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.90	
4.32/1.90	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.90	
4.32/1.90	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.90	
4.32/1.90	balance_out_ga(x1, x2)  =  balance_out_ga
4.32/1.90	
4.32/1.90	BALANCE_IN_GA(x1, x2)  =  BALANCE_IN_GA(x1)
4.32/1.90	
4.32/1.90	U1_GA(x1, x2, x3)  =  U1_GA(x3)
4.32/1.90	
4.32/1.90	BALANCE_IN_GAAAA(x1, x2, x3, x4, x5)  =  BALANCE_IN_GAAAA(x1)
4.32/1.90	
4.32/1.90	U2_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_GAAAA(x3, x18)
4.32/1.90	
4.32/1.90	U3_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_GAAAA(x18)
4.32/1.90	
4.32/1.90	
4.32/1.90	We have to consider all (P,R,Pi)-chains
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(5) DependencyGraphProof (EQUIVALENT)
4.32/1.90	The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(6)
4.32/1.90	Obligation:
4.32/1.90	Pi DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_GAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_GAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   balance_in_ga(T, TB) -> U1_ga(T, TB, balance_in_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, [])))
4.32/1.90	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.90	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.90	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.90	   U1_ga(T, TB, balance_out_gaaaa(T, -(I, []), -(.(','(TB, -(I, [])), X), X), -(Rest, []), -(Rest, []))) -> balance_out_ga(T, TB)
4.32/1.90	
4.32/1.90	The argument filtering Pi contains the following mapping:
4.32/1.90	balance_in_ga(x1, x2)  =  balance_in_ga(x1)
4.32/1.90	
4.32/1.90	U1_ga(x1, x2, x3)  =  U1_ga(x3)
4.32/1.90	
4.32/1.90	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.90	
4.32/1.90	nil  =  nil
4.32/1.90	
4.32/1.90	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.90	
4.32/1.90	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.90	
4.32/1.90	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.90	
4.32/1.90	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.90	
4.32/1.90	balance_out_ga(x1, x2)  =  balance_out_ga
4.32/1.90	
4.32/1.90	BALANCE_IN_GAAAA(x1, x2, x3, x4, x5)  =  BALANCE_IN_GAAAA(x1)
4.32/1.90	
4.32/1.90	U2_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_GAAAA(x3, x18)
4.32/1.90	
4.32/1.90	
4.32/1.90	We have to consider all (P,R,Pi)-chains
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(7) UsableRulesProof (EQUIVALENT)
4.32/1.90	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(8)
4.32/1.90	Obligation:
4.32/1.90	Pi DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> BALANCE_IN_GAAAA(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_GAAAA(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> BALANCE_IN_GAAAA(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   balance_in_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T)) -> balance_out_gaaaa(nil, -(X, X), -(A, B), -(A, B), -(.(','(nil, -(C, C)), T), T))
4.32/1.90	   balance_in_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT)) -> U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1)))
4.32/1.90	   U2_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(L, -(IH, .(V, IT1)), -(H, T), -(HR1, TR1), -(NH, NT1))) -> U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_in_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT)))
4.32/1.90	   U3_gaaaa(L, V, R, IH, IT, LB, VB, RB, A, D, H, X, T, HR, TR, NH, NT, balance_out_gaaaa(R, -(IT1, IT), -(HR1, TR1), -(HR, TR), -(NT1, NT))) -> balance_out_gaaaa(tree(L, V, R), -(IH, IT), -(.(','(tree(LB, VB, RB), -(A, D)), H), .(','(LB, -(A, .(VB, X))), .(','(RB, -(X, D)), T))), -(HR, TR), -(NH, NT))
4.32/1.90	
4.32/1.90	The argument filtering Pi contains the following mapping:
4.32/1.90	balance_in_gaaaa(x1, x2, x3, x4, x5)  =  balance_in_gaaaa(x1)
4.32/1.90	
4.32/1.90	nil  =  nil
4.32/1.90	
4.32/1.90	balance_out_gaaaa(x1, x2, x3, x4, x5)  =  balance_out_gaaaa
4.32/1.90	
4.32/1.90	tree(x1, x2, x3)  =  tree(x1, x2, x3)
4.32/1.90	
4.32/1.90	U2_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_gaaaa(x3, x18)
4.32/1.90	
4.32/1.90	U3_gaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U3_gaaaa(x18)
4.32/1.90	
4.32/1.90	BALANCE_IN_GAAAA(x1, x2, x3, x4, x5)  =  BALANCE_IN_GAAAA(x1)
4.32/1.90	
4.32/1.90	U2_GAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18)  =  U2_GAAAA(x3, x18)
4.32/1.90	
4.32/1.90	
4.32/1.90	We have to consider all (P,R,Pi)-chains
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(9) PiDPToQDPProof (SOUND)
4.32/1.90	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(10)
4.32/1.90	Obligation:
4.32/1.90	Q DP problem:
4.32/1.90	The TRS P consists of the following rules:
4.32/1.90	
4.32/1.90	   U2_GAAAA(R, balance_out_gaaaa) -> BALANCE_IN_GAAAA(R)
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R)) -> U2_GAAAA(R, balance_in_gaaaa(L))
4.32/1.90	   BALANCE_IN_GAAAA(tree(L, V, R)) -> BALANCE_IN_GAAAA(L)
4.32/1.90	
4.32/1.90	The TRS R consists of the following rules:
4.32/1.90	
4.32/1.90	   balance_in_gaaaa(nil) -> balance_out_gaaaa
4.32/1.90	   balance_in_gaaaa(tree(L, V, R)) -> U2_gaaaa(R, balance_in_gaaaa(L))
4.32/1.90	   U2_gaaaa(R, balance_out_gaaaa) -> U3_gaaaa(balance_in_gaaaa(R))
4.32/1.90	   U3_gaaaa(balance_out_gaaaa) -> balance_out_gaaaa
4.32/1.90	
4.32/1.90	The set Q consists of the following terms:
4.32/1.90	
4.32/1.90	   balance_in_gaaaa(x0)
4.32/1.90	   U2_gaaaa(x0, x1)
4.32/1.90	   U3_gaaaa(x0)
4.32/1.90	
4.32/1.90	We have to consider all (P,Q,R)-chains.
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(11) QDPSizeChangeProof (EQUIVALENT)
4.32/1.90	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. 
4.32/1.90	
4.32/1.90	From the DPs we obtained the following set of size-change graphs:
4.32/1.90	*BALANCE_IN_GAAAA(tree(L, V, R)) -> U2_GAAAA(R, balance_in_gaaaa(L))
4.32/1.90	The graph contains the following edges 1 > 1
4.32/1.90	
4.32/1.90	
4.32/1.90	*BALANCE_IN_GAAAA(tree(L, V, R)) -> BALANCE_IN_GAAAA(L)
4.32/1.90	The graph contains the following edges 1 > 1
4.32/1.90	
4.32/1.90	
4.32/1.90	*U2_GAAAA(R, balance_out_gaaaa) -> BALANCE_IN_GAAAA(R)
4.32/1.90	The graph contains the following edges 1 >= 1
4.32/1.90	
4.32/1.90	
4.32/1.90	----------------------------------------
4.32/1.90	
4.32/1.90	(12)
4.32/1.90	YES
4.50/1.94	EOF