5.74/2.26 YES 5.74/2.28 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.74/2.28 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.74/2.28 5.74/2.28 5.74/2.28 Left Termination of the query pattern 5.74/2.28 5.74/2.28 palindrome(g) 5.74/2.28 5.74/2.28 w.r.t. the given Prolog program could successfully be proven: 5.74/2.28 5.74/2.28 (0) Prolog 5.74/2.28 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.74/2.28 (2) PiTRS 5.74/2.28 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.74/2.28 (4) PiDP 5.74/2.28 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.74/2.28 (6) AND 5.74/2.28 (7) PiDP 5.74/2.28 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.74/2.28 (9) PiDP 5.74/2.28 (10) PiDPToQDPProof [SOUND, 0 ms] 5.74/2.28 (11) QDP 5.74/2.28 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.74/2.28 (13) YES 5.74/2.28 (14) PiDP 5.74/2.28 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.74/2.28 (16) PiDP 5.74/2.28 (17) PiDPToQDPProof [SOUND, 0 ms] 5.74/2.28 (18) QDP 5.74/2.28 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.74/2.28 (20) YES 5.74/2.28 (21) PiDP 5.74/2.28 (22) UsableRulesProof [EQUIVALENT, 0 ms] 5.74/2.28 (23) PiDP 5.74/2.28 (24) PiDPToQDPProof [SOUND, 0 ms] 5.74/2.28 (25) QDP 5.74/2.28 (26) MRRProof [EQUIVALENT, 0 ms] 5.74/2.28 (27) QDP 5.74/2.28 (28) PisEmptyProof [EQUIVALENT, 0 ms] 5.74/2.28 (29) YES 5.74/2.28 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (0) 5.74/2.28 Obligation: 5.74/2.28 Clauses: 5.74/2.28 5.74/2.28 palindrome(L) :- ','(halves(L, X1s, X2s, EvenOdd), ','(eq(EvenOdd, even), eq(X1s, X2s))). 5.74/2.28 palindrome(L) :- ','(halves(L, X1s, X2s, EvenOdd), ','(eq(EvenOdd, odd), last(X1s, X1, X2s))). 5.74/2.28 halves([], [], [], even). 5.74/2.28 halves(.(X, []), .(X, []), [], odd). 5.74/2.28 halves(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) :- ','(last(.(Y, Xs), R, Rests), halves(Rests, Ts, Rs, EvenOdd)). 5.74/2.28 last(.(T, []), T, []). 5.74/2.28 last(.(H, T), X, .(H, M)) :- last(T, X, M). 5.74/2.28 eq(X, X). 5.74/2.28 5.74/2.28 5.74/2.28 Query: palindrome(g) 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (1) PrologToPiTRSProof (SOUND) 5.74/2.28 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.74/2.28 5.74/2.28 palindrome_in_1: (b) 5.74/2.28 5.74/2.28 halves_in_4: (b,f,f,f) 5.74/2.28 5.74/2.28 last_in_3: (b,f,f) (b,f,b) 5.74/2.28 5.74/2.28 Transforming Prolog into the following Term Rewriting System: 5.74/2.28 5.74/2.28 Pi-finite rewrite system: 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 5.74/2.28 5.74/2.28 5.74/2.28 5.74/2.28 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.74/2.28 5.74/2.28 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (2) 5.74/2.28 Obligation: 5.74/2.28 Pi-finite rewrite system: 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (3) DependencyPairsProof (EQUIVALENT) 5.74/2.28 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 PALINDROME_IN_G(L) -> U1_G(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 PALINDROME_IN_G(L) -> HALVES_IN_GAAA(L, X1s, X2s, EvenOdd) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> LAST_IN_GAA(.(Y, Xs), R, Rests) 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> U8_GAA(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> LAST_IN_GAA(T, X, M) 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> HALVES_IN_GAAA(Rests, Ts, Rs, EvenOdd) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_G(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> EQ_IN_GG(EvenOdd, even) 5.74/2.28 U2_G(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_G(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U2_G(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> EQ_IN_GG(X1s, X2s) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_G(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> EQ_IN_GG(EvenOdd, odd) 5.74/2.28 U4_G(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_G(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 U4_G(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> LAST_IN_GAG(X1s, X1, X2s) 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> U8_GAG(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> LAST_IN_GAG(T, X, M) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 PALINDROME_IN_G(x1) = PALINDROME_IN_G(x1) 5.74/2.28 5.74/2.28 U1_G(x1, x2) = U1_G(x2) 5.74/2.28 5.74/2.28 HALVES_IN_GAAA(x1, x2, x3, x4) = HALVES_IN_GAAA(x1) 5.74/2.28 5.74/2.28 U6_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U6_GAAA(x1, x8) 5.74/2.28 5.74/2.28 LAST_IN_GAA(x1, x2, x3) = LAST_IN_GAA(x1) 5.74/2.28 5.74/2.28 U8_GAA(x1, x2, x3, x4, x5) = U8_GAA(x1, x5) 5.74/2.28 5.74/2.28 U7_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U7_GAAA(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_G(x1, x2, x3, x4) = U2_G(x2, x3, x4) 5.74/2.28 5.74/2.28 EQ_IN_GG(x1, x2) = EQ_IN_GG(x1, x2) 5.74/2.28 5.74/2.28 U3_G(x1, x2) = U3_G(x2) 5.74/2.28 5.74/2.28 U4_G(x1, x2, x3, x4) = U4_G(x2, x3, x4) 5.74/2.28 5.74/2.28 U5_G(x1, x2) = U5_G(x2) 5.74/2.28 5.74/2.28 LAST_IN_GAG(x1, x2, x3) = LAST_IN_GAG(x1, x3) 5.74/2.28 5.74/2.28 U8_GAG(x1, x2, x3, x4, x5) = U8_GAG(x5) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (4) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 PALINDROME_IN_G(L) -> U1_G(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 PALINDROME_IN_G(L) -> HALVES_IN_GAAA(L, X1s, X2s, EvenOdd) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> LAST_IN_GAA(.(Y, Xs), R, Rests) 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> U8_GAA(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> LAST_IN_GAA(T, X, M) 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> HALVES_IN_GAAA(Rests, Ts, Rs, EvenOdd) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_G(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> EQ_IN_GG(EvenOdd, even) 5.74/2.28 U2_G(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_G(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U2_G(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> EQ_IN_GG(X1s, X2s) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_G(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U1_G(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> EQ_IN_GG(EvenOdd, odd) 5.74/2.28 U4_G(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_G(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 U4_G(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> LAST_IN_GAG(X1s, X1, X2s) 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> U8_GAG(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> LAST_IN_GAG(T, X, M) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 PALINDROME_IN_G(x1) = PALINDROME_IN_G(x1) 5.74/2.28 5.74/2.28 U1_G(x1, x2) = U1_G(x2) 5.74/2.28 5.74/2.28 HALVES_IN_GAAA(x1, x2, x3, x4) = HALVES_IN_GAAA(x1) 5.74/2.28 5.74/2.28 U6_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U6_GAAA(x1, x8) 5.74/2.28 5.74/2.28 LAST_IN_GAA(x1, x2, x3) = LAST_IN_GAA(x1) 5.74/2.28 5.74/2.28 U8_GAA(x1, x2, x3, x4, x5) = U8_GAA(x1, x5) 5.74/2.28 5.74/2.28 U7_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U7_GAAA(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_G(x1, x2, x3, x4) = U2_G(x2, x3, x4) 5.74/2.28 5.74/2.28 EQ_IN_GG(x1, x2) = EQ_IN_GG(x1, x2) 5.74/2.28 5.74/2.28 U3_G(x1, x2) = U3_G(x2) 5.74/2.28 5.74/2.28 U4_G(x1, x2, x3, x4) = U4_G(x2, x3, x4) 5.74/2.28 5.74/2.28 U5_G(x1, x2) = U5_G(x2) 5.74/2.28 5.74/2.28 LAST_IN_GAG(x1, x2, x3) = LAST_IN_GAG(x1, x3) 5.74/2.28 5.74/2.28 U8_GAG(x1, x2, x3, x4, x5) = U8_GAG(x5) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (5) DependencyGraphProof (EQUIVALENT) 5.74/2.28 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 14 less nodes. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (6) 5.74/2.28 Complex Obligation (AND) 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (7) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> LAST_IN_GAG(T, X, M) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 LAST_IN_GAG(x1, x2, x3) = LAST_IN_GAG(x1, x3) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (8) UsableRulesProof (EQUIVALENT) 5.74/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (9) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAG(.(H, T), X, .(H, M)) -> LAST_IN_GAG(T, X, M) 5.74/2.28 5.74/2.28 R is empty. 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 LAST_IN_GAG(x1, x2, x3) = LAST_IN_GAG(x1, x3) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (10) PiDPToQDPProof (SOUND) 5.74/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (11) 5.74/2.28 Obligation: 5.74/2.28 Q DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAG(.(H, T), .(H, M)) -> LAST_IN_GAG(T, M) 5.74/2.28 5.74/2.28 R is empty. 5.74/2.28 Q is empty. 5.74/2.28 We have to consider all (P,Q,R)-chains. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (12) QDPSizeChangeProof (EQUIVALENT) 5.74/2.28 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. 5.74/2.28 5.74/2.28 From the DPs we obtained the following set of size-change graphs: 5.74/2.28 *LAST_IN_GAG(.(H, T), .(H, M)) -> LAST_IN_GAG(T, M) 5.74/2.28 The graph contains the following edges 1 > 1, 2 > 2 5.74/2.28 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (13) 5.74/2.28 YES 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (14) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> LAST_IN_GAA(T, X, M) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 LAST_IN_GAA(x1, x2, x3) = LAST_IN_GAA(x1) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (15) UsableRulesProof (EQUIVALENT) 5.74/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (16) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAA(.(H, T), X, .(H, M)) -> LAST_IN_GAA(T, X, M) 5.74/2.28 5.74/2.28 R is empty. 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 LAST_IN_GAA(x1, x2, x3) = LAST_IN_GAA(x1) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (17) PiDPToQDPProof (SOUND) 5.74/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (18) 5.74/2.28 Obligation: 5.74/2.28 Q DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 LAST_IN_GAA(.(H, T)) -> LAST_IN_GAA(T) 5.74/2.28 5.74/2.28 R is empty. 5.74/2.28 Q is empty. 5.74/2.28 We have to consider all (P,Q,R)-chains. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (19) QDPSizeChangeProof (EQUIVALENT) 5.74/2.28 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. 5.74/2.28 5.74/2.28 From the DPs we obtained the following set of size-change graphs: 5.74/2.28 *LAST_IN_GAA(.(H, T)) -> LAST_IN_GAA(T) 5.74/2.28 The graph contains the following edges 1 > 1 5.74/2.28 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (20) 5.74/2.28 YES 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (21) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> HALVES_IN_GAAA(Rests, Ts, Rs, EvenOdd) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 palindrome_in_g(L) -> U1_g(L, halves_in_gaaa(L, X1s, X2s, EvenOdd)) 5.74/2.28 halves_in_gaaa([], [], [], even) -> halves_out_gaaa([], [], [], even) 5.74/2.28 halves_in_gaaa(.(X, []), .(X, []), [], odd) -> halves_out_gaaa(.(X, []), .(X, []), [], odd) 5.74/2.28 halves_in_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 U6_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_in_gaaa(Rests, Ts, Rs, EvenOdd)) 5.74/2.28 U7_gaaa(T, Y, Xs, Ts, R, Rs, EvenOdd, halves_out_gaaa(Rests, Ts, Rs, EvenOdd)) -> halves_out_gaaa(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U2_g(L, X1s, X2s, eq_in_gg(EvenOdd, even)) 5.74/2.28 eq_in_gg(X, X) -> eq_out_gg(X, X) 5.74/2.28 U2_g(L, X1s, X2s, eq_out_gg(EvenOdd, even)) -> U3_g(L, eq_in_gg(X1s, X2s)) 5.74/2.28 U3_g(L, eq_out_gg(X1s, X2s)) -> palindrome_out_g(L) 5.74/2.28 U1_g(L, halves_out_gaaa(L, X1s, X2s, EvenOdd)) -> U4_g(L, X1s, X2s, eq_in_gg(EvenOdd, odd)) 5.74/2.28 U4_g(L, X1s, X2s, eq_out_gg(EvenOdd, odd)) -> U5_g(L, last_in_gag(X1s, X1, X2s)) 5.74/2.28 last_in_gag(.(T, []), T, []) -> last_out_gag(.(T, []), T, []) 5.74/2.28 last_in_gag(.(H, T), X, .(H, M)) -> U8_gag(H, T, X, M, last_in_gag(T, X, M)) 5.74/2.28 U8_gag(H, T, X, M, last_out_gag(T, X, M)) -> last_out_gag(.(H, T), X, .(H, M)) 5.74/2.28 U5_g(L, last_out_gag(X1s, X1, X2s)) -> palindrome_out_g(L) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 palindrome_in_g(x1) = palindrome_in_g(x1) 5.74/2.28 5.74/2.28 U1_g(x1, x2) = U1_g(x2) 5.74/2.28 5.74/2.28 halves_in_gaaa(x1, x2, x3, x4) = halves_in_gaaa(x1) 5.74/2.28 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 halves_out_gaaa(x1, x2, x3, x4) = halves_out_gaaa(x2, x3, x4) 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 U6_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U6_gaaa(x1, x8) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 U7_gaaa(x1, x2, x3, x4, x5, x6, x7, x8) = U7_gaaa(x1, x5, x8) 5.74/2.28 5.74/2.28 U2_g(x1, x2, x3, x4) = U2_g(x2, x3, x4) 5.74/2.28 5.74/2.28 eq_in_gg(x1, x2) = eq_in_gg(x1, x2) 5.74/2.28 5.74/2.28 eq_out_gg(x1, x2) = eq_out_gg 5.74/2.28 5.74/2.28 even = even 5.74/2.28 5.74/2.28 U3_g(x1, x2) = U3_g(x2) 5.74/2.28 5.74/2.28 palindrome_out_g(x1) = palindrome_out_g 5.74/2.28 5.74/2.28 U4_g(x1, x2, x3, x4) = U4_g(x2, x3, x4) 5.74/2.28 5.74/2.28 odd = odd 5.74/2.28 5.74/2.28 U5_g(x1, x2) = U5_g(x2) 5.74/2.28 5.74/2.28 last_in_gag(x1, x2, x3) = last_in_gag(x1, x3) 5.74/2.28 5.74/2.28 last_out_gag(x1, x2, x3) = last_out_gag(x2) 5.74/2.28 5.74/2.28 U8_gag(x1, x2, x3, x4, x5) = U8_gag(x5) 5.74/2.28 5.74/2.28 HALVES_IN_GAAA(x1, x2, x3, x4) = HALVES_IN_GAAA(x1) 5.74/2.28 5.74/2.28 U6_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U6_GAAA(x1, x8) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (22) UsableRulesProof (EQUIVALENT) 5.74/2.28 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (23) 5.74/2.28 Obligation: 5.74/2.28 Pi DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_out_gaa(.(Y, Xs), R, Rests)) -> HALVES_IN_GAAA(Rests, Ts, Rs, EvenOdd) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs)), .(T, Ts), .(R, Rs), EvenOdd) -> U6_GAAA(T, Y, Xs, Ts, R, Rs, EvenOdd, last_in_gaa(.(Y, Xs), R, Rests)) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 last_in_gaa(.(T, []), T, []) -> last_out_gaa(.(T, []), T, []) 5.74/2.28 last_in_gaa(.(H, T), X, .(H, M)) -> U8_gaa(H, T, X, M, last_in_gaa(T, X, M)) 5.74/2.28 U8_gaa(H, T, X, M, last_out_gaa(T, X, M)) -> last_out_gaa(.(H, T), X, .(H, M)) 5.74/2.28 5.74/2.28 The argument filtering Pi contains the following mapping: 5.74/2.28 [] = [] 5.74/2.28 5.74/2.28 .(x1, x2) = .(x1, x2) 5.74/2.28 5.74/2.28 last_in_gaa(x1, x2, x3) = last_in_gaa(x1) 5.74/2.28 5.74/2.28 last_out_gaa(x1, x2, x3) = last_out_gaa(x2, x3) 5.74/2.28 5.74/2.28 U8_gaa(x1, x2, x3, x4, x5) = U8_gaa(x1, x5) 5.74/2.28 5.74/2.28 HALVES_IN_GAAA(x1, x2, x3, x4) = HALVES_IN_GAAA(x1) 5.74/2.28 5.74/2.28 U6_GAAA(x1, x2, x3, x4, x5, x6, x7, x8) = U6_GAAA(x1, x8) 5.74/2.28 5.74/2.28 5.74/2.28 We have to consider all (P,R,Pi)-chains 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (24) PiDPToQDPProof (SOUND) 5.74/2.28 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (25) 5.74/2.28 Obligation: 5.74/2.28 Q DP problem: 5.74/2.28 The TRS P consists of the following rules: 5.74/2.28 5.74/2.28 U6_GAAA(T, last_out_gaa(R, Rests)) -> HALVES_IN_GAAA(Rests) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs))) -> U6_GAAA(T, last_in_gaa(.(Y, Xs))) 5.74/2.28 5.74/2.28 The TRS R consists of the following rules: 5.74/2.28 5.74/2.28 last_in_gaa(.(T, [])) -> last_out_gaa(T, []) 5.74/2.28 last_in_gaa(.(H, T)) -> U8_gaa(H, last_in_gaa(T)) 5.74/2.28 U8_gaa(H, last_out_gaa(X, M)) -> last_out_gaa(X, .(H, M)) 5.74/2.28 5.74/2.28 The set Q consists of the following terms: 5.74/2.28 5.74/2.28 last_in_gaa(x0) 5.74/2.28 U8_gaa(x0, x1) 5.74/2.28 5.74/2.28 We have to consider all (P,Q,R)-chains. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (26) MRRProof (EQUIVALENT) 5.74/2.28 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 5.74/2.28 5.74/2.28 Strictly oriented dependency pairs: 5.74/2.28 5.74/2.28 U6_GAAA(T, last_out_gaa(R, Rests)) -> HALVES_IN_GAAA(Rests) 5.74/2.28 HALVES_IN_GAAA(.(T, .(Y, Xs))) -> U6_GAAA(T, last_in_gaa(.(Y, Xs))) 5.74/2.28 5.74/2.28 Strictly oriented rules of the TRS R: 5.74/2.28 5.74/2.28 last_in_gaa(.(T, [])) -> last_out_gaa(T, []) 5.74/2.28 last_in_gaa(.(H, T)) -> U8_gaa(H, last_in_gaa(T)) 5.74/2.28 U8_gaa(H, last_out_gaa(X, M)) -> last_out_gaa(X, .(H, M)) 5.74/2.28 5.74/2.28 Used ordering: Knuth-Bendix order [KBO] with precedence:last_in_gaa_1 > U8_gaa_2 > HALVES_IN_GAAA_1 > U6_GAAA_2 > last_out_gaa_2 > [] > ._2 5.74/2.28 5.74/2.28 and weight map: 5.74/2.28 5.74/2.28 []=1 5.74/2.28 last_in_gaa_1=1 5.74/2.28 HALVES_IN_GAAA_1=1 5.74/2.28 ._2=0 5.74/2.28 last_out_gaa_2=1 5.74/2.28 U8_gaa_2=0 5.74/2.28 U6_GAAA_2=0 5.74/2.28 5.74/2.28 The variable weight is 1 5.74/2.28 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (27) 5.74/2.28 Obligation: 5.74/2.28 Q DP problem: 5.74/2.28 P is empty. 5.74/2.28 R is empty. 5.74/2.28 The set Q consists of the following terms: 5.74/2.28 5.74/2.28 last_in_gaa(x0) 5.74/2.28 U8_gaa(x0, x1) 5.74/2.28 5.74/2.28 We have to consider all (P,Q,R)-chains. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (28) PisEmptyProof (EQUIVALENT) 5.74/2.28 The TRS P is empty. Hence, there is no (P,Q,R) chain. 5.74/2.28 ---------------------------------------- 5.74/2.28 5.74/2.28 (29) 5.74/2.28 YES 5.87/2.32 EOF