6.15/2.70	YES
6.15/2.72	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
6.15/2.72	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.15/2.72	
6.15/2.72	
6.15/2.72	Left Termination of the query pattern
6.15/2.72	
6.15/2.72	insert(a,a,g)
6.15/2.72	
6.15/2.72	w.r.t. the given Prolog program could successfully be proven:
6.15/2.72	
6.15/2.72	(0) Prolog
6.15/2.72	(1) PrologToPiTRSProof [SOUND, 0 ms]
6.15/2.72	(2) PiTRS
6.15/2.72	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
6.15/2.72	(4) PiDP
6.15/2.72	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
6.15/2.72	(6) AND
6.15/2.72	    (7) PiDP
6.15/2.72	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
6.15/2.72	        (9) PiDP
6.15/2.72	        (10) PiDPToQDPProof [SOUND, 8 ms]
6.15/2.72	        (11) QDP
6.15/2.72	        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.15/2.72	        (13) YES
6.15/2.72	    (14) PiDP
6.15/2.72	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
6.15/2.72	        (16) PiDP
6.15/2.72	        (17) PiDPToQDPProof [EQUIVALENT, 0 ms]
6.15/2.72	        (18) QDP
6.15/2.72	        (19) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.15/2.72	        (20) YES
6.15/2.72	    (21) PiDP
6.15/2.72	        (22) UsableRulesProof [EQUIVALENT, 0 ms]
6.15/2.72	        (23) PiDP
6.15/2.72	        (24) PiDPToQDPProof [SOUND, 0 ms]
6.15/2.72	        (25) QDP
6.15/2.72	        (26) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.15/2.72	        (27) YES
6.15/2.72	    (28) PiDP
6.15/2.72	        (29) UsableRulesProof [EQUIVALENT, 0 ms]
6.15/2.72	        (30) PiDP
6.15/2.72	        (31) PiDPToQDPProof [SOUND, 0 ms]
6.15/2.72	        (32) QDP
6.15/2.72	        (33) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.15/2.72	        (34) YES
6.15/2.72	    (35) PiDP
6.15/2.72	        (36) UsableRulesProof [EQUIVALENT, 0 ms]
6.15/2.72	        (37) PiDP
6.15/2.72	        (38) PiDPToQDPProof [SOUND, 1 ms]
6.15/2.72	        (39) QDP
6.15/2.72	        (40) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.15/2.72	        (41) YES
6.15/2.72	
6.15/2.72	
6.15/2.72	----------------------------------------
6.15/2.72	
6.15/2.72	(0)
6.15/2.72	Obligation:
6.15/2.72	Clauses:
6.15/2.72	
6.15/2.72	insert(X, void, tree(X, void, void)).
6.15/2.72	insert(X, tree(X, Left, Right), tree(X, Left, Right)).
6.15/2.72	insert(X, tree(Y, Left, Right), tree(Y, Left1, Right)) :- ','(less(X, Y), insert(X, Left, Left1)).
6.15/2.72	insert(X, tree(Y, Left, Right), tree(Y, Left, Right1)) :- ','(less(Y, X), insert(X, Right, Right1)).
6.15/2.72	less(0, s(X1)).
6.15/2.72	less(s(X), s(Y)) :- less(X, Y).
6.15/2.72	
6.15/2.72	
6.15/2.72	Query: insert(a,a,g)
6.15/2.72	----------------------------------------
6.15/2.72	
6.15/2.72	(1) PrologToPiTRSProof (SOUND)
6.15/2.72	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
6.15/2.72	
6.15/2.72	insert_in_3: (f,f,b) (b,f,b)
6.15/2.72	
6.15/2.72	less_in_2: (f,b) (b,b) (b,f)
6.15/2.72	
6.15/2.72	Transforming Prolog into the following Term Rewriting System:
6.15/2.72	
6.15/2.72	Pi-finite rewrite system:
6.15/2.72	The TRS R consists of the following rules:
6.15/2.72	
6.15/2.72	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.15/2.72	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.15/2.72	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.15/2.72	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.15/2.72	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.15/2.72	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.15/2.72	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.15/2.72	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.15/2.72	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.15/2.72	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.15/2.72	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.15/2.72	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.15/2.72	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.15/2.72	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.15/2.72	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.15/2.72	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.15/2.72	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.15/2.72	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.15/2.72	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.15/2.72	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.15/2.72	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.15/2.72	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.15/2.72	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.15/2.72	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.15/2.72	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.15/2.72	
6.15/2.72	The argument filtering Pi contains the following mapping:
6.15/2.72	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.15/2.72	
6.15/2.72	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.15/2.72	
6.15/2.72	void  =  void
6.15/2.72	
6.15/2.72	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.15/2.72	
6.15/2.72	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.15/2.72	
6.15/2.72	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.15/2.72	
6.15/2.72	s(x1)  =  s(x1)
6.15/2.72	
6.15/2.72	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.15/2.72	
6.15/2.72	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.15/2.72	
6.15/2.72	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.15/2.72	
6.15/2.72	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.15/2.72	
6.15/2.72	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.15/2.72	
6.15/2.72	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.15/2.72	
6.15/2.72	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.15/2.72	
6.15/2.72	0  =  0
6.15/2.72	
6.15/2.72	less_out_gg(x1, x2)  =  less_out_gg
6.15/2.72	
6.15/2.72	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.15/2.72	
6.15/2.72	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.15/2.72	
6.15/2.72	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.15/2.72	
6.15/2.72	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.15/2.72	
6.15/2.72	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.15/2.72	
6.15/2.72	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.15/2.72	
6.15/2.72	less_out_ga(x1, x2)  =  less_out_ga
6.15/2.72	
6.15/2.72	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.15/2.72	
6.15/2.72	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.15/2.72	
6.15/2.72	
6.15/2.72	
6.15/2.72	
6.15/2.72	
6.15/2.72	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
6.15/2.72	
6.15/2.72	
6.15/2.72	
6.15/2.72	----------------------------------------
6.15/2.72	
6.15/2.72	(2)
6.15/2.72	Obligation:
6.15/2.72	Pi-finite rewrite system:
6.15/2.72	The TRS R consists of the following rules:
6.15/2.73	
6.15/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.15/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.15/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.15/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.15/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.15/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.15/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.15/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.15/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.15/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.15/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.15/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.15/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.15/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.15/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.15/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.15/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.15/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.15/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.15/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.15/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.15/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.15/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.15/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.15/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.15/2.73	
6.15/2.73	The argument filtering Pi contains the following mapping:
6.15/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.15/2.73	
6.15/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.15/2.73	
6.15/2.73	void  =  void
6.15/2.73	
6.15/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.15/2.73	
6.15/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.15/2.73	
6.15/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.15/2.73	
6.15/2.73	s(x1)  =  s(x1)
6.15/2.73	
6.15/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.15/2.73	
6.15/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.15/2.73	
6.15/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.15/2.73	
6.15/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.15/2.73	
6.15/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.15/2.73	
6.15/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.15/2.73	
6.15/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.15/2.73	
6.15/2.73	0  =  0
6.15/2.73	
6.15/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.15/2.73	
6.15/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.15/2.73	
6.15/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.15/2.73	
6.15/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.15/2.73	
6.15/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.15/2.73	
6.15/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.15/2.73	
6.15/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.15/2.73	
6.15/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.15/2.73	
6.15/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.15/2.73	
6.15/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.15/2.73	
6.15/2.73	
6.15/2.73	
6.15/2.73	----------------------------------------
6.15/2.73	
6.15/2.73	(3) DependencyPairsProof (EQUIVALENT)
6.15/2.73	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
6.15/2.73	Pi DP problem:
6.15/2.73	The TRS P consists of the following rules:
6.15/2.73	
6.15/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_AAG(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.15/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_AG(X, Y)
6.15/2.73	   LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y))
6.51/2.73	   LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y)
6.51/2.73	   U1_AAG(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_AAG(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   U1_AAG(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAG(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GG(X, Y)
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> U5_GG(X, Y, less_in_gg(X, Y))
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_GAG(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_GG(Y, X)
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_GAG(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> INSERT_IN_GAG(X, Right, Right1)
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_AAG(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_GA(Y, X)
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y))
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y)
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_AAG(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> INSERT_IN_AAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_AAG(x1, x2, x3)  =  INSERT_IN_AAG(x3)
6.51/2.73	
6.51/2.73	U1_AAG(x1, x2, x3, x4, x5, x6)  =  U1_AAG(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
6.51/2.73	
6.51/2.73	U5_AG(x1, x2, x3)  =  U5_AG(x3)
6.51/2.73	
6.51/2.73	U2_AAG(x1, x2, x3, x4, x5, x6)  =  U2_AAG(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_GAG(x1, x2, x3)  =  INSERT_IN_GAG(x1, x3)
6.51/2.73	
6.51/2.73	U1_GAG(x1, x2, x3, x4, x5, x6)  =  U1_GAG(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GG(x1, x2)  =  LESS_IN_GG(x1, x2)
6.51/2.73	
6.51/2.73	U5_GG(x1, x2, x3)  =  U5_GG(x3)
6.51/2.73	
6.51/2.73	U2_GAG(x1, x2, x3, x4, x5, x6)  =  U2_GAG(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_GAG(x1, x2, x3, x4, x5, x6)  =  U3_GAG(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_GAG(x1, x2, x3, x4, x5, x6)  =  U4_GAG(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_AAG(x1, x2, x3, x4, x5, x6)  =  U3_AAG(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GA(x1, x2)  =  LESS_IN_GA(x1)
6.51/2.73	
6.51/2.73	U5_GA(x1, x2, x3)  =  U5_GA(x3)
6.51/2.73	
6.51/2.73	U4_AAG(x1, x2, x3, x4, x5, x6)  =  U4_AAG(x2, x3, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(4)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_AAG(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_AG(X, Y)
6.51/2.73	   LESS_IN_AG(s(X), s(Y)) -> U5_AG(X, Y, less_in_ag(X, Y))
6.51/2.73	   LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y)
6.51/2.73	   U1_AAG(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_AAG(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   U1_AAG(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAG(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> LESS_IN_GG(X, Y)
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> U5_GG(X, Y, less_in_gg(X, Y))
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_GAG(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_GG(Y, X)
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_GAG(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> INSERT_IN_GAG(X, Right, Right1)
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_AAG(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> LESS_IN_GA(Y, X)
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> U5_GA(X, Y, less_in_ga(X, Y))
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y)
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_AAG(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> INSERT_IN_AAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_AAG(x1, x2, x3)  =  INSERT_IN_AAG(x3)
6.51/2.73	
6.51/2.73	U1_AAG(x1, x2, x3, x4, x5, x6)  =  U1_AAG(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
6.51/2.73	
6.51/2.73	U5_AG(x1, x2, x3)  =  U5_AG(x3)
6.51/2.73	
6.51/2.73	U2_AAG(x1, x2, x3, x4, x5, x6)  =  U2_AAG(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_GAG(x1, x2, x3)  =  INSERT_IN_GAG(x1, x3)
6.51/2.73	
6.51/2.73	U1_GAG(x1, x2, x3, x4, x5, x6)  =  U1_GAG(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GG(x1, x2)  =  LESS_IN_GG(x1, x2)
6.51/2.73	
6.51/2.73	U5_GG(x1, x2, x3)  =  U5_GG(x3)
6.51/2.73	
6.51/2.73	U2_GAG(x1, x2, x3, x4, x5, x6)  =  U2_GAG(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_GAG(x1, x2, x3, x4, x5, x6)  =  U3_GAG(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_GAG(x1, x2, x3, x4, x5, x6)  =  U4_GAG(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_AAG(x1, x2, x3, x4, x5, x6)  =  U3_AAG(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GA(x1, x2)  =  LESS_IN_GA(x1)
6.51/2.73	
6.51/2.73	U5_GA(x1, x2, x3)  =  U5_GA(x3)
6.51/2.73	
6.51/2.73	U4_AAG(x1, x2, x3, x4, x5, x6)  =  U4_AAG(x2, x3, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(5) DependencyGraphProof (EQUIVALENT)
6.51/2.73	The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 13 less nodes.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(6)
6.51/2.73	Complex Obligation (AND)
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(7)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GA(x1, x2)  =  LESS_IN_GA(x1)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(8) UsableRulesProof (EQUIVALENT)
6.51/2.73	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(9)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GA(s(X), s(Y)) -> LESS_IN_GA(X, Y)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	LESS_IN_GA(x1, x2)  =  LESS_IN_GA(x1)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(10) PiDPToQDPProof (SOUND)
6.51/2.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(11)
6.51/2.73	Obligation:
6.51/2.73	Q DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GA(s(X)) -> LESS_IN_GA(X)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	Q is empty.
6.51/2.73	We have to consider all (P,Q,R)-chains.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(12) QDPSizeChangeProof (EQUIVALENT)
6.51/2.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. 
6.51/2.73	
6.51/2.73	From the DPs we obtained the following set of size-change graphs:
6.51/2.73	*LESS_IN_GA(s(X)) -> LESS_IN_GA(X)
6.51/2.73	The graph contains the following edges 1 > 1
6.51/2.73	
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(13)
6.51/2.73	YES
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(14)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	LESS_IN_GG(x1, x2)  =  LESS_IN_GG(x1, x2)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(15) UsableRulesProof (EQUIVALENT)
6.51/2.73	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(16)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	Pi is empty.
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(17) PiDPToQDPProof (EQUIVALENT)
6.51/2.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(18)
6.51/2.73	Obligation:
6.51/2.73	Q DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	Q is empty.
6.51/2.73	We have to consider all (P,Q,R)-chains.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(19) QDPSizeChangeProof (EQUIVALENT)
6.51/2.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. 
6.51/2.73	
6.51/2.73	From the DPs we obtained the following set of size-change graphs:
6.51/2.73	*LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y)
6.51/2.73	The graph contains the following edges 1 > 1, 2 > 2
6.51/2.73	
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(20)
6.51/2.73	YES
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(21)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAG(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> INSERT_IN_GAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_GAG(x1, x2, x3)  =  INSERT_IN_GAG(x1, x3)
6.51/2.73	
6.51/2.73	U1_GAG(x1, x2, x3, x4, x5, x6)  =  U1_GAG(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	U3_GAG(x1, x2, x3, x4, x5, x6)  =  U3_GAG(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(22) UsableRulesProof (EQUIVALENT)
6.51/2.73	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(23)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   U1_GAG(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> INSERT_IN_GAG(X, Left, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_GAG(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_GAG(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> INSERT_IN_GAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	INSERT_IN_GAG(x1, x2, x3)  =  INSERT_IN_GAG(x1, x3)
6.51/2.73	
6.51/2.73	U1_GAG(x1, x2, x3, x4, x5, x6)  =  U1_GAG(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	U3_GAG(x1, x2, x3, x4, x5, x6)  =  U3_GAG(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(24) PiDPToQDPProof (SOUND)
6.51/2.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(25)
6.51/2.73	Obligation:
6.51/2.73	Q DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   U1_GAG(X, Y, Right, Left1, less_out_gg) -> INSERT_IN_GAG(X, Left1)
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left1, Right)) -> U1_GAG(X, Y, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   INSERT_IN_GAG(X, tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_GAG(X, Y, Left, Right1, less_out_gg) -> INSERT_IN_GAG(X, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(less_in_gg(X, Y))
6.51/2.73	   U5_gg(less_out_gg) -> less_out_gg
6.51/2.73	
6.51/2.73	The set Q consists of the following terms:
6.51/2.73	
6.51/2.73	   less_in_gg(x0, x1)
6.51/2.73	   U5_gg(x0)
6.51/2.73	
6.51/2.73	We have to consider all (P,Q,R)-chains.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(26) QDPSizeChangeProof (EQUIVALENT)
6.51/2.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. 
6.51/2.73	
6.51/2.73	From the DPs we obtained the following set of size-change graphs:
6.51/2.73	*INSERT_IN_GAG(X, tree(Y, Left1, Right)) -> U1_GAG(X, Y, Right, Left1, less_in_gg(X, Y))
6.51/2.73	The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 2 > 4
6.51/2.73	
6.51/2.73	
6.51/2.73	*INSERT_IN_GAG(X, tree(Y, Left, Right1)) -> U3_GAG(X, Y, Left, Right1, less_in_gg(Y, X))
6.51/2.73	The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 2 > 4
6.51/2.73	
6.51/2.73	
6.51/2.73	*U1_GAG(X, Y, Right, Left1, less_out_gg) -> INSERT_IN_GAG(X, Left1)
6.51/2.73	The graph contains the following edges 1 >= 1, 4 >= 2
6.51/2.73	
6.51/2.73	
6.51/2.73	*U3_GAG(X, Y, Left, Right1, less_out_gg) -> INSERT_IN_GAG(X, Right1)
6.51/2.73	The graph contains the following edges 1 >= 1, 4 >= 2
6.51/2.73	
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(27)
6.51/2.73	YES
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(28)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(29) UsableRulesProof (EQUIVALENT)
6.51/2.73	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(30)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_AG(s(X), s(Y)) -> LESS_IN_AG(X, Y)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	LESS_IN_AG(x1, x2)  =  LESS_IN_AG(x2)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(31) PiDPToQDPProof (SOUND)
6.51/2.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(32)
6.51/2.73	Obligation:
6.51/2.73	Q DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y)
6.51/2.73	
6.51/2.73	R is empty.
6.51/2.73	Q is empty.
6.51/2.73	We have to consider all (P,Q,R)-chains.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(33) QDPSizeChangeProof (EQUIVALENT)
6.51/2.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. 
6.51/2.73	
6.51/2.73	From the DPs we obtained the following set of size-change graphs:
6.51/2.73	*LESS_IN_AG(s(Y)) -> LESS_IN_AG(Y)
6.51/2.73	The graph contains the following edges 1 > 1
6.51/2.73	
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(34)
6.51/2.73	YES
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(35)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_AAG(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> INSERT_IN_AAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   insert_in_aag(X, void, tree(X, void, void)) -> insert_out_aag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_aag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_aag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_aag(X, Y, Left, Right, Left1, less_in_ag(X, Y))
6.51/2.73	   less_in_ag(0, s(X1)) -> less_out_ag(0, s(X1))
6.51/2.73	   less_in_ag(s(X), s(Y)) -> U5_ag(X, Y, less_in_ag(X, Y))
6.51/2.73	   U5_ag(X, Y, less_out_ag(X, Y)) -> less_out_ag(s(X), s(Y))
6.51/2.73	   U1_aag(X, Y, Left, Right, Left1, less_out_ag(X, Y)) -> U2_aag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, void, tree(X, void, void)) -> insert_out_gag(X, void, tree(X, void, void))
6.51/2.73	   insert_in_gag(X, tree(X, Left, Right), tree(X, Left, Right)) -> insert_out_gag(X, tree(X, Left, Right), tree(X, Left, Right))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right)) -> U1_gag(X, Y, Left, Right, Left1, less_in_gg(X, Y))
6.51/2.73	   less_in_gg(0, s(X1)) -> less_out_gg(0, s(X1))
6.51/2.73	   less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y))
6.51/2.73	   U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y))
6.51/2.73	   U1_gag(X, Y, Left, Right, Left1, less_out_gg(X, Y)) -> U2_gag(X, Y, Left, Right, Left1, insert_in_gag(X, Left, Left1))
6.51/2.73	   insert_in_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_gag(X, Y, Left, Right, Right1, less_in_gg(Y, X))
6.51/2.73	   U3_gag(X, Y, Left, Right, Right1, less_out_gg(Y, X)) -> U4_gag(X, Y, Left, Right, Right1, insert_in_gag(X, Right, Right1))
6.51/2.73	   U4_gag(X, Y, Left, Right, Right1, insert_out_gag(X, Right, Right1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	   U2_gag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_gag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   U2_aag(X, Y, Left, Right, Left1, insert_out_gag(X, Left, Left1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left1, Right))
6.51/2.73	   insert_in_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_aag(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	   U3_aag(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> U4_aag(X, Y, Left, Right, Right1, insert_in_aag(X, Right, Right1))
6.51/2.73	   U4_aag(X, Y, Left, Right, Right1, insert_out_aag(X, Right, Right1)) -> insert_out_aag(X, tree(Y, Left, Right), tree(Y, Left, Right1))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	insert_in_aag(x1, x2, x3)  =  insert_in_aag(x3)
6.51/2.73	
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	void  =  void
6.51/2.73	
6.51/2.73	insert_out_aag(x1, x2, x3)  =  insert_out_aag(x1, x2)
6.51/2.73	
6.51/2.73	U1_aag(x1, x2, x3, x4, x5, x6)  =  U1_aag(x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ag(x1, x2)  =  less_in_ag(x2)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	less_out_ag(x1, x2)  =  less_out_ag(x1)
6.51/2.73	
6.51/2.73	U5_ag(x1, x2, x3)  =  U5_ag(x3)
6.51/2.73	
6.51/2.73	U2_aag(x1, x2, x3, x4, x5, x6)  =  U2_aag(x1, x2, x4, x6)
6.51/2.73	
6.51/2.73	insert_in_gag(x1, x2, x3)  =  insert_in_gag(x1, x3)
6.51/2.73	
6.51/2.73	insert_out_gag(x1, x2, x3)  =  insert_out_gag(x2)
6.51/2.73	
6.51/2.73	U1_gag(x1, x2, x3, x4, x5, x6)  =  U1_gag(x1, x2, x4, x5, x6)
6.51/2.73	
6.51/2.73	less_in_gg(x1, x2)  =  less_in_gg(x1, x2)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_out_gg(x1, x2)  =  less_out_gg
6.51/2.73	
6.51/2.73	U5_gg(x1, x2, x3)  =  U5_gg(x3)
6.51/2.73	
6.51/2.73	U2_gag(x1, x2, x3, x4, x5, x6)  =  U2_gag(x2, x4, x6)
6.51/2.73	
6.51/2.73	U3_gag(x1, x2, x3, x4, x5, x6)  =  U3_gag(x1, x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	U4_gag(x1, x2, x3, x4, x5, x6)  =  U4_gag(x2, x3, x6)
6.51/2.73	
6.51/2.73	U3_aag(x1, x2, x3, x4, x5, x6)  =  U3_aag(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	U4_aag(x1, x2, x3, x4, x5, x6)  =  U4_aag(x2, x3, x6)
6.51/2.73	
6.51/2.73	INSERT_IN_AAG(x1, x2, x3)  =  INSERT_IN_AAG(x3)
6.51/2.73	
6.51/2.73	U3_AAG(x1, x2, x3, x4, x5, x6)  =  U3_AAG(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(36) UsableRulesProof (EQUIVALENT)
6.51/2.73	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(37)
6.51/2.73	Obligation:
6.51/2.73	Pi DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   INSERT_IN_AAG(X, tree(Y, Left, Right), tree(Y, Left, Right1)) -> U3_AAG(X, Y, Left, Right, Right1, less_in_ga(Y, X))
6.51/2.73	   U3_AAG(X, Y, Left, Right, Right1, less_out_ga(Y, X)) -> INSERT_IN_AAG(X, Right, Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   less_in_ga(0, s(X1)) -> less_out_ga(0, s(X1))
6.51/2.73	   less_in_ga(s(X), s(Y)) -> U5_ga(X, Y, less_in_ga(X, Y))
6.51/2.73	   U5_ga(X, Y, less_out_ga(X, Y)) -> less_out_ga(s(X), s(Y))
6.51/2.73	
6.51/2.73	The argument filtering Pi contains the following mapping:
6.51/2.73	tree(x1, x2, x3)  =  tree(x1, x2, x3)
6.51/2.73	
6.51/2.73	s(x1)  =  s(x1)
6.51/2.73	
6.51/2.73	0  =  0
6.51/2.73	
6.51/2.73	less_in_ga(x1, x2)  =  less_in_ga(x1)
6.51/2.73	
6.51/2.73	less_out_ga(x1, x2)  =  less_out_ga
6.51/2.73	
6.51/2.73	U5_ga(x1, x2, x3)  =  U5_ga(x3)
6.51/2.73	
6.51/2.73	INSERT_IN_AAG(x1, x2, x3)  =  INSERT_IN_AAG(x3)
6.51/2.73	
6.51/2.73	U3_AAG(x1, x2, x3, x4, x5, x6)  =  U3_AAG(x2, x3, x5, x6)
6.51/2.73	
6.51/2.73	
6.51/2.73	We have to consider all (P,R,Pi)-chains
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(38) PiDPToQDPProof (SOUND)
6.51/2.73	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(39)
6.51/2.73	Obligation:
6.51/2.73	Q DP problem:
6.51/2.73	The TRS P consists of the following rules:
6.51/2.73	
6.51/2.73	   INSERT_IN_AAG(tree(Y, Left, Right1)) -> U3_AAG(Y, Left, Right1, less_in_ga(Y))
6.51/2.73	   U3_AAG(Y, Left, Right1, less_out_ga) -> INSERT_IN_AAG(Right1)
6.51/2.73	
6.51/2.73	The TRS R consists of the following rules:
6.51/2.73	
6.51/2.73	   less_in_ga(0) -> less_out_ga
6.51/2.73	   less_in_ga(s(X)) -> U5_ga(less_in_ga(X))
6.51/2.73	   U5_ga(less_out_ga) -> less_out_ga
6.51/2.73	
6.51/2.73	The set Q consists of the following terms:
6.51/2.73	
6.51/2.73	   less_in_ga(x0)
6.51/2.73	   U5_ga(x0)
6.51/2.73	
6.51/2.73	We have to consider all (P,Q,R)-chains.
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(40) QDPSizeChangeProof (EQUIVALENT)
6.51/2.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. 
6.51/2.73	
6.51/2.73	From the DPs we obtained the following set of size-change graphs:
6.51/2.73	*U3_AAG(Y, Left, Right1, less_out_ga) -> INSERT_IN_AAG(Right1)
6.51/2.73	The graph contains the following edges 3 >= 1
6.51/2.73	
6.51/2.73	
6.51/2.73	*INSERT_IN_AAG(tree(Y, Left, Right1)) -> U3_AAG(Y, Left, Right1, less_in_ga(Y))
6.51/2.73	The graph contains the following edges 1 > 1, 1 > 2, 1 > 3
6.51/2.73	
6.51/2.73	
6.51/2.73	----------------------------------------
6.51/2.73	
6.51/2.73	(41)
6.51/2.73	YES
6.51/2.75	EOF