7.43/2.76	YES
7.77/2.78	proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl
7.77/2.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
7.77/2.78	
7.77/2.78	
7.77/2.78	Left Termination of the query pattern
7.77/2.78	
7.77/2.78	weight(g,a)
7.77/2.78	
7.77/2.78	w.r.t. the given Prolog program could successfully be proven:
7.77/2.78	
7.77/2.78	(0) Prolog
7.77/2.78	(1) PrologToPiTRSProof [SOUND, 25 ms]
7.77/2.78	(2) PiTRS
7.77/2.78	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
7.77/2.78	(4) PiDP
7.77/2.78	(5) DependencyGraphProof [EQUIVALENT, 3 ms]
7.77/2.78	(6) AND
7.77/2.78	    (7) PiDP
7.77/2.78	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
7.77/2.78	        (9) PiDP
7.77/2.78	        (10) PiDPToQDPProof [SOUND, 12 ms]
7.77/2.78	        (11) QDP
7.77/2.78	        (12) UsableRulesReductionPairsProof [EQUIVALENT, 50 ms]
7.77/2.78	        (13) QDP
7.77/2.78	        (14) PisEmptyProof [EQUIVALENT, 0 ms]
7.77/2.78	        (15) YES
7.77/2.78	    (16) PiDP
7.77/2.78	        (17) UsableRulesProof [EQUIVALENT, 0 ms]
7.77/2.78	        (18) PiDP
7.77/2.78	        (19) PiDPToQDPProof [SOUND, 0 ms]
7.77/2.78	        (20) QDP
7.77/2.78	        (21) UsableRulesReductionPairsProof [EQUIVALENT, 22 ms]
7.77/2.78	        (22) QDP
7.77/2.78	        (23) DependencyGraphProof [EQUIVALENT, 0 ms]
7.77/2.78	        (24) TRUE
7.77/2.78	
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(0)
7.77/2.78	Obligation:
7.77/2.78	Clauses:
7.77/2.78	
7.77/2.78	sum(.(s(N), XS), .(M, YS), ZS) :- sum(.(N, XS), .(s(M), YS), ZS).
7.77/2.78	sum(.(0, XS), YS, ZS) :- sum(XS, YS, ZS).
7.77/2.78	sum([], YS, YS).
7.77/2.78	weight(.(N, .(M, XS)), X) :- ','(sum(.(N, .(M, XS)), .(0, XS), YS), weight(YS, X)).
7.77/2.78	weight(.(X, []), X).
7.77/2.78	
7.77/2.78	
7.77/2.78	Query: weight(g,a)
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(1) PrologToPiTRSProof (SOUND)
7.77/2.78	We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
7.77/2.78	
7.77/2.78	weight_in_2: (b,f)
7.77/2.78	
7.77/2.78	sum_in_3: (b,b,f)
7.77/2.78	
7.77/2.78	Transforming Prolog into the following Term Rewriting System:
7.77/2.78	
7.77/2.78	Pi-finite rewrite system:
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	
7.77/2.78	
7.77/2.78	
7.77/2.78	
7.77/2.78	Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
7.77/2.78	
7.77/2.78	
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(2)
7.77/2.78	Obligation:
7.77/2.78	Pi-finite rewrite system:
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(3) DependencyPairsProof (EQUIVALENT)
7.77/2.78	Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> SUM_IN_GGA(.(N, .(M, XS)), .(0, XS), YS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> U1_GGA(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS)
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> U2_GGA(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS)
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_GA(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X)
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	WEIGHT_IN_GA(x1, x2)  =  WEIGHT_IN_GA(x1)
7.77/2.78	
7.77/2.78	U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x5)
7.77/2.78	
7.77/2.78	SUM_IN_GGA(x1, x2, x3)  =  SUM_IN_GGA(x1, x2)
7.77/2.78	
7.77/2.78	U1_GGA(x1, x2, x3, x4, x5, x6)  =  U1_GGA(x6)
7.77/2.78	
7.77/2.78	U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
7.77/2.78	
7.77/2.78	U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x5)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(4)
7.77/2.78	Obligation:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> SUM_IN_GGA(.(N, .(M, XS)), .(0, XS), YS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> U1_GGA(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS)
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> U2_GGA(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS)
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_GA(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X)
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	WEIGHT_IN_GA(x1, x2)  =  WEIGHT_IN_GA(x1)
7.77/2.78	
7.77/2.78	U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x5)
7.77/2.78	
7.77/2.78	SUM_IN_GGA(x1, x2, x3)  =  SUM_IN_GGA(x1, x2)
7.77/2.78	
7.77/2.78	U1_GGA(x1, x2, x3, x4, x5, x6)  =  U1_GGA(x6)
7.77/2.78	
7.77/2.78	U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
7.77/2.78	
7.77/2.78	U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x5)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(5) DependencyGraphProof (EQUIVALENT)
7.77/2.78	The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(6)
7.77/2.78	Complex Obligation (AND)
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(7)
7.77/2.78	Obligation:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS)
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	SUM_IN_GGA(x1, x2, x3)  =  SUM_IN_GGA(x1, x2)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(8) UsableRulesProof (EQUIVALENT)
7.77/2.78	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(9)
7.77/2.78	Obligation:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS, ZS) -> SUM_IN_GGA(XS, YS, ZS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS), ZS) -> SUM_IN_GGA(.(N, XS), .(s(M), YS), ZS)
7.77/2.78	
7.77/2.78	R is empty.
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	SUM_IN_GGA(x1, x2, x3)  =  SUM_IN_GGA(x1, x2)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(10) PiDPToQDPProof (SOUND)
7.77/2.78	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(11)
7.77/2.78	Obligation:
7.77/2.78	Q DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS) -> SUM_IN_GGA(XS, YS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS)) -> SUM_IN_GGA(.(N, XS), .(s(M), YS))
7.77/2.78	
7.77/2.78	R is empty.
7.77/2.78	Q is empty.
7.77/2.78	We have to consider all (P,Q,R)-chains.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(12) UsableRulesReductionPairsProof (EQUIVALENT)
7.77/2.78	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.
7.77/2.78	
7.77/2.78	The following dependency pairs can be deleted:
7.77/2.78	
7.77/2.78	   SUM_IN_GGA(.(0, XS), YS) -> SUM_IN_GGA(XS, YS)
7.77/2.78	   SUM_IN_GGA(.(s(N), XS), .(M, YS)) -> SUM_IN_GGA(.(N, XS), .(s(M), YS))
7.77/2.78	No rules are removed from R.
7.77/2.78	
7.77/2.78	Used ordering: POLO with Polynomial interpretation [POLO]:
7.77/2.78	
7.77/2.78	   POL(.(x_1, x_2)) = x_1 + x_2
7.77/2.78	   POL(0) = 0
7.77/2.78	   POL(SUM_IN_GGA(x_1, x_2)) = 2*x_1 + x_2
7.77/2.78	   POL(s(x_1)) = 2 + x_1
7.77/2.78	
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(13)
7.77/2.78	Obligation:
7.77/2.78	Q DP problem:
7.77/2.78	P is empty.
7.77/2.78	R is empty.
7.77/2.78	Q is empty.
7.77/2.78	We have to consider all (P,Q,R)-chains.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(14) PisEmptyProof (EQUIVALENT)
7.77/2.78	The TRS P is empty. Hence, there is no (P,Q,R) chain.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(15)
7.77/2.78	YES
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(16)
7.77/2.78	Obligation:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X)
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   weight_in_ga(.(N, .(M, XS)), X) -> U3_ga(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U3_ga(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> U4_ga(N, M, XS, X, weight_in_ga(YS, X))
7.77/2.78	   weight_in_ga(.(X, []), X) -> weight_out_ga(.(X, []), X)
7.77/2.78	   U4_ga(N, M, XS, X, weight_out_ga(YS, X)) -> weight_out_ga(.(N, .(M, XS)), X)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	weight_in_ga(x1, x2)  =  weight_in_ga(x1)
7.77/2.78	
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	U3_ga(x1, x2, x3, x4, x5)  =  U3_ga(x5)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	U4_ga(x1, x2, x3, x4, x5)  =  U4_ga(x5)
7.77/2.78	
7.77/2.78	weight_out_ga(x1, x2)  =  weight_out_ga(x2)
7.77/2.78	
7.77/2.78	WEIGHT_IN_GA(x1, x2)  =  WEIGHT_IN_GA(x1)
7.77/2.78	
7.77/2.78	U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x5)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(17) UsableRulesProof (EQUIVALENT)
7.77/2.78	For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(18)
7.77/2.78	Obligation:
7.77/2.78	Pi DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   U3_GA(N, M, XS, X, sum_out_gga(.(N, .(M, XS)), .(0, XS), YS)) -> WEIGHT_IN_GA(YS, X)
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS)), X) -> U3_GA(N, M, XS, X, sum_in_gga(.(N, .(M, XS)), .(0, XS), YS))
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS), ZS) -> U1_gga(N, XS, M, YS, ZS, sum_in_gga(.(N, XS), .(s(M), YS), ZS))
7.77/2.78	   sum_in_gga(.(0, XS), YS, ZS) -> U2_gga(XS, YS, ZS, sum_in_gga(XS, YS, ZS))
7.77/2.78	   U1_gga(N, XS, M, YS, ZS, sum_out_gga(.(N, XS), .(s(M), YS), ZS)) -> sum_out_gga(.(s(N), XS), .(M, YS), ZS)
7.77/2.78	   U2_gga(XS, YS, ZS, sum_out_gga(XS, YS, ZS)) -> sum_out_gga(.(0, XS), YS, ZS)
7.77/2.78	   sum_in_gga([], YS, YS) -> sum_out_gga([], YS, YS)
7.77/2.78	
7.77/2.78	The argument filtering Pi contains the following mapping:
7.77/2.78	.(x1, x2)  =  .(x1, x2)
7.77/2.78	
7.77/2.78	sum_in_gga(x1, x2, x3)  =  sum_in_gga(x1, x2)
7.77/2.78	
7.77/2.78	s(x1)  =  s(x1)
7.77/2.78	
7.77/2.78	U1_gga(x1, x2, x3, x4, x5, x6)  =  U1_gga(x6)
7.77/2.78	
7.77/2.78	0  =  0
7.77/2.78	
7.77/2.78	U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
7.77/2.78	
7.77/2.78	[]  =  []
7.77/2.78	
7.77/2.78	sum_out_gga(x1, x2, x3)  =  sum_out_gga(x3)
7.77/2.78	
7.77/2.78	WEIGHT_IN_GA(x1, x2)  =  WEIGHT_IN_GA(x1)
7.77/2.78	
7.77/2.78	U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x5)
7.77/2.78	
7.77/2.78	
7.77/2.78	We have to consider all (P,R,Pi)-chains
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(19) PiDPToQDPProof (SOUND)
7.77/2.78	Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(20)
7.77/2.78	Obligation:
7.77/2.78	Q DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   U3_GA(sum_out_gga(YS)) -> WEIGHT_IN_GA(YS)
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS))) -> U3_GA(sum_in_gga(.(N, .(M, XS)), .(0, XS)))
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS)) -> U1_gga(sum_in_gga(.(N, XS), .(s(M), YS)))
7.77/2.78	   sum_in_gga(.(0, XS), YS) -> U2_gga(sum_in_gga(XS, YS))
7.77/2.78	   U1_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS)
7.77/2.78	   U2_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS)
7.77/2.78	   sum_in_gga([], YS) -> sum_out_gga(YS)
7.77/2.78	
7.77/2.78	The set Q consists of the following terms:
7.77/2.78	
7.77/2.78	   sum_in_gga(x0, x1)
7.77/2.78	   U1_gga(x0)
7.77/2.78	   U2_gga(x0)
7.77/2.78	
7.77/2.78	We have to consider all (P,Q,R)-chains.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(21) UsableRulesReductionPairsProof (EQUIVALENT)
7.77/2.78	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.
7.77/2.78	
7.77/2.78	The following dependency pairs can be deleted:
7.77/2.78	
7.77/2.78	   WEIGHT_IN_GA(.(N, .(M, XS))) -> U3_GA(sum_in_gga(.(N, .(M, XS)), .(0, XS)))
7.77/2.78	The following rules are removed from R:
7.77/2.78	
7.77/2.78	   sum_in_gga([], YS) -> sum_out_gga(YS)
7.77/2.78	Used ordering: POLO with Polynomial interpretation [POLO]:
7.77/2.78	
7.77/2.78	   POL(.(x_1, x_2)) = x_1 + 2*x_2
7.77/2.78	   POL(0) = 0
7.77/2.78	   POL(U1_gga(x_1)) = x_1
7.77/2.78	   POL(U2_gga(x_1)) = x_1
7.77/2.78	   POL(U3_GA(x_1)) = x_1
7.77/2.78	   POL(WEIGHT_IN_GA(x_1)) = 1 + 2*x_1
7.77/2.78	   POL([]) = 2
7.77/2.78	   POL(s(x_1)) = x_1
7.77/2.78	   POL(sum_in_gga(x_1, x_2)) = x_1 + 2*x_2
7.77/2.78	   POL(sum_out_gga(x_1)) = 1 + 2*x_1
7.77/2.78	
7.77/2.78	
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(22)
7.77/2.78	Obligation:
7.77/2.78	Q DP problem:
7.77/2.78	The TRS P consists of the following rules:
7.77/2.78	
7.77/2.78	   U3_GA(sum_out_gga(YS)) -> WEIGHT_IN_GA(YS)
7.77/2.78	
7.77/2.78	The TRS R consists of the following rules:
7.77/2.78	
7.77/2.78	   sum_in_gga(.(s(N), XS), .(M, YS)) -> U1_gga(sum_in_gga(.(N, XS), .(s(M), YS)))
7.77/2.78	   sum_in_gga(.(0, XS), YS) -> U2_gga(sum_in_gga(XS, YS))
7.77/2.78	   U2_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS)
7.77/2.78	   U1_gga(sum_out_gga(ZS)) -> sum_out_gga(ZS)
7.77/2.78	
7.77/2.78	The set Q consists of the following terms:
7.77/2.78	
7.77/2.78	   sum_in_gga(x0, x1)
7.77/2.78	   U1_gga(x0)
7.77/2.78	   U2_gga(x0)
7.77/2.78	
7.77/2.78	We have to consider all (P,Q,R)-chains.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(23) DependencyGraphProof (EQUIVALENT)
7.77/2.78	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
7.77/2.78	----------------------------------------
7.77/2.78	
7.77/2.78	(24)
7.77/2.78	TRUE
7.90/2.85	EOF