4.41/1.96 YES 4.41/1.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.41/1.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.41/1.97 4.41/1.97 4.41/1.97 Left Termination of the query pattern 4.41/1.97 4.41/1.97 goal(g,a,a) 4.41/1.97 4.41/1.97 w.r.t. the given Prolog program could successfully be proven: 4.41/1.97 4.41/1.97 (0) Prolog 4.41/1.97 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.41/1.97 (2) PiTRS 4.41/1.97 (3) DependencyPairsProof [EQUIVALENT, 25 ms] 4.41/1.97 (4) PiDP 4.41/1.97 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.41/1.97 (6) AND 4.41/1.97 (7) PiDP 4.41/1.97 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.41/1.97 (9) PiDP 4.41/1.97 (10) PiDPToQDPProof [SOUND, 0 ms] 4.41/1.97 (11) QDP 4.41/1.97 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.41/1.97 (13) YES 4.41/1.97 (14) PiDP 4.41/1.97 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.41/1.97 (16) PiDP 4.41/1.97 (17) PiDPToQDPProof [SOUND, 0 ms] 4.41/1.97 (18) QDP 4.41/1.97 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.41/1.97 (20) YES 4.41/1.97 (21) PiDP 4.41/1.97 (22) UsableRulesProof [EQUIVALENT, 0 ms] 4.41/1.97 (23) PiDP 4.41/1.97 (24) PiDPToQDPProof [SOUND, 0 ms] 4.41/1.97 (25) QDP 4.41/1.97 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.41/1.97 (27) YES 4.41/1.97 4.41/1.97 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (0) 4.41/1.97 Obligation: 4.41/1.97 Clauses: 4.41/1.97 4.41/1.97 goal(A, B, C) :- ','(s2l(A, D), applast(D, B, C)). 4.41/1.97 applast(L, X, Last) :- ','(append(L, .(X, []), LX), last(Last, LX)). 4.41/1.97 last(X, .(X, [])). 4.41/1.97 last(X, .(H, T)) :- last(X, T). 4.41/1.97 append([], L, L). 4.41/1.97 append(.(H, L1), L2, .(H, L3)) :- append(L1, L2, L3). 4.41/1.97 s2l(s(X), .(Y, Xs)) :- s2l(X, Xs). 4.41/1.97 s2l(0, []). 4.41/1.97 4.41/1.97 4.41/1.97 Query: goal(g,a,a) 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (1) PrologToPiTRSProof (SOUND) 4.41/1.97 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.41/1.97 4.41/1.97 goal_in_3: (b,f,f) 4.41/1.97 4.41/1.97 s2l_in_2: (b,f) 4.41/1.97 4.41/1.97 applast_in_3: (b,f,f) 4.41/1.97 4.41/1.97 append_in_3: (b,b,f) 4.41/1.97 4.41/1.97 last_in_2: (f,b) 4.41/1.97 4.41/1.97 Transforming Prolog into the following Term Rewriting System: 4.41/1.97 4.41/1.97 Pi-finite rewrite system: 4.41/1.97 The TRS R consists of the following rules: 4.41/1.97 4.41/1.97 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.97 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.97 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.97 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.97 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.97 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.97 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.97 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.97 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.97 4.41/1.97 The argument filtering Pi contains the following mapping: 4.41/1.97 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.97 4.41/1.97 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.97 4.41/1.97 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.97 4.41/1.97 s(x1) = s(x1) 4.41/1.97 4.41/1.97 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.97 4.41/1.97 0 = 0 4.41/1.97 4.41/1.97 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.97 4.41/1.97 .(x1, x2) = .(x2) 4.41/1.97 4.41/1.97 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.97 4.41/1.97 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.97 4.41/1.97 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.97 4.41/1.97 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.97 4.41/1.97 [] = [] 4.41/1.97 4.41/1.97 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.97 4.41/1.97 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.97 4.41/1.97 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.97 4.41/1.97 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.97 4.41/1.97 last_out_ag(x1, x2) = last_out_ag 4.41/1.97 4.41/1.97 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.97 4.41/1.97 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.97 4.41/1.97 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.97 4.41/1.97 4.41/1.97 4.41/1.97 4.41/1.97 4.41/1.97 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.41/1.97 4.41/1.97 4.41/1.97 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (2) 4.41/1.97 Obligation: 4.41/1.97 Pi-finite rewrite system: 4.41/1.97 The TRS R consists of the following rules: 4.41/1.97 4.41/1.97 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.97 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.97 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.97 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.97 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.97 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.97 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.97 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.97 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.97 4.41/1.97 The argument filtering Pi contains the following mapping: 4.41/1.97 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.97 4.41/1.97 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.97 4.41/1.97 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.97 4.41/1.97 s(x1) = s(x1) 4.41/1.97 4.41/1.97 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.97 4.41/1.97 0 = 0 4.41/1.97 4.41/1.97 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.97 4.41/1.97 .(x1, x2) = .(x2) 4.41/1.97 4.41/1.97 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.97 4.41/1.97 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.97 4.41/1.97 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.97 4.41/1.97 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.97 4.41/1.97 [] = [] 4.41/1.97 4.41/1.97 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.97 4.41/1.97 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.97 4.41/1.97 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.97 4.41/1.97 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.97 4.41/1.97 last_out_ag(x1, x2) = last_out_ag 4.41/1.97 4.41/1.97 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.97 4.41/1.97 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.97 4.41/1.97 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.97 4.41/1.97 4.41/1.97 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (3) DependencyPairsProof (EQUIVALENT) 4.41/1.97 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.41/1.97 Pi DP problem: 4.41/1.97 The TRS P consists of the following rules: 4.41/1.97 4.41/1.97 GOAL_IN_GAA(A, B, C) -> U1_GAA(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 GOAL_IN_GAA(A, B, C) -> S2L_IN_GA(A, D) 4.41/1.97 S2L_IN_GA(s(X), .(Y, Xs)) -> U7_GA(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 S2L_IN_GA(s(X), .(Y, Xs)) -> S2L_IN_GA(X, Xs) 4.41/1.97 U1_GAA(A, B, C, s2l_out_ga(A, D)) -> U2_GAA(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 U1_GAA(A, B, C, s2l_out_ga(A, D)) -> APPLAST_IN_GAA(D, B, C) 4.41/1.97 APPLAST_IN_GAA(L, X, Last) -> U3_GAA(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 APPLAST_IN_GAA(L, X, Last) -> APPEND_IN_GGA(L, .(X, []), LX) 4.41/1.97 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> U6_GGA(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_GGA(L1, L2, L3) 4.41/1.97 U3_GAA(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_GAA(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 U3_GAA(L, X, Last, append_out_gga(L, .(X, []), LX)) -> LAST_IN_AG(Last, LX) 4.41/1.97 LAST_IN_AG(X, .(H, T)) -> U5_AG(X, H, T, last_in_ag(X, T)) 4.41/1.97 LAST_IN_AG(X, .(H, T)) -> LAST_IN_AG(X, T) 4.41/1.97 4.41/1.97 The TRS R consists of the following rules: 4.41/1.97 4.41/1.97 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.97 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.97 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.97 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.97 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.97 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.97 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.97 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.97 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.97 4.41/1.97 The argument filtering Pi contains the following mapping: 4.41/1.97 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.97 4.41/1.97 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.97 4.41/1.97 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.97 4.41/1.97 s(x1) = s(x1) 4.41/1.97 4.41/1.97 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.97 4.41/1.97 0 = 0 4.41/1.97 4.41/1.97 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.97 4.41/1.97 .(x1, x2) = .(x2) 4.41/1.97 4.41/1.97 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.97 4.41/1.97 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.97 4.41/1.97 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.97 4.41/1.97 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.97 4.41/1.97 [] = [] 4.41/1.97 4.41/1.97 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.97 4.41/1.97 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.97 4.41/1.97 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.97 4.41/1.97 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.97 4.41/1.97 last_out_ag(x1, x2) = last_out_ag 4.41/1.97 4.41/1.97 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.97 4.41/1.97 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.97 4.41/1.97 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.97 4.41/1.97 GOAL_IN_GAA(x1, x2, x3) = GOAL_IN_GAA(x1) 4.41/1.97 4.41/1.97 U1_GAA(x1, x2, x3, x4) = U1_GAA(x4) 4.41/1.97 4.41/1.97 S2L_IN_GA(x1, x2) = S2L_IN_GA(x1) 4.41/1.97 4.41/1.97 U7_GA(x1, x2, x3, x4) = U7_GA(x4) 4.41/1.97 4.41/1.97 U2_GAA(x1, x2, x3, x4) = U2_GAA(x4) 4.41/1.97 4.41/1.97 APPLAST_IN_GAA(x1, x2, x3) = APPLAST_IN_GAA(x1) 4.41/1.97 4.41/1.97 U3_GAA(x1, x2, x3, x4) = U3_GAA(x4) 4.41/1.97 4.41/1.97 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 4.41/1.97 4.41/1.97 U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x5) 4.41/1.97 4.41/1.97 U4_GAA(x1, x2, x3, x4) = U4_GAA(x4) 4.41/1.97 4.41/1.97 LAST_IN_AG(x1, x2) = LAST_IN_AG(x2) 4.41/1.97 4.41/1.97 U5_AG(x1, x2, x3, x4) = U5_AG(x4) 4.41/1.97 4.41/1.97 4.41/1.97 We have to consider all (P,R,Pi)-chains 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (4) 4.41/1.97 Obligation: 4.41/1.97 Pi DP problem: 4.41/1.97 The TRS P consists of the following rules: 4.41/1.97 4.41/1.97 GOAL_IN_GAA(A, B, C) -> U1_GAA(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 GOAL_IN_GAA(A, B, C) -> S2L_IN_GA(A, D) 4.41/1.97 S2L_IN_GA(s(X), .(Y, Xs)) -> U7_GA(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 S2L_IN_GA(s(X), .(Y, Xs)) -> S2L_IN_GA(X, Xs) 4.41/1.97 U1_GAA(A, B, C, s2l_out_ga(A, D)) -> U2_GAA(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 U1_GAA(A, B, C, s2l_out_ga(A, D)) -> APPLAST_IN_GAA(D, B, C) 4.41/1.97 APPLAST_IN_GAA(L, X, Last) -> U3_GAA(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 APPLAST_IN_GAA(L, X, Last) -> APPEND_IN_GGA(L, .(X, []), LX) 4.41/1.97 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> U6_GGA(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_GGA(L1, L2, L3) 4.41/1.97 U3_GAA(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_GAA(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 U3_GAA(L, X, Last, append_out_gga(L, .(X, []), LX)) -> LAST_IN_AG(Last, LX) 4.41/1.97 LAST_IN_AG(X, .(H, T)) -> U5_AG(X, H, T, last_in_ag(X, T)) 4.41/1.97 LAST_IN_AG(X, .(H, T)) -> LAST_IN_AG(X, T) 4.41/1.97 4.41/1.97 The TRS R consists of the following rules: 4.41/1.97 4.41/1.97 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.97 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.97 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.97 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.97 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.97 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.97 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.97 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.97 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.97 4.41/1.97 The argument filtering Pi contains the following mapping: 4.41/1.97 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.97 4.41/1.97 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.97 4.41/1.97 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.97 4.41/1.97 s(x1) = s(x1) 4.41/1.97 4.41/1.97 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.97 4.41/1.97 0 = 0 4.41/1.97 4.41/1.97 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.97 4.41/1.97 .(x1, x2) = .(x2) 4.41/1.97 4.41/1.97 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.97 4.41/1.97 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.97 4.41/1.97 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.97 4.41/1.97 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.97 4.41/1.97 [] = [] 4.41/1.97 4.41/1.97 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.97 4.41/1.97 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.97 4.41/1.97 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.97 4.41/1.97 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.97 4.41/1.97 last_out_ag(x1, x2) = last_out_ag 4.41/1.97 4.41/1.97 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.97 4.41/1.97 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.97 4.41/1.97 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.97 4.41/1.97 GOAL_IN_GAA(x1, x2, x3) = GOAL_IN_GAA(x1) 4.41/1.97 4.41/1.97 U1_GAA(x1, x2, x3, x4) = U1_GAA(x4) 4.41/1.97 4.41/1.97 S2L_IN_GA(x1, x2) = S2L_IN_GA(x1) 4.41/1.97 4.41/1.97 U7_GA(x1, x2, x3, x4) = U7_GA(x4) 4.41/1.97 4.41/1.97 U2_GAA(x1, x2, x3, x4) = U2_GAA(x4) 4.41/1.97 4.41/1.97 APPLAST_IN_GAA(x1, x2, x3) = APPLAST_IN_GAA(x1) 4.41/1.97 4.41/1.97 U3_GAA(x1, x2, x3, x4) = U3_GAA(x4) 4.41/1.97 4.41/1.97 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 4.41/1.97 4.41/1.97 U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x5) 4.41/1.97 4.41/1.97 U4_GAA(x1, x2, x3, x4) = U4_GAA(x4) 4.41/1.97 4.41/1.97 LAST_IN_AG(x1, x2) = LAST_IN_AG(x2) 4.41/1.97 4.41/1.97 U5_AG(x1, x2, x3, x4) = U5_AG(x4) 4.41/1.97 4.41/1.97 4.41/1.97 We have to consider all (P,R,Pi)-chains 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (5) DependencyGraphProof (EQUIVALENT) 4.41/1.97 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 11 less nodes. 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (6) 4.41/1.97 Complex Obligation (AND) 4.41/1.97 4.41/1.97 ---------------------------------------- 4.41/1.97 4.41/1.97 (7) 4.41/1.97 Obligation: 4.41/1.97 Pi DP problem: 4.41/1.97 The TRS P consists of the following rules: 4.41/1.97 4.41/1.97 LAST_IN_AG(X, .(H, T)) -> LAST_IN_AG(X, T) 4.41/1.97 4.41/1.97 The TRS R consists of the following rules: 4.41/1.97 4.41/1.97 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.97 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.97 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.97 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.97 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.97 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.97 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.97 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.97 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.97 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.97 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.98 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.98 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.98 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.98 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.98 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.98 4.41/1.98 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.98 4.41/1.98 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.98 4.41/1.98 s(x1) = s(x1) 4.41/1.98 4.41/1.98 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.98 4.41/1.98 0 = 0 4.41/1.98 4.41/1.98 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.98 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.98 4.41/1.98 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.98 4.41/1.98 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.98 4.41/1.98 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.98 4.41/1.98 [] = [] 4.41/1.98 4.41/1.98 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.98 4.41/1.98 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.98 4.41/1.98 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.98 4.41/1.98 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.98 4.41/1.98 last_out_ag(x1, x2) = last_out_ag 4.41/1.98 4.41/1.98 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.98 4.41/1.98 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.98 4.41/1.98 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.98 4.41/1.98 LAST_IN_AG(x1, x2) = LAST_IN_AG(x2) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (8) UsableRulesProof (EQUIVALENT) 4.41/1.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (9) 4.41/1.98 Obligation: 4.41/1.98 Pi DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 LAST_IN_AG(X, .(H, T)) -> LAST_IN_AG(X, T) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 LAST_IN_AG(x1, x2) = LAST_IN_AG(x2) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (10) PiDPToQDPProof (SOUND) 4.41/1.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (11) 4.41/1.98 Obligation: 4.41/1.98 Q DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 LAST_IN_AG(.(T)) -> LAST_IN_AG(T) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 Q is empty. 4.41/1.98 We have to consider all (P,Q,R)-chains. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (12) QDPSizeChangeProof (EQUIVALENT) 4.41/1.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.41/1.98 4.41/1.98 From the DPs we obtained the following set of size-change graphs: 4.41/1.98 *LAST_IN_AG(.(T)) -> LAST_IN_AG(T) 4.41/1.98 The graph contains the following edges 1 > 1 4.41/1.98 4.41/1.98 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (13) 4.41/1.98 YES 4.41/1.98 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (14) 4.41/1.98 Obligation: 4.41/1.98 Pi DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_GGA(L1, L2, L3) 4.41/1.98 4.41/1.98 The TRS R consists of the following rules: 4.41/1.98 4.41/1.98 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.98 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.98 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.98 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.98 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.98 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.98 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.98 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.98 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.98 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.98 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.98 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.98 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.98 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.98 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.98 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.98 4.41/1.98 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.98 4.41/1.98 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.98 4.41/1.98 s(x1) = s(x1) 4.41/1.98 4.41/1.98 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.98 4.41/1.98 0 = 0 4.41/1.98 4.41/1.98 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.98 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.98 4.41/1.98 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.98 4.41/1.98 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.98 4.41/1.98 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.98 4.41/1.98 [] = [] 4.41/1.98 4.41/1.98 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.98 4.41/1.98 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.98 4.41/1.98 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.98 4.41/1.98 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.98 4.41/1.98 last_out_ag(x1, x2) = last_out_ag 4.41/1.98 4.41/1.98 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.98 4.41/1.98 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.98 4.41/1.98 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.98 4.41/1.98 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (15) UsableRulesProof (EQUIVALENT) 4.41/1.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (16) 4.41/1.98 Obligation: 4.41/1.98 Pi DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 APPEND_IN_GGA(.(H, L1), L2, .(H, L3)) -> APPEND_IN_GGA(L1, L2, L3) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 APPEND_IN_GGA(x1, x2, x3) = APPEND_IN_GGA(x1, x2) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (17) PiDPToQDPProof (SOUND) 4.41/1.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (18) 4.41/1.98 Obligation: 4.41/1.98 Q DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 APPEND_IN_GGA(.(L1), L2) -> APPEND_IN_GGA(L1, L2) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 Q is empty. 4.41/1.98 We have to consider all (P,Q,R)-chains. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (19) QDPSizeChangeProof (EQUIVALENT) 4.41/1.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.41/1.98 4.41/1.98 From the DPs we obtained the following set of size-change graphs: 4.41/1.98 *APPEND_IN_GGA(.(L1), L2) -> APPEND_IN_GGA(L1, L2) 4.41/1.98 The graph contains the following edges 1 > 1, 2 >= 2 4.41/1.98 4.41/1.98 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (20) 4.41/1.98 YES 4.41/1.98 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (21) 4.41/1.98 Obligation: 4.41/1.98 Pi DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 S2L_IN_GA(s(X), .(Y, Xs)) -> S2L_IN_GA(X, Xs) 4.41/1.98 4.41/1.98 The TRS R consists of the following rules: 4.41/1.98 4.41/1.98 goal_in_gaa(A, B, C) -> U1_gaa(A, B, C, s2l_in_ga(A, D)) 4.41/1.98 s2l_in_ga(s(X), .(Y, Xs)) -> U7_ga(X, Y, Xs, s2l_in_ga(X, Xs)) 4.41/1.98 s2l_in_ga(0, []) -> s2l_out_ga(0, []) 4.41/1.98 U7_ga(X, Y, Xs, s2l_out_ga(X, Xs)) -> s2l_out_ga(s(X), .(Y, Xs)) 4.41/1.98 U1_gaa(A, B, C, s2l_out_ga(A, D)) -> U2_gaa(A, B, C, applast_in_gaa(D, B, C)) 4.41/1.98 applast_in_gaa(L, X, Last) -> U3_gaa(L, X, Last, append_in_gga(L, .(X, []), LX)) 4.41/1.98 append_in_gga([], L, L) -> append_out_gga([], L, L) 4.41/1.98 append_in_gga(.(H, L1), L2, .(H, L3)) -> U6_gga(H, L1, L2, L3, append_in_gga(L1, L2, L3)) 4.41/1.98 U6_gga(H, L1, L2, L3, append_out_gga(L1, L2, L3)) -> append_out_gga(.(H, L1), L2, .(H, L3)) 4.41/1.98 U3_gaa(L, X, Last, append_out_gga(L, .(X, []), LX)) -> U4_gaa(L, X, Last, last_in_ag(Last, LX)) 4.41/1.98 last_in_ag(X, .(X, [])) -> last_out_ag(X, .(X, [])) 4.41/1.98 last_in_ag(X, .(H, T)) -> U5_ag(X, H, T, last_in_ag(X, T)) 4.41/1.98 U5_ag(X, H, T, last_out_ag(X, T)) -> last_out_ag(X, .(H, T)) 4.41/1.98 U4_gaa(L, X, Last, last_out_ag(Last, LX)) -> applast_out_gaa(L, X, Last) 4.41/1.98 U2_gaa(A, B, C, applast_out_gaa(D, B, C)) -> goal_out_gaa(A, B, C) 4.41/1.98 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 goal_in_gaa(x1, x2, x3) = goal_in_gaa(x1) 4.41/1.98 4.41/1.98 U1_gaa(x1, x2, x3, x4) = U1_gaa(x4) 4.41/1.98 4.41/1.98 s2l_in_ga(x1, x2) = s2l_in_ga(x1) 4.41/1.98 4.41/1.98 s(x1) = s(x1) 4.41/1.98 4.41/1.98 U7_ga(x1, x2, x3, x4) = U7_ga(x4) 4.41/1.98 4.41/1.98 0 = 0 4.41/1.98 4.41/1.98 s2l_out_ga(x1, x2) = s2l_out_ga(x2) 4.41/1.98 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 U2_gaa(x1, x2, x3, x4) = U2_gaa(x4) 4.41/1.98 4.41/1.98 applast_in_gaa(x1, x2, x3) = applast_in_gaa(x1) 4.41/1.98 4.41/1.98 U3_gaa(x1, x2, x3, x4) = U3_gaa(x4) 4.41/1.98 4.41/1.98 append_in_gga(x1, x2, x3) = append_in_gga(x1, x2) 4.41/1.98 4.41/1.98 [] = [] 4.41/1.98 4.41/1.98 append_out_gga(x1, x2, x3) = append_out_gga(x3) 4.41/1.98 4.41/1.98 U6_gga(x1, x2, x3, x4, x5) = U6_gga(x5) 4.41/1.98 4.41/1.98 U4_gaa(x1, x2, x3, x4) = U4_gaa(x4) 4.41/1.98 4.41/1.98 last_in_ag(x1, x2) = last_in_ag(x2) 4.41/1.98 4.41/1.98 last_out_ag(x1, x2) = last_out_ag 4.41/1.98 4.41/1.98 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.41/1.98 4.41/1.98 applast_out_gaa(x1, x2, x3) = applast_out_gaa 4.41/1.98 4.41/1.98 goal_out_gaa(x1, x2, x3) = goal_out_gaa 4.41/1.98 4.41/1.98 S2L_IN_GA(x1, x2) = S2L_IN_GA(x1) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (22) UsableRulesProof (EQUIVALENT) 4.41/1.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (23) 4.41/1.98 Obligation: 4.41/1.98 Pi DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 S2L_IN_GA(s(X), .(Y, Xs)) -> S2L_IN_GA(X, Xs) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 The argument filtering Pi contains the following mapping: 4.41/1.98 s(x1) = s(x1) 4.41/1.98 4.41/1.98 .(x1, x2) = .(x2) 4.41/1.98 4.41/1.98 S2L_IN_GA(x1, x2) = S2L_IN_GA(x1) 4.41/1.98 4.41/1.98 4.41/1.98 We have to consider all (P,R,Pi)-chains 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (24) PiDPToQDPProof (SOUND) 4.41/1.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (25) 4.41/1.98 Obligation: 4.41/1.98 Q DP problem: 4.41/1.98 The TRS P consists of the following rules: 4.41/1.98 4.41/1.98 S2L_IN_GA(s(X)) -> S2L_IN_GA(X) 4.41/1.98 4.41/1.98 R is empty. 4.41/1.98 Q is empty. 4.41/1.98 We have to consider all (P,Q,R)-chains. 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (26) QDPSizeChangeProof (EQUIVALENT) 4.41/1.98 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.41/1.98 4.41/1.98 From the DPs we obtained the following set of size-change graphs: 4.41/1.98 *S2L_IN_GA(s(X)) -> S2L_IN_GA(X) 4.41/1.98 The graph contains the following edges 1 > 1 4.41/1.98 4.41/1.98 4.41/1.98 ---------------------------------------- 4.41/1.98 4.41/1.98 (27) 4.41/1.98 YES 4.62/2.01 EOF