8.49/3.03 YES 8.49/3.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 8.49/3.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.49/3.05 8.49/3.05 8.49/3.05 Left Termination of the query pattern 8.49/3.05 8.49/3.05 qs(g,a) 8.49/3.05 8.49/3.05 w.r.t. the given Prolog program could successfully be proven: 8.49/3.05 8.49/3.05 (0) Prolog 8.49/3.05 (1) PrologToPiTRSProof [SOUND, 18 ms] 8.49/3.05 (2) PiTRS 8.49/3.05 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.49/3.05 (4) PiDP 8.49/3.05 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.49/3.05 (6) AND 8.49/3.05 (7) PiDP 8.49/3.05 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.49/3.05 (9) PiDP 8.49/3.05 (10) PiDPToQDPProof [SOUND, 7 ms] 8.49/3.05 (11) QDP 8.49/3.05 (12) QDPSizeChangeProof [EQUIVALENT, 1 ms] 8.49/3.05 (13) YES 8.49/3.05 (14) PiDP 8.49/3.05 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.49/3.05 (16) PiDP 8.49/3.05 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.49/3.05 (18) QDP 8.49/3.05 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.49/3.05 (20) YES 8.49/3.05 (21) PiDP 8.49/3.05 (22) UsableRulesProof [EQUIVALENT, 0 ms] 8.49/3.05 (23) PiDP 8.49/3.05 (24) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.49/3.05 (25) QDP 8.49/3.05 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.49/3.05 (27) YES 8.49/3.05 (28) PiDP 8.49/3.05 (29) UsableRulesProof [EQUIVALENT, 0 ms] 8.49/3.05 (30) PiDP 8.49/3.05 (31) PiDPToQDPProof [SOUND, 0 ms] 8.49/3.05 (32) QDP 8.49/3.05 (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.49/3.05 (34) YES 8.49/3.05 (35) PiDP 8.49/3.05 (36) PiDPToQDPProof [SOUND, 0 ms] 8.49/3.05 (37) QDP 8.49/3.05 (38) QDPQMonotonicMRRProof [EQUIVALENT, 63 ms] 8.49/3.05 (39) QDP 8.49/3.05 (40) DependencyGraphProof [EQUIVALENT, 0 ms] 8.49/3.05 (41) TRUE 8.49/3.05 8.49/3.05 8.49/3.05 ---------------------------------------- 8.49/3.05 8.49/3.05 (0) 8.49/3.05 Obligation: 8.49/3.05 Clauses: 8.49/3.05 8.49/3.05 qs([], []). 8.49/3.05 qs(cons(X, L), S) :- ','(split(L, X, L1, L2), ','(qs(L1, S1), ','(qs(L2, S2), append(S1, cons(X, S2), S)))). 8.49/3.05 append([], L, L). 8.49/3.05 append(cons(X, L1), L2, cons(X, L3)) :- append(L1, L2, L3). 8.49/3.05 split([], X, [], []). 8.49/3.05 split(cons(X, L), Y, cons(X, L1), L2) :- ','(less(X, Y), split(L, Y, L1, L2)). 8.49/3.05 split(cons(X, L), Y, L1, cons(X, L2)) :- ','(geq(X, Y), split(L, Y, L1, L2)). 8.49/3.05 less(0, s(X)). 8.49/3.05 less(s(X), s(Y)) :- less(X, Y). 8.49/3.05 geq(X, X). 8.49/3.05 geq(s(X), 0). 8.49/3.05 geq(s(X), s(Y)) :- geq(X, Y). 8.49/3.05 8.49/3.05 8.49/3.05 Query: qs(g,a) 8.49/3.05 ---------------------------------------- 8.49/3.05 8.49/3.05 (1) PrologToPiTRSProof (SOUND) 8.49/3.05 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.49/3.05 8.49/3.05 qs_in_2: (b,f) 8.49/3.05 8.49/3.05 split_in_4: (b,b,f,f) 8.49/3.05 8.49/3.05 less_in_2: (b,b) 8.49/3.05 8.49/3.05 geq_in_2: (b,b) 8.49/3.05 8.49/3.05 append_in_3: (b,b,f) 8.49/3.05 8.49/3.05 Transforming Prolog into the following Term Rewriting System: 8.49/3.05 8.49/3.05 Pi-finite rewrite system: 8.49/3.05 The TRS R consists of the following rules: 8.49/3.05 8.49/3.05 qs_in_ga([], []) -> qs_out_ga([], []) 8.49/3.05 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.49/3.05 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.49/3.05 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.49/3.05 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.49/3.05 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.49/3.05 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.49/3.05 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.49/3.05 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.49/3.05 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.49/3.05 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.49/3.05 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.49/3.05 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.49/3.05 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.49/3.05 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.49/3.05 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.49/3.05 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.49/3.05 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.49/3.05 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.49/3.05 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.49/3.05 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.49/3.05 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.49/3.05 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.49/3.05 8.49/3.05 The argument filtering Pi contains the following mapping: 8.49/3.05 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.49/3.05 8.49/3.05 [] = [] 8.49/3.05 8.49/3.05 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.49/3.05 8.49/3.05 cons(x1, x2) = cons(x1, x2) 8.49/3.05 8.49/3.05 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.49/3.05 8.49/3.05 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.49/3.05 8.49/3.05 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.49/3.05 8.49/3.05 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.49/3.05 8.49/3.05 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.49/3.05 8.49/3.05 0 = 0 8.49/3.05 8.49/3.05 s(x1) = s(x1) 8.49/3.05 8.49/3.05 less_out_gg(x1, x2) = less_out_gg 8.49/3.05 8.49/3.05 U10_gg(x1, x2, x3) = U10_gg(x3) 8.49/3.05 8.49/3.05 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.49/3.05 8.49/3.05 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.49/3.05 8.49/3.05 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.49/3.05 8.49/3.05 geq_out_gg(x1, x2) = geq_out_gg 8.49/3.05 8.49/3.05 U11_gg(x1, x2, x3) = U11_gg(x3) 8.49/3.05 8.49/3.05 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.49/3.05 8.49/3.05 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.49/3.05 8.49/3.05 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.49/3.05 8.49/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.49/3.05 8.49/3.05 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.49/3.05 8.49/3.05 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.49/3.05 8.49/3.05 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.49/3.05 8.49/3.05 8.49/3.05 8.49/3.05 8.49/3.05 8.49/3.05 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.49/3.05 8.49/3.05 8.49/3.05 8.49/3.05 ---------------------------------------- 8.49/3.05 8.49/3.05 (2) 8.49/3.05 Obligation: 8.49/3.05 Pi-finite rewrite system: 8.49/3.05 The TRS R consists of the following rules: 8.49/3.05 8.49/3.05 qs_in_ga([], []) -> qs_out_ga([], []) 8.49/3.05 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.49/3.05 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.49/3.05 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.49/3.05 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.49/3.05 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.49/3.05 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.49/3.05 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.49/3.05 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.49/3.05 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.49/3.05 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.49/3.05 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.49/3.05 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.49/3.05 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.49/3.05 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.49/3.05 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.49/3.05 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.49/3.05 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.49/3.05 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.49/3.05 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.49/3.05 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.49/3.05 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.49/3.05 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.49/3.05 8.49/3.05 The argument filtering Pi contains the following mapping: 8.49/3.05 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.49/3.05 8.49/3.05 [] = [] 8.49/3.05 8.49/3.05 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.49/3.05 8.49/3.05 cons(x1, x2) = cons(x1, x2) 8.49/3.05 8.49/3.05 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.49/3.05 8.49/3.05 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.49/3.05 8.49/3.05 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.49/3.05 8.49/3.05 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.49/3.05 8.49/3.05 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.49/3.05 8.49/3.05 0 = 0 8.49/3.05 8.49/3.05 s(x1) = s(x1) 8.49/3.05 8.49/3.05 less_out_gg(x1, x2) = less_out_gg 8.49/3.05 8.49/3.05 U10_gg(x1, x2, x3) = U10_gg(x3) 8.49/3.05 8.49/3.05 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.49/3.05 8.49/3.05 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.49/3.05 8.49/3.05 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.49/3.05 8.49/3.05 geq_out_gg(x1, x2) = geq_out_gg 8.49/3.05 8.49/3.05 U11_gg(x1, x2, x3) = U11_gg(x3) 8.49/3.05 8.49/3.05 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.49/3.05 8.49/3.05 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.49/3.05 8.49/3.05 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.05 8.59/3.05 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.05 8.59/3.05 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.05 8.59/3.05 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.05 8.59/3.05 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.05 8.59/3.05 8.59/3.05 8.59/3.05 ---------------------------------------- 8.59/3.05 8.59/3.05 (3) DependencyPairsProof (EQUIVALENT) 8.59/3.05 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.59/3.05 Pi DP problem: 8.59/3.05 The TRS P consists of the following rules: 8.59/3.05 8.59/3.05 QS_IN_GA(cons(X, L), S) -> U1_GA(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.05 QS_IN_GA(cons(X, L), S) -> SPLIT_IN_GGAA(L, X, L1, L2) 8.59/3.05 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> U6_GGAA(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.05 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> LESS_IN_GG(X, Y) 8.59/3.05 LESS_IN_GG(s(X), s(Y)) -> U10_GG(X, Y, less_in_gg(X, Y)) 8.59/3.05 LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.05 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_GGAA(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.05 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.05 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> U8_GGAA(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.05 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> GEQ_IN_GG(X, Y) 8.59/3.05 GEQ_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, geq_in_gg(X, Y)) 8.59/3.05 GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.05 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_GGAA(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.05 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.05 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_GA(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.05 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> QS_IN_GA(L1, S1) 8.59/3.05 U2_GA(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_GA(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.05 U2_GA(X, L, S, L2, qs_out_ga(L1, S1)) -> QS_IN_GA(L2, S2) 8.59/3.05 U3_GA(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_GA(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.05 U3_GA(X, L, S, S1, qs_out_ga(L2, S2)) -> APPEND_IN_GGA(S1, cons(X, S2), S) 8.59/3.05 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> U5_GGA(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.05 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> APPEND_IN_GGA(L1, L2, L3) 8.59/3.05 8.59/3.05 The TRS R consists of the following rules: 8.59/3.05 8.59/3.05 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.05 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.05 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.05 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.05 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.05 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.05 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.05 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.05 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.05 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.05 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.05 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.05 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.05 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.05 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.05 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.05 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.05 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.05 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.05 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.05 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.05 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.05 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.05 8.59/3.05 The argument filtering Pi contains the following mapping: 8.59/3.05 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.05 8.59/3.05 [] = [] 8.59/3.05 8.59/3.05 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.05 8.59/3.05 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 QS_IN_GA(x1, x2) = QS_IN_GA(x1) 8.59/3.06 8.59/3.06 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 8.59/3.06 8.59/3.06 SPLIT_IN_GGAA(x1, x2, x3, x4) = SPLIT_IN_GGAA(x1, x2) 8.59/3.06 8.59/3.06 U6_GGAA(x1, x2, x3, x4, x5, x6) = U6_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 U10_GG(x1, x2, x3) = U10_GG(x3) 8.59/3.06 8.59/3.06 U7_GGAA(x1, x2, x3, x4, x5, x6) = U7_GGAA(x1, x6) 8.59/3.06 8.59/3.06 U8_GGAA(x1, x2, x3, x4, x5, x6) = U8_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 GEQ_IN_GG(x1, x2) = GEQ_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 U11_GG(x1, x2, x3) = U11_GG(x3) 8.59/3.06 8.59/3.06 U9_GGAA(x1, x2, x3, x4, x5, x6) = U9_GGAA(x1, x6) 8.59/3.06 8.59/3.06 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_GA(x1, x2, x3, x4) = U4_GA(x4) 8.59/3.06 8.59/3.06 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 8.59/3.06 8.59/3.06 U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x5) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (4) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 QS_IN_GA(cons(X, L), S) -> U1_GA(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 QS_IN_GA(cons(X, L), S) -> SPLIT_IN_GGAA(L, X, L1, L2) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> U6_GGAA(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> LESS_IN_GG(X, Y) 8.59/3.06 LESS_IN_GG(s(X), s(Y)) -> U10_GG(X, Y, less_in_gg(X, Y)) 8.59/3.06 LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.06 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_GGAA(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> U8_GGAA(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> GEQ_IN_GG(X, Y) 8.59/3.06 GEQ_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, geq_in_gg(X, Y)) 8.59/3.06 GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.06 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_GGAA(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_GA(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> QS_IN_GA(L1, S1) 8.59/3.06 U2_GA(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_GA(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U2_GA(X, L, S, L2, qs_out_ga(L1, S1)) -> QS_IN_GA(L2, S2) 8.59/3.06 U3_GA(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_GA(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 U3_GA(X, L, S, S1, qs_out_ga(L2, S2)) -> APPEND_IN_GGA(S1, cons(X, S2), S) 8.59/3.06 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> U5_GGA(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> APPEND_IN_GGA(L1, L2, L3) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 QS_IN_GA(x1, x2) = QS_IN_GA(x1) 8.59/3.06 8.59/3.06 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 8.59/3.06 8.59/3.06 SPLIT_IN_GGAA(x1, x2, x3, x4) = SPLIT_IN_GGAA(x1, x2) 8.59/3.06 8.59/3.06 U6_GGAA(x1, x2, x3, x4, x5, x6) = U6_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 U10_GG(x1, x2, x3) = U10_GG(x3) 8.59/3.06 8.59/3.06 U7_GGAA(x1, x2, x3, x4, x5, x6) = U7_GGAA(x1, x6) 8.59/3.06 8.59/3.06 U8_GGAA(x1, x2, x3, x4, x5, x6) = U8_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 GEQ_IN_GG(x1, x2) = GEQ_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 U11_GG(x1, x2, x3) = U11_GG(x3) 8.59/3.06 8.59/3.06 U9_GGAA(x1, x2, x3, x4, x5, x6) = U9_GGAA(x1, x6) 8.59/3.06 8.59/3.06 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_GA(x1, x2, x3, x4) = U4_GA(x4) 8.59/3.06 8.59/3.06 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 8.59/3.06 8.59/3.06 U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x5) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (5) DependencyGraphProof (EQUIVALENT) 8.59/3.06 The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 11 less nodes. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (6) 8.59/3.06 Complex Obligation (AND) 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (7) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> APPEND_IN_GGA(L1, L2, L3) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (8) UsableRulesProof (EQUIVALENT) 8.59/3.06 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (9) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 APPEND_IN_GGA(cons(X, L1), L2, cons(X, L3)) -> APPEND_IN_GGA(L1, L2, L3) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (10) PiDPToQDPProof (SOUND) 8.59/3.06 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (11) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 APPEND_IN_GGA(cons(X, L1), L2) -> APPEND_IN_GGA(L1, L2) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 Q is empty. 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (12) QDPSizeChangeProof (EQUIVALENT) 8.59/3.06 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. 8.59/3.06 8.59/3.06 From the DPs we obtained the following set of size-change graphs: 8.59/3.06 *APPEND_IN_GGA(cons(X, L1), L2) -> APPEND_IN_GGA(L1, L2) 8.59/3.06 The graph contains the following edges 1 > 1, 2 >= 2 8.59/3.06 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (13) 8.59/3.06 YES 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (14) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 GEQ_IN_GG(x1, x2) = GEQ_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (15) UsableRulesProof (EQUIVALENT) 8.59/3.06 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (16) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 Pi is empty. 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (17) PiDPToQDPProof (EQUIVALENT) 8.59/3.06 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (18) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 Q is empty. 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (19) QDPSizeChangeProof (EQUIVALENT) 8.59/3.06 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. 8.59/3.06 8.59/3.06 From the DPs we obtained the following set of size-change graphs: 8.59/3.06 *GEQ_IN_GG(s(X), s(Y)) -> GEQ_IN_GG(X, Y) 8.59/3.06 The graph contains the following edges 1 > 1, 2 > 2 8.59/3.06 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (20) 8.59/3.06 YES 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (21) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (22) UsableRulesProof (EQUIVALENT) 8.59/3.06 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (23) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 Pi is empty. 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (24) PiDPToQDPProof (EQUIVALENT) 8.59/3.06 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (25) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.06 8.59/3.06 R is empty. 8.59/3.06 Q is empty. 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (26) QDPSizeChangeProof (EQUIVALENT) 8.59/3.06 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. 8.59/3.06 8.59/3.06 From the DPs we obtained the following set of size-change graphs: 8.59/3.06 *LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) 8.59/3.06 The graph contains the following edges 1 > 1, 2 > 2 8.59/3.06 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (27) 8.59/3.06 YES 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (28) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> U6_GGAA(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> U8_GGAA(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 SPLIT_IN_GGAA(x1, x2, x3, x4) = SPLIT_IN_GGAA(x1, x2) 8.59/3.06 8.59/3.06 U6_GGAA(x1, x2, x3, x4, x5, x6) = U6_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 U8_GGAA(x1, x2, x3, x4, x5, x6) = U8_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (29) UsableRulesProof (EQUIVALENT) 8.59/3.06 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (30) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U6_GGAA(X, L, Y, L1, L2, less_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, cons(X, L1), L2) -> U6_GGAA(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y, L1, cons(X, L2)) -> U8_GGAA(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 U8_GGAA(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> SPLIT_IN_GGAA(L, Y, L1, L2) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 SPLIT_IN_GGAA(x1, x2, x3, x4) = SPLIT_IN_GGAA(x1, x2) 8.59/3.06 8.59/3.06 U6_GGAA(x1, x2, x3, x4, x5, x6) = U6_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 U8_GGAA(x1, x2, x3, x4, x5, x6) = U8_GGAA(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (31) PiDPToQDPProof (SOUND) 8.59/3.06 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (32) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U6_GGAA(X, L, Y, less_out_gg) -> SPLIT_IN_GGAA(L, Y) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y) -> U6_GGAA(X, L, Y, less_in_gg(X, Y)) 8.59/3.06 SPLIT_IN_GGAA(cons(X, L), Y) -> U8_GGAA(X, L, Y, geq_in_gg(X, Y)) 8.59/3.06 U8_GGAA(X, L, Y, geq_out_gg) -> SPLIT_IN_GGAA(L, Y) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(less_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(geq_in_gg(X, Y)) 8.59/3.06 U10_gg(less_out_gg) -> less_out_gg 8.59/3.06 U11_gg(geq_out_gg) -> geq_out_gg 8.59/3.06 8.59/3.06 The set Q consists of the following terms: 8.59/3.06 8.59/3.06 less_in_gg(x0, x1) 8.59/3.06 geq_in_gg(x0, x1) 8.59/3.06 U10_gg(x0) 8.59/3.06 U11_gg(x0) 8.59/3.06 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (33) QDPSizeChangeProof (EQUIVALENT) 8.59/3.06 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. 8.59/3.06 8.59/3.06 From the DPs we obtained the following set of size-change graphs: 8.59/3.06 *SPLIT_IN_GGAA(cons(X, L), Y) -> U6_GGAA(X, L, Y, less_in_gg(X, Y)) 8.59/3.06 The graph contains the following edges 1 > 1, 1 > 2, 2 >= 3 8.59/3.06 8.59/3.06 8.59/3.06 *SPLIT_IN_GGAA(cons(X, L), Y) -> U8_GGAA(X, L, Y, geq_in_gg(X, Y)) 8.59/3.06 The graph contains the following edges 1 > 1, 1 > 2, 2 >= 3 8.59/3.06 8.59/3.06 8.59/3.06 *U6_GGAA(X, L, Y, less_out_gg) -> SPLIT_IN_GGAA(L, Y) 8.59/3.06 The graph contains the following edges 2 >= 1, 3 >= 2 8.59/3.06 8.59/3.06 8.59/3.06 *U8_GGAA(X, L, Y, geq_out_gg) -> SPLIT_IN_GGAA(L, Y) 8.59/3.06 The graph contains the following edges 2 >= 1, 3 >= 2 8.59/3.06 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (34) 8.59/3.06 YES 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (35) 8.59/3.06 Obligation: 8.59/3.06 Pi DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_GA(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_GA(X, L, S, L2, qs_out_ga(L1, S1)) -> QS_IN_GA(L2, S2) 8.59/3.06 QS_IN_GA(cons(X, L), S) -> U1_GA(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 U1_GA(X, L, S, split_out_ggaa(L, X, L1, L2)) -> QS_IN_GA(L1, S1) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([], []) -> qs_out_ga([], []) 8.59/3.06 qs_in_ga(cons(X, L), S) -> U1_ga(X, L, S, split_in_ggaa(L, X, L1, L2)) 8.59/3.06 split_in_ggaa([], X, [], []) -> split_out_ggaa([], X, [], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y, cons(X, L1), L2) -> U6_ggaa(X, L, Y, L1, L2, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg(0, s(X)) 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(X, Y, less_in_gg(X, Y)) 8.59/3.06 U10_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) 8.59/3.06 U6_ggaa(X, L, Y, L1, L2, less_out_gg(X, Y)) -> U7_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 split_in_ggaa(cons(X, L), Y, L1, cons(X, L2)) -> U8_ggaa(X, L, Y, L1, L2, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg(X, X) 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg(s(X), 0) 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(X, Y, geq_in_gg(X, Y)) 8.59/3.06 U11_gg(X, Y, geq_out_gg(X, Y)) -> geq_out_gg(s(X), s(Y)) 8.59/3.06 U8_ggaa(X, L, Y, L1, L2, geq_out_gg(X, Y)) -> U9_ggaa(X, L, Y, L1, L2, split_in_ggaa(L, Y, L1, L2)) 8.59/3.06 U9_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, L, Y, L1, L2, split_out_ggaa(L, Y, L1, L2)) -> split_out_ggaa(cons(X, L), Y, cons(X, L1), L2) 8.59/3.06 U1_ga(X, L, S, split_out_ggaa(L, X, L1, L2)) -> U2_ga(X, L, S, L2, qs_in_ga(L1, S1)) 8.59/3.06 U2_ga(X, L, S, L2, qs_out_ga(L1, S1)) -> U3_ga(X, L, S, S1, qs_in_ga(L2, S2)) 8.59/3.06 U3_ga(X, L, S, S1, qs_out_ga(L2, S2)) -> U4_ga(X, L, S, append_in_gga(S1, cons(X, S2), S)) 8.59/3.06 append_in_gga([], L, L) -> append_out_gga([], L, L) 8.59/3.06 append_in_gga(cons(X, L1), L2, cons(X, L3)) -> U5_gga(X, L1, L2, L3, append_in_gga(L1, L2, L3)) 8.59/3.06 U5_gga(X, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(cons(X, L1), L2, cons(X, L3)) 8.59/3.06 U4_ga(X, L, S, append_out_gga(S1, cons(X, S2), S)) -> qs_out_ga(cons(X, L), S) 8.59/3.06 8.59/3.06 The argument filtering Pi contains the following mapping: 8.59/3.06 qs_in_ga(x1, x2) = qs_in_ga(x1) 8.59/3.06 8.59/3.06 [] = [] 8.59/3.06 8.59/3.06 qs_out_ga(x1, x2) = qs_out_ga(x2) 8.59/3.06 8.59/3.06 cons(x1, x2) = cons(x1, x2) 8.59/3.06 8.59/3.06 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) 8.59/3.06 8.59/3.06 split_in_ggaa(x1, x2, x3, x4) = split_in_ggaa(x1, x2) 8.59/3.06 8.59/3.06 split_out_ggaa(x1, x2, x3, x4) = split_out_ggaa(x3, x4) 8.59/3.06 8.59/3.06 U6_ggaa(x1, x2, x3, x4, x5, x6) = U6_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 less_in_gg(x1, x2) = less_in_gg(x1, x2) 8.59/3.06 8.59/3.06 0 = 0 8.59/3.06 8.59/3.06 s(x1) = s(x1) 8.59/3.06 8.59/3.06 less_out_gg(x1, x2) = less_out_gg 8.59/3.06 8.59/3.06 U10_gg(x1, x2, x3) = U10_gg(x3) 8.59/3.06 8.59/3.06 U7_ggaa(x1, x2, x3, x4, x5, x6) = U7_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U8_ggaa(x1, x2, x3, x4, x5, x6) = U8_ggaa(x1, x2, x3, x6) 8.59/3.06 8.59/3.06 geq_in_gg(x1, x2) = geq_in_gg(x1, x2) 8.59/3.06 8.59/3.06 geq_out_gg(x1, x2) = geq_out_gg 8.59/3.06 8.59/3.06 U11_gg(x1, x2, x3) = U11_gg(x3) 8.59/3.06 8.59/3.06 U9_ggaa(x1, x2, x3, x4, x5, x6) = U9_ggaa(x1, x6) 8.59/3.06 8.59/3.06 U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x1, x4, x5) 8.59/3.06 8.59/3.06 U4_ga(x1, x2, x3, x4) = U4_ga(x4) 8.59/3.06 8.59/3.06 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 8.59/3.06 8.59/3.06 append_out_gga(x1, x2, x3) = append_out_gga(x3) 8.59/3.06 8.59/3.06 U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x5) 8.59/3.06 8.59/3.06 QS_IN_GA(x1, x2) = QS_IN_GA(x1) 8.59/3.06 8.59/3.06 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) 8.59/3.06 8.59/3.06 U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x4, x5) 8.59/3.06 8.59/3.06 8.59/3.06 We have to consider all (P,R,Pi)-chains 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (36) PiDPToQDPProof (SOUND) 8.59/3.06 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (37) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U1_GA(X, split_out_ggaa(L1, L2)) -> U2_GA(X, L2, qs_in_ga(L1)) 8.59/3.06 U2_GA(X, L2, qs_out_ga(S1)) -> QS_IN_GA(L2) 8.59/3.06 QS_IN_GA(cons(X, L)) -> U1_GA(X, split_in_ggaa(L, X)) 8.59/3.06 U1_GA(X, split_out_ggaa(L1, L2)) -> QS_IN_GA(L1) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([]) -> qs_out_ga([]) 8.59/3.06 qs_in_ga(cons(X, L)) -> U1_ga(X, split_in_ggaa(L, X)) 8.59/3.06 split_in_ggaa([], X) -> split_out_ggaa([], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y) -> U6_ggaa(X, L, Y, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(less_in_gg(X, Y)) 8.59/3.06 U10_gg(less_out_gg) -> less_out_gg 8.59/3.06 U6_ggaa(X, L, Y, less_out_gg) -> U7_ggaa(X, split_in_ggaa(L, Y)) 8.59/3.06 split_in_ggaa(cons(X, L), Y) -> U8_ggaa(X, L, Y, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(geq_in_gg(X, Y)) 8.59/3.06 U11_gg(geq_out_gg) -> geq_out_gg 8.59/3.06 U8_ggaa(X, L, Y, geq_out_gg) -> U9_ggaa(X, split_in_ggaa(L, Y)) 8.59/3.06 U9_ggaa(X, split_out_ggaa(L1, L2)) -> split_out_ggaa(L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, split_out_ggaa(L1, L2)) -> split_out_ggaa(cons(X, L1), L2) 8.59/3.06 U1_ga(X, split_out_ggaa(L1, L2)) -> U2_ga(X, L2, qs_in_ga(L1)) 8.59/3.06 U2_ga(X, L2, qs_out_ga(S1)) -> U3_ga(X, S1, qs_in_ga(L2)) 8.59/3.06 U3_ga(X, S1, qs_out_ga(S2)) -> U4_ga(append_in_gga(S1, cons(X, S2))) 8.59/3.06 append_in_gga([], L) -> append_out_gga(L) 8.59/3.06 append_in_gga(cons(X, L1), L2) -> U5_gga(X, append_in_gga(L1, L2)) 8.59/3.06 U5_gga(X, append_out_gga(L3)) -> append_out_gga(cons(X, L3)) 8.59/3.06 U4_ga(append_out_gga(S)) -> qs_out_ga(S) 8.59/3.06 8.59/3.06 The set Q consists of the following terms: 8.59/3.06 8.59/3.06 qs_in_ga(x0) 8.59/3.06 split_in_ggaa(x0, x1) 8.59/3.06 less_in_gg(x0, x1) 8.59/3.06 U10_gg(x0) 8.59/3.06 U6_ggaa(x0, x1, x2, x3) 8.59/3.06 geq_in_gg(x0, x1) 8.59/3.06 U11_gg(x0) 8.59/3.06 U8_ggaa(x0, x1, x2, x3) 8.59/3.06 U9_ggaa(x0, x1) 8.59/3.06 U7_ggaa(x0, x1) 8.59/3.06 U1_ga(x0, x1) 8.59/3.06 U2_ga(x0, x1, x2) 8.59/3.06 U3_ga(x0, x1, x2) 8.59/3.06 append_in_gga(x0, x1) 8.59/3.06 U5_gga(x0, x1) 8.59/3.06 U4_ga(x0) 8.59/3.06 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (38) QDPQMonotonicMRRProof (EQUIVALENT) 8.59/3.06 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 8.59/3.06 8.59/3.06 Strictly oriented dependency pairs: 8.59/3.06 8.59/3.06 U1_GA(X, split_out_ggaa(L1, L2)) -> U2_GA(X, L2, qs_in_ga(L1)) 8.59/3.06 QS_IN_GA(cons(X, L)) -> U1_GA(X, split_in_ggaa(L, X)) 8.59/3.06 U1_GA(X, split_out_ggaa(L1, L2)) -> QS_IN_GA(L1) 8.59/3.06 8.59/3.06 8.59/3.06 Used ordering: Polynomial interpretation [POLO]: 8.59/3.06 8.59/3.06 POL(0) = 0 8.59/3.06 POL(QS_IN_GA(x_1)) = x_1 8.59/3.06 POL(U10_gg(x_1)) = 0 8.59/3.06 POL(U11_gg(x_1)) = 0 8.59/3.06 POL(U1_GA(x_1, x_2)) = 1 + 2*x_2 8.59/3.06 POL(U1_ga(x_1, x_2)) = 0 8.59/3.06 POL(U2_GA(x_1, x_2, x_3)) = 2*x_2 8.59/3.06 POL(U2_ga(x_1, x_2, x_3)) = 0 8.59/3.06 POL(U3_ga(x_1, x_2, x_3)) = 0 8.59/3.06 POL(U4_ga(x_1)) = 0 8.59/3.06 POL(U5_gga(x_1, x_2)) = 0 8.59/3.06 POL(U6_ggaa(x_1, x_2, x_3, x_4)) = 2 + 2*x_2 8.59/3.06 POL(U7_ggaa(x_1, x_2)) = 2 + 2*x_2 8.59/3.06 POL(U8_ggaa(x_1, x_2, x_3, x_4)) = 2 + 2*x_2 8.59/3.06 POL(U9_ggaa(x_1, x_2)) = 2 + 2*x_2 8.59/3.06 POL([]) = 0 8.59/3.06 POL(append_in_gga(x_1, x_2)) = 2*x_1 8.59/3.06 POL(append_out_gga(x_1)) = 0 8.59/3.06 POL(cons(x_1, x_2)) = 2 + 2*x_2 8.59/3.06 POL(geq_in_gg(x_1, x_2)) = 2*x_1 8.59/3.06 POL(geq_out_gg) = 0 8.59/3.06 POL(less_in_gg(x_1, x_2)) = 0 8.59/3.06 POL(less_out_gg) = 0 8.59/3.06 POL(qs_in_ga(x_1)) = 0 8.59/3.06 POL(qs_out_ga(x_1)) = 0 8.59/3.06 POL(s(x_1)) = 2*x_1 8.59/3.06 POL(split_in_ggaa(x_1, x_2)) = x_1 8.59/3.06 POL(split_out_ggaa(x_1, x_2)) = x_1 + x_2 8.59/3.06 8.59/3.06 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (39) 8.59/3.06 Obligation: 8.59/3.06 Q DP problem: 8.59/3.06 The TRS P consists of the following rules: 8.59/3.06 8.59/3.06 U2_GA(X, L2, qs_out_ga(S1)) -> QS_IN_GA(L2) 8.59/3.06 8.59/3.06 The TRS R consists of the following rules: 8.59/3.06 8.59/3.06 qs_in_ga([]) -> qs_out_ga([]) 8.59/3.06 qs_in_ga(cons(X, L)) -> U1_ga(X, split_in_ggaa(L, X)) 8.59/3.06 split_in_ggaa([], X) -> split_out_ggaa([], []) 8.59/3.06 split_in_ggaa(cons(X, L), Y) -> U6_ggaa(X, L, Y, less_in_gg(X, Y)) 8.59/3.06 less_in_gg(0, s(X)) -> less_out_gg 8.59/3.06 less_in_gg(s(X), s(Y)) -> U10_gg(less_in_gg(X, Y)) 8.59/3.06 U10_gg(less_out_gg) -> less_out_gg 8.59/3.06 U6_ggaa(X, L, Y, less_out_gg) -> U7_ggaa(X, split_in_ggaa(L, Y)) 8.59/3.06 split_in_ggaa(cons(X, L), Y) -> U8_ggaa(X, L, Y, geq_in_gg(X, Y)) 8.59/3.06 geq_in_gg(X, X) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), 0) -> geq_out_gg 8.59/3.06 geq_in_gg(s(X), s(Y)) -> U11_gg(geq_in_gg(X, Y)) 8.59/3.06 U11_gg(geq_out_gg) -> geq_out_gg 8.59/3.06 U8_ggaa(X, L, Y, geq_out_gg) -> U9_ggaa(X, split_in_ggaa(L, Y)) 8.59/3.06 U9_ggaa(X, split_out_ggaa(L1, L2)) -> split_out_ggaa(L1, cons(X, L2)) 8.59/3.06 U7_ggaa(X, split_out_ggaa(L1, L2)) -> split_out_ggaa(cons(X, L1), L2) 8.59/3.06 U1_ga(X, split_out_ggaa(L1, L2)) -> U2_ga(X, L2, qs_in_ga(L1)) 8.59/3.06 U2_ga(X, L2, qs_out_ga(S1)) -> U3_ga(X, S1, qs_in_ga(L2)) 8.59/3.06 U3_ga(X, S1, qs_out_ga(S2)) -> U4_ga(append_in_gga(S1, cons(X, S2))) 8.59/3.06 append_in_gga([], L) -> append_out_gga(L) 8.59/3.06 append_in_gga(cons(X, L1), L2) -> U5_gga(X, append_in_gga(L1, L2)) 8.59/3.06 U5_gga(X, append_out_gga(L3)) -> append_out_gga(cons(X, L3)) 8.59/3.06 U4_ga(append_out_gga(S)) -> qs_out_ga(S) 8.59/3.06 8.59/3.06 The set Q consists of the following terms: 8.59/3.06 8.59/3.06 qs_in_ga(x0) 8.59/3.06 split_in_ggaa(x0, x1) 8.59/3.06 less_in_gg(x0, x1) 8.59/3.06 U10_gg(x0) 8.59/3.06 U6_ggaa(x0, x1, x2, x3) 8.59/3.06 geq_in_gg(x0, x1) 8.59/3.06 U11_gg(x0) 8.59/3.06 U8_ggaa(x0, x1, x2, x3) 8.59/3.06 U9_ggaa(x0, x1) 8.59/3.06 U7_ggaa(x0, x1) 8.59/3.06 U1_ga(x0, x1) 8.59/3.06 U2_ga(x0, x1, x2) 8.59/3.06 U3_ga(x0, x1, x2) 8.59/3.06 append_in_gga(x0, x1) 8.59/3.06 U5_gga(x0, x1) 8.59/3.06 U4_ga(x0) 8.59/3.06 8.59/3.06 We have to consider all (P,Q,R)-chains. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (40) DependencyGraphProof (EQUIVALENT) 8.59/3.06 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 8.59/3.06 ---------------------------------------- 8.59/3.06 8.59/3.06 (41) 8.59/3.06 TRUE 8.59/3.10 EOF