5.88/2.52	YES
6.43/2.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
6.43/2.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.43/2.54	
6.43/2.54	
6.43/2.54	Left Termination of the query pattern
6.43/2.54	
6.43/2.54	slowsort(g,a)
6.43/2.54	
6.43/2.54	w.r.t. the given Prolog program could successfully be proven:
6.43/2.54	
6.43/2.54	(0) Prolog
6.43/2.54	(1) PrologToPiTRSProof [SOUND, 0 ms]
6.43/2.54	(2) PiTRS
6.43/2.54	(3) DependencyPairsProof [EQUIVALENT, 1 ms]
6.43/2.54	(4) PiDP
6.43/2.54	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
6.43/2.54	(6) AND
6.43/2.54	    (7) PiDP
6.43/2.54	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
6.43/2.54	        (9) PiDP
6.43/2.54	        (10) PiDPToQDPProof [EQUIVALENT, 0 ms]
6.43/2.54	        (11) QDP
6.43/2.54	        (12) QDPSizeChangeProof [EQUIVALENT, 1 ms]
6.43/2.54	        (13) YES
6.43/2.54	    (14) PiDP
6.43/2.54	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
6.43/2.54	        (16) PiDP
6.43/2.54	        (17) PiDPToQDPProof [SOUND, 0 ms]
6.43/2.54	        (18) QDP
6.43/2.54	        (19) UsableRulesReductionPairsProof [EQUIVALENT, 14 ms]
6.43/2.54	        (20) QDP
6.43/2.54	        (21) DependencyGraphProof [EQUIVALENT, 0 ms]
6.43/2.54	        (22) TRUE
6.43/2.54	    (23) PiDP
6.43/2.54	        (24) UsableRulesProof [EQUIVALENT, 0 ms]
6.43/2.54	        (25) PiDP
6.43/2.54	        (26) PiDPToQDPProof [SOUND, 0 ms]
6.43/2.54	        (27) QDP
6.43/2.54	        (28) QDPSizeChangeProof [EQUIVALENT, 0 ms]
6.43/2.54	        (29) YES
6.43/2.54	    (30) PiDP
6.43/2.54	        (31) UsableRulesProof [EQUIVALENT, 0 ms]
6.43/2.54	        (32) PiDP
6.43/2.54	        (33) PiDPToQDPProof [SOUND, 0 ms]
6.43/2.54	        (34) QDP
6.43/2.54	        (35) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
6.43/2.54	        (36) QDP
6.43/2.54	        (37) DependencyGraphProof [EQUIVALENT, 0 ms]
6.43/2.54	        (38) TRUE
6.43/2.54	
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(0)
6.43/2.54	Obligation:
6.43/2.54	Clauses:
6.43/2.54	
6.43/2.54	slowsort(X, Y) :- ','(perm(X, Y), sorted(Y)).
6.43/2.54	sorted([]).
6.43/2.54	sorted(.(X, [])).
6.43/2.54	sorted(.(X, .(Y, Z))) :- ','(le(X, Y), sorted(.(Y, Z))).
6.43/2.54	perm([], []).
6.43/2.54	perm(.(X, .(Y, [])), .(U, .(V, []))) :- ','(delete(U, .(X, Y), Z), perm(Z, V)).
6.43/2.54	delete(X, .(X, Y), Y).
6.43/2.54	delete(X, .(Y, Z), W) :- delete(X, Z, W).
6.43/2.54	le(s(X), s(Y)) :- le(X, Y).
6.43/2.54	le(0, s(X)).
6.43/2.54	le(0, 0).
6.43/2.54	
6.43/2.54	
6.43/2.54	Query: slowsort(g,a)
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(1) PrologToPiTRSProof (SOUND)
6.43/2.54	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
6.43/2.54	
6.43/2.54	slowsort_in_2: (b,f)
6.43/2.54	
6.43/2.54	perm_in_2: (b,f)
6.43/2.54	
6.43/2.54	delete_in_3: (f,b,f)
6.43/2.54	
6.43/2.54	sorted_in_1: (b)
6.43/2.54	
6.43/2.54	le_in_2: (b,b)
6.43/2.54	
6.43/2.54	Transforming Prolog into the following Term Rewriting System:
6.43/2.54	
6.43/2.54	Pi-finite rewrite system:
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	
6.43/2.54	
6.43/2.54	
6.43/2.54	
6.43/2.54	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
6.43/2.54	
6.43/2.54	
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(2)
6.43/2.54	Obligation:
6.43/2.54	Pi-finite rewrite system:
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(3) DependencyPairsProof (EQUIVALENT)
6.43/2.54	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   SLOWSORT_IN_GA(X, Y) -> U1_GA(X, Y, perm_in_ga(X, Y))
6.43/2.54	   SLOWSORT_IN_GA(X, Y) -> PERM_IN_GA(X, Y)
6.43/2.54	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> U5_GA(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_AGA(U, .(X, Y), Z)
6.43/2.54	   DELETE_IN_AGA(X, .(Y, Z), W) -> U7_AGA(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   DELETE_IN_AGA(X, .(Y, Z), W) -> DELETE_IN_AGA(X, Z, W)
6.43/2.54	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_GA(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> PERM_IN_GA(Z, V)
6.43/2.54	   U1_GA(X, Y, perm_out_ga(X, Y)) -> U2_GA(X, Y, sorted_in_g(Y))
6.43/2.54	   U1_GA(X, Y, perm_out_ga(X, Y)) -> SORTED_IN_G(Y)
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y)
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y))
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z))
6.43/2.54	
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	SLOWSORT_IN_GA(x1, x2)  =  SLOWSORT_IN_GA(x1)
6.43/2.54	
6.43/2.54	U1_GA(x1, x2, x3)  =  U1_GA(x3)
6.43/2.54	
6.43/2.54	PERM_IN_GA(x1, x2)  =  PERM_IN_GA(x1)
6.43/2.54	
6.43/2.54	U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x5)
6.43/2.54	
6.43/2.54	DELETE_IN_AGA(x1, x2, x3)  =  DELETE_IN_AGA(x2)
6.43/2.54	
6.43/2.54	U7_AGA(x1, x2, x3, x4, x5)  =  U7_AGA(x5)
6.43/2.54	
6.43/2.54	U6_GA(x1, x2, x3, x4, x5)  =  U6_GA(x3, x5)
6.43/2.54	
6.43/2.54	U2_GA(x1, x2, x3)  =  U2_GA(x2, x3)
6.43/2.54	
6.43/2.54	SORTED_IN_G(x1)  =  SORTED_IN_G(x1)
6.43/2.54	
6.43/2.54	U3_G(x1, x2, x3, x4)  =  U3_G(x2, x3, x4)
6.43/2.54	
6.43/2.54	LE_IN_GG(x1, x2)  =  LE_IN_GG(x1, x2)
6.43/2.54	
6.43/2.54	U8_GG(x1, x2, x3)  =  U8_GG(x3)
6.43/2.54	
6.43/2.54	U4_G(x1, x2, x3, x4)  =  U4_G(x4)
6.43/2.54	
6.43/2.54	
6.43/2.54	We have to consider all (P,R,Pi)-chains
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(4)
6.43/2.54	Obligation:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   SLOWSORT_IN_GA(X, Y) -> U1_GA(X, Y, perm_in_ga(X, Y))
6.43/2.54	   SLOWSORT_IN_GA(X, Y) -> PERM_IN_GA(X, Y)
6.43/2.54	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> U5_GA(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> DELETE_IN_AGA(U, .(X, Y), Z)
6.43/2.54	   DELETE_IN_AGA(X, .(Y, Z), W) -> U7_AGA(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   DELETE_IN_AGA(X, .(Y, Z), W) -> DELETE_IN_AGA(X, Z, W)
6.43/2.54	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_GA(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> PERM_IN_GA(Z, V)
6.43/2.54	   U1_GA(X, Y, perm_out_ga(X, Y)) -> U2_GA(X, Y, sorted_in_g(Y))
6.43/2.54	   U1_GA(X, Y, perm_out_ga(X, Y)) -> SORTED_IN_G(Y)
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> LE_IN_GG(X, Y)
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> U8_GG(X, Y, le_in_gg(X, Y))
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> U4_G(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z))
6.43/2.54	
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	SLOWSORT_IN_GA(x1, x2)  =  SLOWSORT_IN_GA(x1)
6.43/2.54	
6.43/2.54	U1_GA(x1, x2, x3)  =  U1_GA(x3)
6.43/2.54	
6.43/2.54	PERM_IN_GA(x1, x2)  =  PERM_IN_GA(x1)
6.43/2.54	
6.43/2.54	U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x5)
6.43/2.54	
6.43/2.54	DELETE_IN_AGA(x1, x2, x3)  =  DELETE_IN_AGA(x2)
6.43/2.54	
6.43/2.54	U7_AGA(x1, x2, x3, x4, x5)  =  U7_AGA(x5)
6.43/2.54	
6.43/2.54	U6_GA(x1, x2, x3, x4, x5)  =  U6_GA(x3, x5)
6.43/2.54	
6.43/2.54	U2_GA(x1, x2, x3)  =  U2_GA(x2, x3)
6.43/2.54	
6.43/2.54	SORTED_IN_G(x1)  =  SORTED_IN_G(x1)
6.43/2.54	
6.43/2.54	U3_G(x1, x2, x3, x4)  =  U3_G(x2, x3, x4)
6.43/2.54	
6.43/2.54	LE_IN_GG(x1, x2)  =  LE_IN_GG(x1, x2)
6.43/2.54	
6.43/2.54	U8_GG(x1, x2, x3)  =  U8_GG(x3)
6.43/2.54	
6.43/2.54	U4_G(x1, x2, x3, x4)  =  U4_G(x4)
6.43/2.54	
6.43/2.54	
6.43/2.54	We have to consider all (P,R,Pi)-chains
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(5) DependencyGraphProof (EQUIVALENT)
6.43/2.54	The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 10 less nodes.
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(6)
6.43/2.54	Complex Obligation (AND)
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(7)
6.43/2.54	Obligation:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	LE_IN_GG(x1, x2)  =  LE_IN_GG(x1, x2)
6.43/2.54	
6.43/2.54	
6.43/2.54	We have to consider all (P,R,Pi)-chains
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(8) UsableRulesProof (EQUIVALENT)
6.43/2.54	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(9)
6.43/2.54	Obligation:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	
6.43/2.54	R is empty.
6.43/2.54	Pi is empty.
6.43/2.54	We have to consider all (P,R,Pi)-chains
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(10) PiDPToQDPProof (EQUIVALENT)
6.43/2.54	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(11)
6.43/2.54	Obligation:
6.43/2.54	Q DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	
6.43/2.54	R is empty.
6.43/2.54	Q is empty.
6.43/2.54	We have to consider all (P,Q,R)-chains.
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(12) QDPSizeChangeProof (EQUIVALENT)
6.43/2.54	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.43/2.54	
6.43/2.54	From the DPs we obtained the following set of size-change graphs:
6.43/2.54	*LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y)
6.43/2.54	The graph contains the following edges 1 > 1, 2 > 2
6.43/2.54	
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(13)
6.43/2.54	YES
6.43/2.54	
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(14)
6.43/2.54	Obligation:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z))
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.54	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.54	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.54	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.54	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.54	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.54	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.54	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.54	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.54	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.54	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.54	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.54	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.54	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.54	
6.43/2.54	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.54	
6.43/2.54	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.54	
6.43/2.54	[]  =  []
6.43/2.54	
6.43/2.54	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.54	
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.54	
6.43/2.54	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.54	
6.43/2.54	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.54	
6.43/2.54	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.54	
6.43/2.54	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.54	
6.43/2.54	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.54	
6.43/2.54	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.54	
6.43/2.54	sorted_out_g(x1)  =  sorted_out_g
6.43/2.54	
6.43/2.54	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.54	
6.43/2.54	s(x1)  =  s(x1)
6.43/2.54	
6.43/2.54	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.54	
6.43/2.54	0  =  0
6.43/2.54	
6.43/2.54	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.54	
6.43/2.54	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.54	
6.43/2.54	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.54	
6.43/2.54	SORTED_IN_G(x1)  =  SORTED_IN_G(x1)
6.43/2.54	
6.43/2.54	U3_G(x1, x2, x3, x4)  =  U3_G(x2, x3, x4)
6.43/2.54	
6.43/2.54	
6.43/2.54	We have to consider all (P,R,Pi)-chains
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(15) UsableRulesProof (EQUIVALENT)
6.43/2.54	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.43/2.54	----------------------------------------
6.43/2.54	
6.43/2.54	(16)
6.43/2.54	Obligation:
6.43/2.54	Pi DP problem:
6.43/2.54	The TRS P consists of the following rules:
6.43/2.54	
6.43/2.54	   U3_G(X, Y, Z, le_out_gg(X, Y)) -> SORTED_IN_G(.(Y, Z))
6.43/2.54	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(X, Y, Z, le_in_gg(X, Y))
6.43/2.54	
6.43/2.54	The TRS R consists of the following rules:
6.43/2.54	
6.43/2.54	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.54	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.54	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.54	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.54	
6.43/2.54	The argument filtering Pi contains the following mapping:
6.43/2.54	.(x1, x2)  =  .(x1, x2)
6.43/2.54	
6.43/2.54	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.55	
6.43/2.55	s(x1)  =  s(x1)
6.43/2.55	
6.43/2.55	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.55	
6.43/2.55	0  =  0
6.43/2.55	
6.43/2.55	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.55	
6.43/2.55	SORTED_IN_G(x1)  =  SORTED_IN_G(x1)
6.43/2.55	
6.43/2.55	U3_G(x1, x2, x3, x4)  =  U3_G(x2, x3, x4)
6.43/2.55	
6.43/2.55	
6.43/2.55	We have to consider all (P,R,Pi)-chains
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(17) PiDPToQDPProof (SOUND)
6.43/2.55	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(18)
6.43/2.55	Obligation:
6.43/2.55	Q DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z))
6.43/2.55	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y))
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y))
6.43/2.55	   le_in_gg(0, s(X)) -> le_out_gg
6.43/2.55	   le_in_gg(0, 0) -> le_out_gg
6.43/2.55	   U8_gg(le_out_gg) -> le_out_gg
6.43/2.55	
6.43/2.55	The set Q consists of the following terms:
6.43/2.55	
6.43/2.55	   le_in_gg(x0, x1)
6.43/2.55	   U8_gg(x0)
6.43/2.55	
6.43/2.55	We have to consider all (P,Q,R)-chains.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(19) UsableRulesReductionPairsProof (EQUIVALENT)
6.43/2.55	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
6.43/2.55	
6.43/2.55	No dependency pairs are removed.
6.43/2.55	
6.43/2.55	The following rules are removed from R:
6.43/2.55	
6.43/2.55	   le_in_gg(s(X), s(Y)) -> U8_gg(le_in_gg(X, Y))
6.43/2.55	   le_in_gg(0, s(X)) -> le_out_gg
6.43/2.55	   le_in_gg(0, 0) -> le_out_gg
6.43/2.55	Used ordering: POLO with Polynomial interpretation [POLO]:
6.43/2.55	
6.43/2.55	   POL(.(x_1, x_2)) = x_1 + 2*x_2
6.43/2.55	   POL(0) = 0
6.43/2.55	   POL(SORTED_IN_G(x_1)) = x_1
6.43/2.55	   POL(U3_G(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3
6.43/2.55	   POL(U8_gg(x_1)) = 2*x_1
6.43/2.55	   POL(le_in_gg(x_1, x_2)) = x_1 + x_2
6.43/2.55	   POL(le_out_gg) = 0
6.43/2.55	   POL(s(x_1)) = 2 + 2*x_1
6.43/2.55	
6.43/2.55	
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(20)
6.43/2.55	Obligation:
6.43/2.55	Q DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U3_G(Y, Z, le_out_gg) -> SORTED_IN_G(.(Y, Z))
6.43/2.55	   SORTED_IN_G(.(X, .(Y, Z))) -> U3_G(Y, Z, le_in_gg(X, Y))
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   U8_gg(le_out_gg) -> le_out_gg
6.43/2.55	
6.43/2.55	The set Q consists of the following terms:
6.43/2.55	
6.43/2.55	   le_in_gg(x0, x1)
6.43/2.55	   U8_gg(x0)
6.43/2.55	
6.43/2.55	We have to consider all (P,Q,R)-chains.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(21) DependencyGraphProof (EQUIVALENT)
6.43/2.55	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(22)
6.43/2.55	TRUE
6.43/2.55	
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(23)
6.43/2.55	Obligation:
6.43/2.55	Pi DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   DELETE_IN_AGA(X, .(Y, Z), W) -> DELETE_IN_AGA(X, Z, W)
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.55	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.55	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.55	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.55	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.55	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.55	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.55	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.55	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.55	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.55	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.55	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.55	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.55	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.55	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.55	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.55	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.55	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.55	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.55	
6.43/2.55	The argument filtering Pi contains the following mapping:
6.43/2.55	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.55	
6.43/2.55	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.55	
6.43/2.55	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.55	
6.43/2.55	[]  =  []
6.43/2.55	
6.43/2.55	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.55	
6.43/2.55	.(x1, x2)  =  .(x1, x2)
6.43/2.55	
6.43/2.55	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.55	
6.43/2.55	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.55	
6.43/2.55	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.55	
6.43/2.55	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.55	
6.43/2.55	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.55	
6.43/2.55	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.55	
6.43/2.55	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.55	
6.43/2.55	sorted_out_g(x1)  =  sorted_out_g
6.43/2.55	
6.43/2.55	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.55	
6.43/2.55	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.55	
6.43/2.55	s(x1)  =  s(x1)
6.43/2.55	
6.43/2.55	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.55	
6.43/2.55	0  =  0
6.43/2.55	
6.43/2.55	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.55	
6.43/2.55	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.55	
6.43/2.55	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.55	
6.43/2.55	DELETE_IN_AGA(x1, x2, x3)  =  DELETE_IN_AGA(x2)
6.43/2.55	
6.43/2.55	
6.43/2.55	We have to consider all (P,R,Pi)-chains
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(24) UsableRulesProof (EQUIVALENT)
6.43/2.55	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(25)
6.43/2.55	Obligation:
6.43/2.55	Pi DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   DELETE_IN_AGA(X, .(Y, Z), W) -> DELETE_IN_AGA(X, Z, W)
6.43/2.55	
6.43/2.55	R is empty.
6.43/2.55	The argument filtering Pi contains the following mapping:
6.43/2.55	.(x1, x2)  =  .(x1, x2)
6.43/2.55	
6.43/2.55	DELETE_IN_AGA(x1, x2, x3)  =  DELETE_IN_AGA(x2)
6.43/2.55	
6.43/2.55	
6.43/2.55	We have to consider all (P,R,Pi)-chains
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(26) PiDPToQDPProof (SOUND)
6.43/2.55	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(27)
6.43/2.55	Obligation:
6.43/2.55	Q DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   DELETE_IN_AGA(.(Y, Z)) -> DELETE_IN_AGA(Z)
6.43/2.55	
6.43/2.55	R is empty.
6.43/2.55	Q is empty.
6.43/2.55	We have to consider all (P,Q,R)-chains.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(28) QDPSizeChangeProof (EQUIVALENT)
6.43/2.55	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.43/2.55	
6.43/2.55	From the DPs we obtained the following set of size-change graphs:
6.43/2.55	*DELETE_IN_AGA(.(Y, Z)) -> DELETE_IN_AGA(Z)
6.43/2.55	The graph contains the following edges 1 > 1
6.43/2.55	
6.43/2.55	
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(29)
6.43/2.55	YES
6.43/2.55	
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(30)
6.43/2.55	Obligation:
6.43/2.55	Pi DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> PERM_IN_GA(Z, V)
6.43/2.55	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> U5_GA(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   slowsort_in_ga(X, Y) -> U1_ga(X, Y, perm_in_ga(X, Y))
6.43/2.55	   perm_in_ga([], []) -> perm_out_ga([], [])
6.43/2.55	   perm_in_ga(.(X, .(Y, [])), .(U, .(V, []))) -> U5_ga(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.55	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.55	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.55	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.55	   U5_ga(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> U6_ga(X, Y, U, V, perm_in_ga(Z, V))
6.43/2.55	   U6_ga(X, Y, U, V, perm_out_ga(Z, V)) -> perm_out_ga(.(X, .(Y, [])), .(U, .(V, [])))
6.43/2.55	   U1_ga(X, Y, perm_out_ga(X, Y)) -> U2_ga(X, Y, sorted_in_g(Y))
6.43/2.55	   sorted_in_g([]) -> sorted_out_g([])
6.43/2.55	   sorted_in_g(.(X, [])) -> sorted_out_g(.(X, []))
6.43/2.55	   sorted_in_g(.(X, .(Y, Z))) -> U3_g(X, Y, Z, le_in_gg(X, Y))
6.43/2.55	   le_in_gg(s(X), s(Y)) -> U8_gg(X, Y, le_in_gg(X, Y))
6.43/2.55	   le_in_gg(0, s(X)) -> le_out_gg(0, s(X))
6.43/2.55	   le_in_gg(0, 0) -> le_out_gg(0, 0)
6.43/2.55	   U8_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y))
6.43/2.55	   U3_g(X, Y, Z, le_out_gg(X, Y)) -> U4_g(X, Y, Z, sorted_in_g(.(Y, Z)))
6.43/2.55	   U4_g(X, Y, Z, sorted_out_g(.(Y, Z))) -> sorted_out_g(.(X, .(Y, Z)))
6.43/2.55	   U2_ga(X, Y, sorted_out_g(Y)) -> slowsort_out_ga(X, Y)
6.43/2.55	
6.43/2.55	The argument filtering Pi contains the following mapping:
6.43/2.55	slowsort_in_ga(x1, x2)  =  slowsort_in_ga(x1)
6.43/2.55	
6.43/2.55	U1_ga(x1, x2, x3)  =  U1_ga(x3)
6.43/2.55	
6.43/2.55	perm_in_ga(x1, x2)  =  perm_in_ga(x1)
6.43/2.55	
6.43/2.55	[]  =  []
6.43/2.55	
6.43/2.55	perm_out_ga(x1, x2)  =  perm_out_ga(x2)
6.43/2.55	
6.43/2.55	.(x1, x2)  =  .(x1, x2)
6.43/2.55	
6.43/2.55	U5_ga(x1, x2, x3, x4, x5)  =  U5_ga(x5)
6.43/2.55	
6.43/2.55	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.55	
6.43/2.55	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.55	
6.43/2.55	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.55	
6.43/2.55	U6_ga(x1, x2, x3, x4, x5)  =  U6_ga(x3, x5)
6.43/2.55	
6.43/2.55	U2_ga(x1, x2, x3)  =  U2_ga(x2, x3)
6.43/2.55	
6.43/2.55	sorted_in_g(x1)  =  sorted_in_g(x1)
6.43/2.55	
6.43/2.55	sorted_out_g(x1)  =  sorted_out_g
6.43/2.55	
6.43/2.55	U3_g(x1, x2, x3, x4)  =  U3_g(x2, x3, x4)
6.43/2.55	
6.43/2.55	le_in_gg(x1, x2)  =  le_in_gg(x1, x2)
6.43/2.55	
6.43/2.55	s(x1)  =  s(x1)
6.43/2.55	
6.43/2.55	U8_gg(x1, x2, x3)  =  U8_gg(x3)
6.43/2.55	
6.43/2.55	0  =  0
6.43/2.55	
6.43/2.55	le_out_gg(x1, x2)  =  le_out_gg
6.43/2.55	
6.43/2.55	U4_g(x1, x2, x3, x4)  =  U4_g(x4)
6.43/2.55	
6.43/2.55	slowsort_out_ga(x1, x2)  =  slowsort_out_ga(x2)
6.43/2.55	
6.43/2.55	PERM_IN_GA(x1, x2)  =  PERM_IN_GA(x1)
6.43/2.55	
6.43/2.55	U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x5)
6.43/2.55	
6.43/2.55	
6.43/2.55	We have to consider all (P,R,Pi)-chains
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(31) UsableRulesProof (EQUIVALENT)
6.43/2.55	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(32)
6.43/2.55	Obligation:
6.43/2.55	Pi DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U5_GA(X, Y, U, V, delete_out_aga(U, .(X, Y), Z)) -> PERM_IN_GA(Z, V)
6.43/2.55	   PERM_IN_GA(.(X, .(Y, [])), .(U, .(V, []))) -> U5_GA(X, Y, U, V, delete_in_aga(U, .(X, Y), Z))
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y)
6.43/2.55	   delete_in_aga(X, .(Y, Z), W) -> U7_aga(X, Y, Z, W, delete_in_aga(X, Z, W))
6.43/2.55	   U7_aga(X, Y, Z, W, delete_out_aga(X, Z, W)) -> delete_out_aga(X, .(Y, Z), W)
6.43/2.55	
6.43/2.55	The argument filtering Pi contains the following mapping:
6.43/2.55	[]  =  []
6.43/2.55	
6.43/2.55	.(x1, x2)  =  .(x1, x2)
6.43/2.55	
6.43/2.55	delete_in_aga(x1, x2, x3)  =  delete_in_aga(x2)
6.43/2.55	
6.43/2.55	delete_out_aga(x1, x2, x3)  =  delete_out_aga(x1, x3)
6.43/2.55	
6.43/2.55	U7_aga(x1, x2, x3, x4, x5)  =  U7_aga(x5)
6.43/2.55	
6.43/2.55	PERM_IN_GA(x1, x2)  =  PERM_IN_GA(x1)
6.43/2.55	
6.43/2.55	U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x5)
6.43/2.55	
6.43/2.55	
6.43/2.55	We have to consider all (P,R,Pi)-chains
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(33) PiDPToQDPProof (SOUND)
6.43/2.55	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(34)
6.43/2.55	Obligation:
6.43/2.55	Q DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U5_GA(delete_out_aga(U, Z)) -> PERM_IN_GA(Z)
6.43/2.55	   PERM_IN_GA(.(X, .(Y, []))) -> U5_GA(delete_in_aga(.(X, Y)))
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   delete_in_aga(.(X, Y)) -> delete_out_aga(X, Y)
6.43/2.55	   delete_in_aga(.(Y, Z)) -> U7_aga(delete_in_aga(Z))
6.43/2.55	   U7_aga(delete_out_aga(X, W)) -> delete_out_aga(X, W)
6.43/2.55	
6.43/2.55	The set Q consists of the following terms:
6.43/2.55	
6.43/2.55	   delete_in_aga(x0)
6.43/2.55	   U7_aga(x0)
6.43/2.55	
6.43/2.55	We have to consider all (P,Q,R)-chains.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(35) UsableRulesReductionPairsProof (EQUIVALENT)
6.43/2.55	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
6.43/2.55	
6.43/2.55	The following dependency pairs can be deleted:
6.43/2.55	
6.43/2.55	   PERM_IN_GA(.(X, .(Y, []))) -> U5_GA(delete_in_aga(.(X, Y)))
6.43/2.55	The following rules are removed from R:
6.43/2.55	
6.43/2.55	   delete_in_aga(.(X, Y)) -> delete_out_aga(X, Y)
6.43/2.55	Used ordering: POLO with Polynomial interpretation [POLO]:
6.43/2.55	
6.43/2.55	   POL(.(x_1, x_2)) = 2*x_1 + 2*x_2
6.43/2.55	   POL(PERM_IN_GA(x_1)) = 2 + 2*x_1
6.43/2.55	   POL(U5_GA(x_1)) = 2 + x_1
6.43/2.55	   POL(U7_aga(x_1)) = x_1
6.43/2.55	   POL([]) = 1
6.43/2.55	   POL(delete_in_aga(x_1)) = 2 + 2*x_1
6.43/2.55	   POL(delete_out_aga(x_1, x_2)) = 2*x_1 + 2*x_2
6.43/2.55	
6.43/2.55	
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(36)
6.43/2.55	Obligation:
6.43/2.55	Q DP problem:
6.43/2.55	The TRS P consists of the following rules:
6.43/2.55	
6.43/2.55	   U5_GA(delete_out_aga(U, Z)) -> PERM_IN_GA(Z)
6.43/2.55	
6.43/2.55	The TRS R consists of the following rules:
6.43/2.55	
6.43/2.55	   delete_in_aga(.(Y, Z)) -> U7_aga(delete_in_aga(Z))
6.43/2.55	   U7_aga(delete_out_aga(X, W)) -> delete_out_aga(X, W)
6.43/2.55	
6.43/2.55	The set Q consists of the following terms:
6.43/2.55	
6.43/2.55	   delete_in_aga(x0)
6.43/2.55	   U7_aga(x0)
6.43/2.55	
6.43/2.55	We have to consider all (P,Q,R)-chains.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(37) DependencyGraphProof (EQUIVALENT)
6.43/2.55	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
6.43/2.55	----------------------------------------
6.43/2.55	
6.43/2.55	(38)
6.43/2.55	TRUE
6.60/2.64	EOF