7.56/2.88 YES 8.09/2.91 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 8.09/2.91 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.09/2.91 8.09/2.91 8.09/2.91 Left Termination of the query pattern 8.09/2.91 8.09/2.91 queens(a) 8.09/2.91 8.09/2.91 w.r.t. the given Prolog program could successfully be proven: 8.09/2.91 8.09/2.91 (0) Prolog 8.09/2.91 (1) PrologToPiTRSProof [SOUND, 37 ms] 8.09/2.91 (2) PiTRS 8.09/2.91 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.09/2.91 (4) PiDP 8.09/2.91 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.09/2.91 (6) AND 8.09/2.91 (7) PiDP 8.09/2.91 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (9) PiDP 8.09/2.91 (10) PiDPToQDPProof [SOUND, 18 ms] 8.09/2.91 (11) QDP 8.09/2.91 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.91 (13) YES 8.09/2.91 (14) PiDP 8.09/2.91 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (16) PiDP 8.09/2.91 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 8.09/2.91 (18) QDP 8.09/2.91 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.91 (20) YES 8.09/2.91 (21) PiDP 8.09/2.91 (22) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (23) PiDP 8.09/2.91 (24) PiDPToQDPProof [SOUND, 0 ms] 8.09/2.91 (25) QDP 8.09/2.91 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.91 (27) YES 8.09/2.91 (28) PiDP 8.09/2.91 (29) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (30) PiDP 8.09/2.91 (31) PiDPToQDPProof [SOUND, 0 ms] 8.09/2.91 (32) QDP 8.09/2.91 (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.91 (34) YES 8.09/2.91 (35) PiDP 8.09/2.91 (36) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (37) PiDP 8.09/2.91 (38) PiDPToQDPProof [SOUND, 0 ms] 8.09/2.91 (39) QDP 8.09/2.91 (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.09/2.91 (41) YES 8.09/2.91 (42) PiDP 8.09/2.91 (43) UsableRulesProof [EQUIVALENT, 0 ms] 8.09/2.91 (44) PiDP 8.09/2.91 (45) PiDPToQDPProof [SOUND, 0 ms] 8.09/2.91 (46) QDP 8.09/2.91 (47) MRRProof [EQUIVALENT, 14 ms] 8.09/2.91 (48) QDP 8.09/2.91 (49) PisEmptyProof [EQUIVALENT, 0 ms] 8.09/2.91 (50) YES 8.09/2.91 8.09/2.91 8.09/2.91 ---------------------------------------- 8.09/2.91 8.09/2.91 (0) 8.09/2.91 Obligation: 8.09/2.91 Clauses: 8.09/2.91 8.09/2.91 queens(Y) :- ','(perm(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y), safe(Y)). 8.09/2.91 perm([], []). 8.09/2.91 perm(.(X, Y), .(V, Res)) :- ','(delete(V, .(X, Y), Rest), perm(Rest, Res)). 8.09/2.91 delete(X, .(X, Y), Y). 8.09/2.91 delete(X, .(F, T), .(F, R)) :- delete(X, T, R). 8.09/2.91 safe([]). 8.09/2.91 safe(.(X, Y)) :- ','(noattack(X, Y, s(0)), safe(Y)). 8.09/2.91 noattack(X, [], N). 8.09/2.91 noattack(X, .(F, T), N) :- ','(notEq(X, F), ','(add(F, N, FplusN), ','(notEq(X, FplusN), ','(add(X, N, XplusN), ','(notEq(F, XplusN), noattack(X, T, s(N))))))). 8.09/2.91 add(0, X, X). 8.09/2.91 add(s(X), Y, s(Z)) :- add(X, Y, Z). 8.09/2.91 notEq(0, s(X)). 8.09/2.91 notEq(s(X), 0). 8.09/2.91 notEq(s(X), s(Y)) :- notEq(X, Y). 8.09/2.91 8.09/2.91 8.09/2.91 Query: queens(a) 8.09/2.91 ---------------------------------------- 8.09/2.91 8.09/2.91 (1) PrologToPiTRSProof (SOUND) 8.09/2.91 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.09/2.91 8.09/2.91 queens_in_1: (f) 8.09/2.91 8.09/2.91 perm_in_2: (b,f) 8.09/2.91 8.09/2.91 delete_in_3: (f,b,f) 8.09/2.91 8.09/2.91 safe_in_1: (b) 8.09/2.91 8.09/2.91 noattack_in_3: (b,b,b) 8.09/2.91 8.09/2.91 notEq_in_2: (b,b) 8.09/2.91 8.09/2.91 add_in_3: (b,b,f) 8.09/2.91 8.09/2.91 Transforming Prolog into the following Term Rewriting System: 8.09/2.91 8.09/2.91 Pi-finite rewrite system: 8.09/2.91 The TRS R consists of the following rules: 8.09/2.91 8.09/2.91 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.91 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.91 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.91 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.91 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.91 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.91 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.91 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.91 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.91 safe_in_g([]) -> safe_out_g([]) 8.09/2.91 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.91 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.91 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.91 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.91 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.91 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.91 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.91 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.91 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.91 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.91 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.91 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.91 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.91 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.91 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.91 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.91 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.91 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.91 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.91 8.09/2.91 The argument filtering Pi contains the following mapping: 8.09/2.91 queens_in_a(x1) = queens_in_a 8.09/2.91 8.09/2.91 U1_a(x1, x2) = U1_a(x2) 8.09/2.91 8.09/2.91 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.91 8.09/2.91 [] = [] 8.09/2.91 8.09/2.91 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.91 8.09/2.91 .(x1, x2) = .(x1, x2) 8.09/2.91 8.09/2.91 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.91 8.09/2.91 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.91 8.09/2.91 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.91 8.09/2.91 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.91 8.09/2.91 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.91 8.09/2.91 s(x1) = s(x1) 8.09/2.91 8.09/2.91 0 = 0 8.09/2.91 8.09/2.91 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.91 8.09/2.91 safe_in_g(x1) = safe_in_g(x1) 8.09/2.91 8.09/2.91 safe_out_g(x1) = safe_out_g 8.09/2.91 8.09/2.91 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.91 8.09/2.91 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.91 8.09/2.91 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.91 8.09/2.91 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.91 8.09/2.91 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.91 8.09/2.91 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.91 8.09/2.91 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.91 8.09/2.91 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.91 8.09/2.91 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.91 8.09/2.91 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.91 8.09/2.91 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.91 8.09/2.91 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.91 8.09/2.91 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.91 8.09/2.91 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.91 8.09/2.91 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.91 8.09/2.91 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.91 8.09/2.91 queens_out_a(x1) = queens_out_a(x1) 8.09/2.91 8.09/2.91 8.09/2.91 8.09/2.91 8.09/2.91 8.09/2.91 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.09/2.91 8.09/2.91 8.09/2.91 8.09/2.91 ---------------------------------------- 8.09/2.91 8.09/2.91 (2) 8.09/2.91 Obligation: 8.09/2.91 Pi-finite rewrite system: 8.09/2.91 The TRS R consists of the following rules: 8.09/2.91 8.09/2.91 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.91 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.91 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.91 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.91 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.91 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.91 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.91 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.91 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.91 safe_in_g([]) -> safe_out_g([]) 8.09/2.91 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.91 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.91 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.91 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.91 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.91 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.91 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.91 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.91 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.91 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.91 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.91 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.91 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.91 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.91 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.91 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.91 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.91 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.91 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.91 8.09/2.91 The argument filtering Pi contains the following mapping: 8.09/2.91 queens_in_a(x1) = queens_in_a 8.09/2.91 8.09/2.91 U1_a(x1, x2) = U1_a(x2) 8.09/2.91 8.09/2.91 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.91 8.09/2.91 [] = [] 8.09/2.91 8.09/2.91 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.91 8.09/2.91 .(x1, x2) = .(x1, x2) 8.09/2.91 8.09/2.91 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.91 8.09/2.91 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.91 8.09/2.91 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.91 8.09/2.91 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.91 8.09/2.91 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.91 8.09/2.91 s(x1) = s(x1) 8.09/2.91 8.09/2.91 0 = 0 8.09/2.91 8.09/2.91 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.91 8.09/2.91 safe_in_g(x1) = safe_in_g(x1) 8.09/2.91 8.09/2.91 safe_out_g(x1) = safe_out_g 8.09/2.91 8.09/2.91 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.91 8.09/2.91 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.91 8.09/2.91 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.91 8.09/2.91 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.91 8.09/2.91 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.91 8.09/2.91 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.91 8.09/2.91 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.91 8.09/2.91 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.91 8.09/2.91 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.91 8.09/2.91 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.91 8.09/2.91 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.91 8.09/2.91 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.91 8.09/2.91 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.91 8.09/2.91 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.91 8.09/2.91 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.91 8.09/2.91 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.91 8.09/2.91 queens_out_a(x1) = queens_out_a(x1) 8.09/2.91 8.09/2.91 8.09/2.91 8.09/2.91 ---------------------------------------- 8.09/2.91 8.09/2.91 (3) DependencyPairsProof (EQUIVALENT) 8.09/2.91 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.09/2.91 Pi DP problem: 8.09/2.91 The TRS P consists of the following rules: 8.09/2.91 8.09/2.91 QUEENS_IN_A(Y) -> U1_A(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.91 QUEENS_IN_A(Y) -> PERM_IN_GA(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y) 8.09/2.91 PERM_IN_GA(.(X, Y), .(V, Res)) -> U3_GA(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.91 PERM_IN_GA(.(X, Y), .(V, Res)) -> DELETE_IN_AGA(V, .(X, Y), Rest) 8.09/2.91 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> U5_AGA(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.91 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> DELETE_IN_AGA(X, T, R) 8.09/2.91 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_GA(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.91 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> PERM_IN_GA(Rest, Res) 8.09/2.91 U1_A(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_A(Y, safe_in_g(Y)) 8.09/2.91 U1_A(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> SAFE_IN_G(Y) 8.09/2.91 SAFE_IN_G(.(X, Y)) -> U6_G(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.91 SAFE_IN_G(.(X, Y)) -> NOATTACK_IN_GGG(X, Y, s(0)) 8.09/2.91 NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.91 NOATTACK_IN_GGG(X, .(F, T), N) -> NOTEQ_IN_GG(X, F) 8.09/2.91 NOTEQ_IN_GG(s(X), s(Y)) -> U15_GG(X, Y, notEq_in_gg(X, Y)) 8.09/2.91 NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.91 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> U9_GGG(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.91 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> ADD_IN_GGA(F, N, FplusN) 8.09/2.91 ADD_IN_GGA(s(X), Y, s(Z)) -> U14_GGA(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.91 ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) 8.09/2.91 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_GGG(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.91 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> NOTEQ_IN_GG(X, FplusN) 8.09/2.91 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_GGG(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.91 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> ADD_IN_GGA(X, N, XplusN) 8.09/2.91 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_GGG(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.91 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> NOTEQ_IN_GG(F, XplusN) 8.09/2.91 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_GGG(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.91 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.91 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_G(X, Y, safe_in_g(Y)) 8.09/2.91 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> SAFE_IN_G(Y) 8.09/2.91 8.09/2.91 The TRS R consists of the following rules: 8.09/2.91 8.09/2.91 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.91 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.91 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.91 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.91 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.91 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.91 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.91 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.91 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.91 safe_in_g([]) -> safe_out_g([]) 8.09/2.91 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.91 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.91 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.91 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.91 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.91 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.91 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.91 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.91 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.91 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.91 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.91 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.91 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.91 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.91 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.91 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.91 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.91 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.91 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.91 8.09/2.91 The argument filtering Pi contains the following mapping: 8.09/2.91 queens_in_a(x1) = queens_in_a 8.09/2.92 8.09/2.92 U1_a(x1, x2) = U1_a(x2) 8.09/2.92 8.09/2.92 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.92 8.09/2.92 [] = [] 8.09/2.92 8.09/2.92 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.92 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.92 8.09/2.92 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.92 8.09/2.92 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.92 8.09/2.92 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.92 8.09/2.92 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.92 8.09/2.92 safe_in_g(x1) = safe_in_g(x1) 8.09/2.92 8.09/2.92 safe_out_g(x1) = safe_out_g 8.09/2.92 8.09/2.92 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.92 8.09/2.92 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.92 8.09/2.92 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.92 8.09/2.92 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.92 8.09/2.92 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.92 8.09/2.92 queens_out_a(x1) = queens_out_a(x1) 8.09/2.92 8.09/2.92 QUEENS_IN_A(x1) = QUEENS_IN_A 8.09/2.92 8.09/2.92 U1_A(x1, x2) = U1_A(x2) 8.09/2.92 8.09/2.92 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 8.09/2.92 8.09/2.92 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) 8.09/2.92 8.09/2.92 DELETE_IN_AGA(x1, x2, x3) = DELETE_IN_AGA(x2) 8.09/2.92 8.09/2.92 U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x5) 8.09/2.92 8.09/2.92 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x3, x5) 8.09/2.92 8.09/2.92 U2_A(x1, x2) = U2_A(x1, x2) 8.09/2.92 8.09/2.92 SAFE_IN_G(x1) = SAFE_IN_G(x1) 8.09/2.92 8.09/2.92 U6_G(x1, x2, x3) = U6_G(x2, x3) 8.09/2.92 8.09/2.92 NOATTACK_IN_GGG(x1, x2, x3) = NOATTACK_IN_GGG(x1, x2, x3) 8.09/2.92 8.09/2.92 U8_GGG(x1, x2, x3, x4, x5) = U8_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) 8.09/2.92 8.09/2.92 U15_GG(x1, x2, x3) = U15_GG(x3) 8.09/2.92 8.09/2.92 U9_GGG(x1, x2, x3, x4, x5) = U9_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) 8.09/2.92 8.09/2.92 U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) 8.09/2.92 8.09/2.92 U10_GGG(x1, x2, x3, x4, x5, x6) = U10_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_GGG(x1, x2, x3, x4, x5, x6) = U11_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_GGG(x1, x2, x3, x4, x5) = U12_GGG(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_GGG(x1, x2, x3, x4, x5) = U13_GGG(x5) 8.09/2.92 8.09/2.92 U7_G(x1, x2, x3) = U7_G(x3) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (4) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 QUEENS_IN_A(Y) -> U1_A(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 QUEENS_IN_A(Y) -> PERM_IN_GA(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y) 8.09/2.92 PERM_IN_GA(.(X, Y), .(V, Res)) -> U3_GA(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 PERM_IN_GA(.(X, Y), .(V, Res)) -> DELETE_IN_AGA(V, .(X, Y), Rest) 8.09/2.92 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> U5_AGA(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> DELETE_IN_AGA(X, T, R) 8.09/2.92 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_GA(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.92 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> PERM_IN_GA(Rest, Res) 8.09/2.92 U1_A(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_A(Y, safe_in_g(Y)) 8.09/2.92 U1_A(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> SAFE_IN_G(Y) 8.09/2.92 SAFE_IN_G(.(X, Y)) -> U6_G(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 SAFE_IN_G(.(X, Y)) -> NOATTACK_IN_GGG(X, Y, s(0)) 8.09/2.92 NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 NOATTACK_IN_GGG(X, .(F, T), N) -> NOTEQ_IN_GG(X, F) 8.09/2.92 NOTEQ_IN_GG(s(X), s(Y)) -> U15_GG(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.92 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> U9_GGG(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> ADD_IN_GGA(F, N, FplusN) 8.09/2.92 ADD_IN_GGA(s(X), Y, s(Z)) -> U14_GGA(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) 8.09/2.92 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_GGG(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> NOTEQ_IN_GG(X, FplusN) 8.09/2.92 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_GGG(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> ADD_IN_GGA(X, N, XplusN) 8.09/2.92 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_GGG(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> NOTEQ_IN_GG(F, XplusN) 8.09/2.92 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_GGG(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.92 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.92 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_G(X, Y, safe_in_g(Y)) 8.09/2.92 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> SAFE_IN_G(Y) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.92 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.92 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.92 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.92 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.92 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.92 safe_in_g([]) -> safe_out_g([]) 8.09/2.92 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.92 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.92 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.92 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.92 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.92 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.92 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.92 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.92 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.92 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 queens_in_a(x1) = queens_in_a 8.09/2.92 8.09/2.92 U1_a(x1, x2) = U1_a(x2) 8.09/2.92 8.09/2.92 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.92 8.09/2.92 [] = [] 8.09/2.92 8.09/2.92 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.92 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.92 8.09/2.92 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.92 8.09/2.92 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.92 8.09/2.92 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.92 8.09/2.92 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.92 8.09/2.92 safe_in_g(x1) = safe_in_g(x1) 8.09/2.92 8.09/2.92 safe_out_g(x1) = safe_out_g 8.09/2.92 8.09/2.92 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.92 8.09/2.92 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.92 8.09/2.92 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.92 8.09/2.92 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.92 8.09/2.92 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.92 8.09/2.92 queens_out_a(x1) = queens_out_a(x1) 8.09/2.92 8.09/2.92 QUEENS_IN_A(x1) = QUEENS_IN_A 8.09/2.92 8.09/2.92 U1_A(x1, x2) = U1_A(x2) 8.09/2.92 8.09/2.92 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 8.09/2.92 8.09/2.92 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) 8.09/2.92 8.09/2.92 DELETE_IN_AGA(x1, x2, x3) = DELETE_IN_AGA(x2) 8.09/2.92 8.09/2.92 U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x2, x5) 8.09/2.92 8.09/2.92 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x3, x5) 8.09/2.92 8.09/2.92 U2_A(x1, x2) = U2_A(x1, x2) 8.09/2.92 8.09/2.92 SAFE_IN_G(x1) = SAFE_IN_G(x1) 8.09/2.92 8.09/2.92 U6_G(x1, x2, x3) = U6_G(x2, x3) 8.09/2.92 8.09/2.92 NOATTACK_IN_GGG(x1, x2, x3) = NOATTACK_IN_GGG(x1, x2, x3) 8.09/2.92 8.09/2.92 U8_GGG(x1, x2, x3, x4, x5) = U8_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) 8.09/2.92 8.09/2.92 U15_GG(x1, x2, x3) = U15_GG(x3) 8.09/2.92 8.09/2.92 U9_GGG(x1, x2, x3, x4, x5) = U9_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) 8.09/2.92 8.09/2.92 U14_GGA(x1, x2, x3, x4) = U14_GGA(x4) 8.09/2.92 8.09/2.92 U10_GGG(x1, x2, x3, x4, x5, x6) = U10_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_GGG(x1, x2, x3, x4, x5, x6) = U11_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_GGG(x1, x2, x3, x4, x5) = U12_GGG(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_GGG(x1, x2, x3, x4, x5) = U13_GGG(x5) 8.09/2.92 8.09/2.92 U7_G(x1, x2, x3) = U7_G(x3) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (5) DependencyGraphProof (EQUIVALENT) 8.09/2.92 The approximation of the Dependency Graph [LOPSTR] contains 6 SCCs with 17 less nodes. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (6) 8.09/2.92 Complex Obligation (AND) 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (7) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.92 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.92 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.92 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.92 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.92 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.92 safe_in_g([]) -> safe_out_g([]) 8.09/2.92 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.92 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.92 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.92 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.92 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.92 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.92 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.92 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.92 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.92 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 queens_in_a(x1) = queens_in_a 8.09/2.92 8.09/2.92 U1_a(x1, x2) = U1_a(x2) 8.09/2.92 8.09/2.92 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.92 8.09/2.92 [] = [] 8.09/2.92 8.09/2.92 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.92 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.92 8.09/2.92 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.92 8.09/2.92 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.92 8.09/2.92 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.92 8.09/2.92 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.92 8.09/2.92 safe_in_g(x1) = safe_in_g(x1) 8.09/2.92 8.09/2.92 safe_out_g(x1) = safe_out_g 8.09/2.92 8.09/2.92 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.92 8.09/2.92 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.92 8.09/2.92 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.92 8.09/2.92 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.92 8.09/2.92 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.92 8.09/2.92 queens_out_a(x1) = queens_out_a(x1) 8.09/2.92 8.09/2.92 ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (8) UsableRulesProof (EQUIVALENT) 8.09/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (9) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 ADD_IN_GGA(s(X), Y, s(Z)) -> ADD_IN_GGA(X, Y, Z) 8.09/2.92 8.09/2.92 R is empty. 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 ADD_IN_GGA(x1, x2, x3) = ADD_IN_GGA(x1, x2) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (10) PiDPToQDPProof (SOUND) 8.09/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (11) 8.09/2.92 Obligation: 8.09/2.92 Q DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 ADD_IN_GGA(s(X), Y) -> ADD_IN_GGA(X, Y) 8.09/2.92 8.09/2.92 R is empty. 8.09/2.92 Q is empty. 8.09/2.92 We have to consider all (P,Q,R)-chains. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (12) QDPSizeChangeProof (EQUIVALENT) 8.09/2.92 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.09/2.92 8.09/2.92 From the DPs we obtained the following set of size-change graphs: 8.09/2.92 *ADD_IN_GGA(s(X), Y) -> ADD_IN_GGA(X, Y) 8.09/2.92 The graph contains the following edges 1 > 1, 2 >= 2 8.09/2.92 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (13) 8.09/2.92 YES 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (14) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.92 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.92 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.92 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.92 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.92 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.92 safe_in_g([]) -> safe_out_g([]) 8.09/2.92 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.92 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.92 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.92 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.92 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.92 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.92 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.92 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.92 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.92 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 queens_in_a(x1) = queens_in_a 8.09/2.92 8.09/2.92 U1_a(x1, x2) = U1_a(x2) 8.09/2.92 8.09/2.92 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.92 8.09/2.92 [] = [] 8.09/2.92 8.09/2.92 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.92 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.92 8.09/2.92 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.92 8.09/2.92 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.92 8.09/2.92 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.92 8.09/2.92 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.92 8.09/2.92 safe_in_g(x1) = safe_in_g(x1) 8.09/2.92 8.09/2.92 safe_out_g(x1) = safe_out_g 8.09/2.92 8.09/2.92 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.92 8.09/2.92 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.92 8.09/2.92 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.92 8.09/2.92 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.92 8.09/2.92 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.92 8.09/2.92 queens_out_a(x1) = queens_out_a(x1) 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (15) UsableRulesProof (EQUIVALENT) 8.09/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (16) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.92 8.09/2.92 R is empty. 8.09/2.92 Pi is empty. 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (17) PiDPToQDPProof (EQUIVALENT) 8.09/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (18) 8.09/2.92 Obligation: 8.09/2.92 Q DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.92 8.09/2.92 R is empty. 8.09/2.92 Q is empty. 8.09/2.92 We have to consider all (P,Q,R)-chains. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (19) QDPSizeChangeProof (EQUIVALENT) 8.09/2.92 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.09/2.92 8.09/2.92 From the DPs we obtained the following set of size-change graphs: 8.09/2.92 *NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) 8.09/2.92 The graph contains the following edges 1 > 1, 2 > 2 8.09/2.92 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (20) 8.09/2.92 YES 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (21) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> U9_GGG(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_GGG(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_GGG(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_GGG(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.92 NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.92 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.92 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.92 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.92 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.92 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.92 safe_in_g([]) -> safe_out_g([]) 8.09/2.92 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.92 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.92 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.92 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.92 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.92 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.92 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.92 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.92 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.92 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 queens_in_a(x1) = queens_in_a 8.09/2.92 8.09/2.92 U1_a(x1, x2) = U1_a(x2) 8.09/2.92 8.09/2.92 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.92 8.09/2.92 [] = [] 8.09/2.92 8.09/2.92 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.92 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.92 8.09/2.92 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.92 8.09/2.92 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.92 8.09/2.92 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.92 8.09/2.92 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.92 8.09/2.92 safe_in_g(x1) = safe_in_g(x1) 8.09/2.92 8.09/2.92 safe_out_g(x1) = safe_out_g 8.09/2.92 8.09/2.92 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.92 8.09/2.92 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.92 8.09/2.92 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.92 8.09/2.92 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.92 8.09/2.92 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.92 8.09/2.92 queens_out_a(x1) = queens_out_a(x1) 8.09/2.92 8.09/2.92 NOATTACK_IN_GGG(x1, x2, x3) = NOATTACK_IN_GGG(x1, x2, x3) 8.09/2.92 8.09/2.92 U8_GGG(x1, x2, x3, x4, x5) = U8_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 U9_GGG(x1, x2, x3, x4, x5) = U9_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 U10_GGG(x1, x2, x3, x4, x5, x6) = U10_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_GGG(x1, x2, x3, x4, x5, x6) = U11_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_GGG(x1, x2, x3, x4, x5) = U12_GGG(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (22) UsableRulesProof (EQUIVALENT) 8.09/2.92 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (23) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 U8_GGG(X, F, T, N, notEq_out_gg(X, F)) -> U9_GGG(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.92 U9_GGG(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_GGG(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_GGG(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_GGG(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.92 U11_GGG(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_GGG(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_GGG(X, F, T, N, notEq_out_gg(F, XplusN)) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.92 NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.92 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.92 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.92 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.92 8.09/2.92 The argument filtering Pi contains the following mapping: 8.09/2.92 .(x1, x2) = .(x1, x2) 8.09/2.92 8.09/2.92 s(x1) = s(x1) 8.09/2.92 8.09/2.92 0 = 0 8.09/2.92 8.09/2.92 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.92 8.09/2.92 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.92 8.09/2.92 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.92 8.09/2.92 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.92 8.09/2.92 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.92 8.09/2.92 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.92 8.09/2.92 NOATTACK_IN_GGG(x1, x2, x3) = NOATTACK_IN_GGG(x1, x2, x3) 8.09/2.92 8.09/2.92 U8_GGG(x1, x2, x3, x4, x5) = U8_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 U9_GGG(x1, x2, x3, x4, x5) = U9_GGG(x1, x2, x3, x4, x5) 8.09/2.92 8.09/2.92 U10_GGG(x1, x2, x3, x4, x5, x6) = U10_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U11_GGG(x1, x2, x3, x4, x5, x6) = U11_GGG(x1, x2, x3, x4, x6) 8.09/2.92 8.09/2.92 U12_GGG(x1, x2, x3, x4, x5) = U12_GGG(x1, x3, x4, x5) 8.09/2.92 8.09/2.92 8.09/2.92 We have to consider all (P,R,Pi)-chains 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (24) PiDPToQDPProof (SOUND) 8.09/2.92 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (25) 8.09/2.92 Obligation: 8.09/2.92 Q DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 U8_GGG(X, F, T, N, notEq_out_gg) -> U9_GGG(X, F, T, N, add_in_gga(F, N)) 8.09/2.92 U9_GGG(X, F, T, N, add_out_gga(FplusN)) -> U10_GGG(X, F, T, N, notEq_in_gg(X, FplusN)) 8.09/2.92 U10_GGG(X, F, T, N, notEq_out_gg) -> U11_GGG(X, F, T, N, add_in_gga(X, N)) 8.09/2.92 U11_GGG(X, F, T, N, add_out_gga(XplusN)) -> U12_GGG(X, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 U12_GGG(X, T, N, notEq_out_gg) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.92 NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 add_in_gga(0, X) -> add_out_gga(X) 8.09/2.92 add_in_gga(s(X), Y) -> U14_gga(add_in_gga(X, Y)) 8.09/2.92 notEq_in_gg(0, s(X)) -> notEq_out_gg 8.09/2.92 notEq_in_gg(s(X), 0) -> notEq_out_gg 8.09/2.92 notEq_in_gg(s(X), s(Y)) -> U15_gg(notEq_in_gg(X, Y)) 8.09/2.92 U14_gga(add_out_gga(Z)) -> add_out_gga(s(Z)) 8.09/2.92 U15_gg(notEq_out_gg) -> notEq_out_gg 8.09/2.92 8.09/2.92 The set Q consists of the following terms: 8.09/2.92 8.09/2.92 add_in_gga(x0, x1) 8.09/2.92 notEq_in_gg(x0, x1) 8.09/2.92 U14_gga(x0) 8.09/2.92 U15_gg(x0) 8.09/2.92 8.09/2.92 We have to consider all (P,Q,R)-chains. 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (26) QDPSizeChangeProof (EQUIVALENT) 8.09/2.92 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.09/2.92 8.09/2.92 From the DPs we obtained the following set of size-change graphs: 8.09/2.92 *U9_GGG(X, F, T, N, add_out_gga(FplusN)) -> U10_GGG(X, F, T, N, notEq_in_gg(X, FplusN)) 8.09/2.92 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4 8.09/2.92 8.09/2.92 8.09/2.92 *NOATTACK_IN_GGG(X, .(F, T), N) -> U8_GGG(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.92 The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 3 >= 4 8.09/2.92 8.09/2.92 8.09/2.92 *U10_GGG(X, F, T, N, notEq_out_gg) -> U11_GGG(X, F, T, N, add_in_gga(X, N)) 8.09/2.92 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4 8.09/2.92 8.09/2.92 8.09/2.92 *U8_GGG(X, F, T, N, notEq_out_gg) -> U9_GGG(X, F, T, N, add_in_gga(F, N)) 8.09/2.92 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4 8.09/2.92 8.09/2.92 8.09/2.92 *U11_GGG(X, F, T, N, add_out_gga(XplusN)) -> U12_GGG(X, T, N, notEq_in_gg(F, XplusN)) 8.09/2.92 The graph contains the following edges 1 >= 1, 3 >= 2, 4 >= 3 8.09/2.92 8.09/2.92 8.09/2.92 *U12_GGG(X, T, N, notEq_out_gg) -> NOATTACK_IN_GGG(X, T, s(N)) 8.09/2.92 The graph contains the following edges 1 >= 1, 2 >= 2 8.09/2.92 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (27) 8.09/2.92 YES 8.09/2.92 8.09/2.92 ---------------------------------------- 8.09/2.92 8.09/2.92 (28) 8.09/2.92 Obligation: 8.09/2.92 Pi DP problem: 8.09/2.92 The TRS P consists of the following rules: 8.09/2.92 8.09/2.92 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> SAFE_IN_G(Y) 8.09/2.92 SAFE_IN_G(.(X, Y)) -> U6_G(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.92 8.09/2.92 The TRS R consists of the following rules: 8.09/2.92 8.09/2.92 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.92 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.92 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.92 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.92 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.92 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.92 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.93 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.93 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.93 safe_in_g([]) -> safe_out_g([]) 8.09/2.93 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.93 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.93 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.93 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.93 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.93 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.93 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.93 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.93 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.93 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.93 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.93 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.93 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.93 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.93 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.93 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.93 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.93 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.93 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 queens_in_a(x1) = queens_in_a 8.09/2.93 8.09/2.93 U1_a(x1, x2) = U1_a(x2) 8.09/2.93 8.09/2.93 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.93 8.09/2.93 [] = [] 8.09/2.93 8.09/2.93 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.93 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.93 8.09/2.93 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.93 8.09/2.93 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.93 8.09/2.93 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.93 8.09/2.93 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.93 8.09/2.93 s(x1) = s(x1) 8.09/2.93 8.09/2.93 0 = 0 8.09/2.93 8.09/2.93 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.93 8.09/2.93 safe_in_g(x1) = safe_in_g(x1) 8.09/2.93 8.09/2.93 safe_out_g(x1) = safe_out_g 8.09/2.93 8.09/2.93 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.93 8.09/2.93 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.93 8.09/2.93 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.93 8.09/2.93 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.93 8.09/2.93 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.93 8.09/2.93 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.93 8.09/2.93 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.93 8.09/2.93 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.93 8.09/2.93 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.93 8.09/2.93 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.93 8.09/2.93 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.93 8.09/2.93 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.93 8.09/2.93 queens_out_a(x1) = queens_out_a(x1) 8.09/2.93 8.09/2.93 SAFE_IN_G(x1) = SAFE_IN_G(x1) 8.09/2.93 8.09/2.93 U6_G(x1, x2, x3) = U6_G(x2, x3) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (29) UsableRulesProof (EQUIVALENT) 8.09/2.93 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (30) 8.09/2.93 Obligation: 8.09/2.93 Pi DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 U6_G(X, Y, noattack_out_ggg(X, Y, s(0))) -> SAFE_IN_G(Y) 8.09/2.93 SAFE_IN_G(.(X, Y)) -> U6_G(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.93 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.93 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.93 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.93 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.93 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.93 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.93 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.93 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.93 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.93 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.93 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.93 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.93 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.93 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.93 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 [] = [] 8.09/2.93 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 s(x1) = s(x1) 8.09/2.93 8.09/2.93 0 = 0 8.09/2.93 8.09/2.93 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.93 8.09/2.93 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.93 8.09/2.93 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.93 8.09/2.93 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.93 8.09/2.93 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.93 8.09/2.93 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.93 8.09/2.93 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.93 8.09/2.93 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.93 8.09/2.93 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.93 8.09/2.93 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.93 8.09/2.93 SAFE_IN_G(x1) = SAFE_IN_G(x1) 8.09/2.93 8.09/2.93 U6_G(x1, x2, x3) = U6_G(x2, x3) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (31) PiDPToQDPProof (SOUND) 8.09/2.93 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (32) 8.09/2.93 Obligation: 8.09/2.93 Q DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 U6_G(Y, noattack_out_ggg) -> SAFE_IN_G(Y) 8.09/2.93 SAFE_IN_G(.(X, Y)) -> U6_G(Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 noattack_in_ggg(X, [], N) -> noattack_out_ggg 8.09/2.93 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.93 U8_ggg(X, F, T, N, notEq_out_gg) -> U9_ggg(X, F, T, N, add_in_gga(F, N)) 8.09/2.93 notEq_in_gg(0, s(X)) -> notEq_out_gg 8.09/2.93 notEq_in_gg(s(X), 0) -> notEq_out_gg 8.09/2.93 notEq_in_gg(s(X), s(Y)) -> U15_gg(notEq_in_gg(X, Y)) 8.09/2.93 U9_ggg(X, F, T, N, add_out_gga(FplusN)) -> U10_ggg(X, F, T, N, notEq_in_gg(X, FplusN)) 8.09/2.93 U15_gg(notEq_out_gg) -> notEq_out_gg 8.09/2.93 add_in_gga(0, X) -> add_out_gga(X) 8.09/2.93 add_in_gga(s(X), Y) -> U14_gga(add_in_gga(X, Y)) 8.09/2.93 U10_ggg(X, F, T, N, notEq_out_gg) -> U11_ggg(X, F, T, N, add_in_gga(X, N)) 8.09/2.93 U14_gga(add_out_gga(Z)) -> add_out_gga(s(Z)) 8.09/2.93 U11_ggg(X, F, T, N, add_out_gga(XplusN)) -> U12_ggg(X, T, N, notEq_in_gg(F, XplusN)) 8.09/2.93 U12_ggg(X, T, N, notEq_out_gg) -> U13_ggg(noattack_in_ggg(X, T, s(N))) 8.09/2.93 U13_ggg(noattack_out_ggg) -> noattack_out_ggg 8.09/2.93 8.09/2.93 The set Q consists of the following terms: 8.09/2.93 8.09/2.93 noattack_in_ggg(x0, x1, x2) 8.09/2.93 U8_ggg(x0, x1, x2, x3, x4) 8.09/2.93 notEq_in_gg(x0, x1) 8.09/2.93 U9_ggg(x0, x1, x2, x3, x4) 8.09/2.93 U15_gg(x0) 8.09/2.93 add_in_gga(x0, x1) 8.09/2.93 U10_ggg(x0, x1, x2, x3, x4) 8.09/2.93 U14_gga(x0) 8.09/2.93 U11_ggg(x0, x1, x2, x3, x4) 8.09/2.93 U12_ggg(x0, x1, x2, x3) 8.09/2.93 U13_ggg(x0) 8.09/2.93 8.09/2.93 We have to consider all (P,Q,R)-chains. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (33) QDPSizeChangeProof (EQUIVALENT) 8.09/2.93 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.09/2.93 8.09/2.93 From the DPs we obtained the following set of size-change graphs: 8.09/2.93 *SAFE_IN_G(.(X, Y)) -> U6_G(Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 The graph contains the following edges 1 > 1 8.09/2.93 8.09/2.93 8.09/2.93 *U6_G(Y, noattack_out_ggg) -> SAFE_IN_G(Y) 8.09/2.93 The graph contains the following edges 1 >= 1 8.09/2.93 8.09/2.93 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (34) 8.09/2.93 YES 8.09/2.93 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (35) 8.09/2.93 Obligation: 8.09/2.93 Pi DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> DELETE_IN_AGA(X, T, R) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.93 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.93 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.93 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.93 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.93 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.93 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.93 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.93 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.93 safe_in_g([]) -> safe_out_g([]) 8.09/2.93 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.93 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.93 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.93 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.93 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.93 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.93 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.93 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.93 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.93 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.93 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.93 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.93 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.93 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.93 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.93 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.93 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.93 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.93 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 queens_in_a(x1) = queens_in_a 8.09/2.93 8.09/2.93 U1_a(x1, x2) = U1_a(x2) 8.09/2.93 8.09/2.93 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.93 8.09/2.93 [] = [] 8.09/2.93 8.09/2.93 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.93 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.93 8.09/2.93 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.93 8.09/2.93 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.93 8.09/2.93 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.93 8.09/2.93 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.93 8.09/2.93 s(x1) = s(x1) 8.09/2.93 8.09/2.93 0 = 0 8.09/2.93 8.09/2.93 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.93 8.09/2.93 safe_in_g(x1) = safe_in_g(x1) 8.09/2.93 8.09/2.93 safe_out_g(x1) = safe_out_g 8.09/2.93 8.09/2.93 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.93 8.09/2.93 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.93 8.09/2.93 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.93 8.09/2.93 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.93 8.09/2.93 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.93 8.09/2.93 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.93 8.09/2.93 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.93 8.09/2.93 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.93 8.09/2.93 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.93 8.09/2.93 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.93 8.09/2.93 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.93 8.09/2.93 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.93 8.09/2.93 queens_out_a(x1) = queens_out_a(x1) 8.09/2.93 8.09/2.93 DELETE_IN_AGA(x1, x2, x3) = DELETE_IN_AGA(x2) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (36) UsableRulesProof (EQUIVALENT) 8.09/2.93 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (37) 8.09/2.93 Obligation: 8.09/2.93 Pi DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 DELETE_IN_AGA(X, .(F, T), .(F, R)) -> DELETE_IN_AGA(X, T, R) 8.09/2.93 8.09/2.93 R is empty. 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 DELETE_IN_AGA(x1, x2, x3) = DELETE_IN_AGA(x2) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (38) PiDPToQDPProof (SOUND) 8.09/2.93 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (39) 8.09/2.93 Obligation: 8.09/2.93 Q DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 DELETE_IN_AGA(.(F, T)) -> DELETE_IN_AGA(T) 8.09/2.93 8.09/2.93 R is empty. 8.09/2.93 Q is empty. 8.09/2.93 We have to consider all (P,Q,R)-chains. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (40) QDPSizeChangeProof (EQUIVALENT) 8.09/2.93 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.09/2.93 8.09/2.93 From the DPs we obtained the following set of size-change graphs: 8.09/2.93 *DELETE_IN_AGA(.(F, T)) -> DELETE_IN_AGA(T) 8.09/2.93 The graph contains the following edges 1 > 1 8.09/2.93 8.09/2.93 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (41) 8.09/2.93 YES 8.09/2.93 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (42) 8.09/2.93 Obligation: 8.09/2.93 Pi DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> PERM_IN_GA(Rest, Res) 8.09/2.93 PERM_IN_GA(.(X, Y), .(V, Res)) -> U3_GA(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 queens_in_a(Y) -> U1_a(Y, perm_in_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) 8.09/2.93 perm_in_ga([], []) -> perm_out_ga([], []) 8.09/2.93 perm_in_ga(.(X, Y), .(V, Res)) -> U3_ga(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.93 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.93 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.93 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.93 U3_ga(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> U4_ga(X, Y, V, Res, perm_in_ga(Rest, Res)) 8.09/2.93 U4_ga(X, Y, V, Res, perm_out_ga(Rest, Res)) -> perm_out_ga(.(X, Y), .(V, Res)) 8.09/2.93 U1_a(Y, perm_out_ga(.(s(0), .(s(s(0)), .(s(s(s(0))), .(s(s(s(s(0)))), .(s(s(s(s(s(0))))), .(s(s(s(s(s(s(0)))))), .(s(s(s(s(s(s(s(0))))))), .(s(s(s(s(s(s(s(s(0)))))))), [])))))))), Y)) -> U2_a(Y, safe_in_g(Y)) 8.09/2.93 safe_in_g([]) -> safe_out_g([]) 8.09/2.93 safe_in_g(.(X, Y)) -> U6_g(X, Y, noattack_in_ggg(X, Y, s(0))) 8.09/2.93 noattack_in_ggg(X, [], N) -> noattack_out_ggg(X, [], N) 8.09/2.93 noattack_in_ggg(X, .(F, T), N) -> U8_ggg(X, F, T, N, notEq_in_gg(X, F)) 8.09/2.93 notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) 8.09/2.93 notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) 8.09/2.93 notEq_in_gg(s(X), s(Y)) -> U15_gg(X, Y, notEq_in_gg(X, Y)) 8.09/2.93 U15_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) 8.09/2.93 U8_ggg(X, F, T, N, notEq_out_gg(X, F)) -> U9_ggg(X, F, T, N, add_in_gga(F, N, FplusN)) 8.09/2.93 add_in_gga(0, X, X) -> add_out_gga(0, X, X) 8.09/2.93 add_in_gga(s(X), Y, s(Z)) -> U14_gga(X, Y, Z, add_in_gga(X, Y, Z)) 8.09/2.93 U14_gga(X, Y, Z, add_out_gga(X, Y, Z)) -> add_out_gga(s(X), Y, s(Z)) 8.09/2.93 U9_ggg(X, F, T, N, add_out_gga(F, N, FplusN)) -> U10_ggg(X, F, T, N, FplusN, notEq_in_gg(X, FplusN)) 8.09/2.93 U10_ggg(X, F, T, N, FplusN, notEq_out_gg(X, FplusN)) -> U11_ggg(X, F, T, N, FplusN, add_in_gga(X, N, XplusN)) 8.09/2.93 U11_ggg(X, F, T, N, FplusN, add_out_gga(X, N, XplusN)) -> U12_ggg(X, F, T, N, notEq_in_gg(F, XplusN)) 8.09/2.93 U12_ggg(X, F, T, N, notEq_out_gg(F, XplusN)) -> U13_ggg(X, F, T, N, noattack_in_ggg(X, T, s(N))) 8.09/2.93 U13_ggg(X, F, T, N, noattack_out_ggg(X, T, s(N))) -> noattack_out_ggg(X, .(F, T), N) 8.09/2.93 U6_g(X, Y, noattack_out_ggg(X, Y, s(0))) -> U7_g(X, Y, safe_in_g(Y)) 8.09/2.93 U7_g(X, Y, safe_out_g(Y)) -> safe_out_g(.(X, Y)) 8.09/2.93 U2_a(Y, safe_out_g(Y)) -> queens_out_a(Y) 8.09/2.93 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 queens_in_a(x1) = queens_in_a 8.09/2.93 8.09/2.93 U1_a(x1, x2) = U1_a(x2) 8.09/2.93 8.09/2.93 perm_in_ga(x1, x2) = perm_in_ga(x1) 8.09/2.93 8.09/2.93 [] = [] 8.09/2.93 8.09/2.93 perm_out_ga(x1, x2) = perm_out_ga(x2) 8.09/2.93 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 U3_ga(x1, x2, x3, x4, x5) = U3_ga(x5) 8.09/2.93 8.09/2.93 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.93 8.09/2.93 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.93 8.09/2.93 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.93 8.09/2.93 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x3, x5) 8.09/2.93 8.09/2.93 s(x1) = s(x1) 8.09/2.93 8.09/2.93 0 = 0 8.09/2.93 8.09/2.93 U2_a(x1, x2) = U2_a(x1, x2) 8.09/2.93 8.09/2.93 safe_in_g(x1) = safe_in_g(x1) 8.09/2.93 8.09/2.93 safe_out_g(x1) = safe_out_g 8.09/2.93 8.09/2.93 U6_g(x1, x2, x3) = U6_g(x2, x3) 8.09/2.93 8.09/2.93 noattack_in_ggg(x1, x2, x3) = noattack_in_ggg(x1, x2, x3) 8.09/2.93 8.09/2.93 noattack_out_ggg(x1, x2, x3) = noattack_out_ggg 8.09/2.93 8.09/2.93 U8_ggg(x1, x2, x3, x4, x5) = U8_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) 8.09/2.93 8.09/2.93 notEq_out_gg(x1, x2) = notEq_out_gg 8.09/2.93 8.09/2.93 U15_gg(x1, x2, x3) = U15_gg(x3) 8.09/2.93 8.09/2.93 U9_ggg(x1, x2, x3, x4, x5) = U9_ggg(x1, x2, x3, x4, x5) 8.09/2.93 8.09/2.93 add_in_gga(x1, x2, x3) = add_in_gga(x1, x2) 8.09/2.93 8.09/2.93 add_out_gga(x1, x2, x3) = add_out_gga(x3) 8.09/2.93 8.09/2.93 U14_gga(x1, x2, x3, x4) = U14_gga(x4) 8.09/2.93 8.09/2.93 U10_ggg(x1, x2, x3, x4, x5, x6) = U10_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U11_ggg(x1, x2, x3, x4, x5, x6) = U11_ggg(x1, x2, x3, x4, x6) 8.09/2.93 8.09/2.93 U12_ggg(x1, x2, x3, x4, x5) = U12_ggg(x1, x3, x4, x5) 8.09/2.93 8.09/2.93 U13_ggg(x1, x2, x3, x4, x5) = U13_ggg(x5) 8.09/2.93 8.09/2.93 U7_g(x1, x2, x3) = U7_g(x3) 8.09/2.93 8.09/2.93 queens_out_a(x1) = queens_out_a(x1) 8.09/2.93 8.09/2.93 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 8.09/2.93 8.09/2.93 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (43) UsableRulesProof (EQUIVALENT) 8.09/2.93 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (44) 8.09/2.93 Obligation: 8.09/2.93 Pi DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 U3_GA(X, Y, V, Res, delete_out_aga(V, .(X, Y), Rest)) -> PERM_IN_GA(Rest, Res) 8.09/2.93 PERM_IN_GA(.(X, Y), .(V, Res)) -> U3_GA(X, Y, V, Res, delete_in_aga(V, .(X, Y), Rest)) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 delete_in_aga(X, .(X, Y), Y) -> delete_out_aga(X, .(X, Y), Y) 8.09/2.93 delete_in_aga(X, .(F, T), .(F, R)) -> U5_aga(X, F, T, R, delete_in_aga(X, T, R)) 8.09/2.93 U5_aga(X, F, T, R, delete_out_aga(X, T, R)) -> delete_out_aga(X, .(F, T), .(F, R)) 8.09/2.93 8.09/2.93 The argument filtering Pi contains the following mapping: 8.09/2.93 .(x1, x2) = .(x1, x2) 8.09/2.93 8.09/2.93 delete_in_aga(x1, x2, x3) = delete_in_aga(x2) 8.09/2.93 8.09/2.93 delete_out_aga(x1, x2, x3) = delete_out_aga(x1, x3) 8.09/2.93 8.09/2.93 U5_aga(x1, x2, x3, x4, x5) = U5_aga(x2, x5) 8.09/2.93 8.09/2.93 PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) 8.09/2.93 8.09/2.93 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x5) 8.09/2.93 8.09/2.93 8.09/2.93 We have to consider all (P,R,Pi)-chains 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (45) PiDPToQDPProof (SOUND) 8.09/2.93 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (46) 8.09/2.93 Obligation: 8.09/2.93 Q DP problem: 8.09/2.93 The TRS P consists of the following rules: 8.09/2.93 8.09/2.93 U3_GA(delete_out_aga(V, Rest)) -> PERM_IN_GA(Rest) 8.09/2.93 PERM_IN_GA(.(X, Y)) -> U3_GA(delete_in_aga(.(X, Y))) 8.09/2.93 8.09/2.93 The TRS R consists of the following rules: 8.09/2.93 8.09/2.93 delete_in_aga(.(X, Y)) -> delete_out_aga(X, Y) 8.09/2.93 delete_in_aga(.(F, T)) -> U5_aga(F, delete_in_aga(T)) 8.09/2.93 U5_aga(F, delete_out_aga(X, R)) -> delete_out_aga(X, .(F, R)) 8.09/2.93 8.09/2.93 The set Q consists of the following terms: 8.09/2.93 8.09/2.93 delete_in_aga(x0) 8.09/2.93 U5_aga(x0, x1) 8.09/2.93 8.09/2.93 We have to consider all (P,Q,R)-chains. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (47) MRRProof (EQUIVALENT) 8.09/2.93 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. 8.09/2.93 8.09/2.93 Strictly oriented dependency pairs: 8.09/2.93 8.09/2.93 U3_GA(delete_out_aga(V, Rest)) -> PERM_IN_GA(Rest) 8.09/2.93 PERM_IN_GA(.(X, Y)) -> U3_GA(delete_in_aga(.(X, Y))) 8.09/2.93 8.09/2.93 Strictly oriented rules of the TRS R: 8.09/2.93 8.09/2.93 delete_in_aga(.(X, Y)) -> delete_out_aga(X, Y) 8.09/2.93 delete_in_aga(.(F, T)) -> U5_aga(F, delete_in_aga(T)) 8.09/2.93 U5_aga(F, delete_out_aga(X, R)) -> delete_out_aga(X, .(F, R)) 8.09/2.93 8.09/2.93 Used ordering: Knuth-Bendix order [KBO] with precedence:._2 > delete_in_aga_1 > U5_aga_2 > U3_GA_1 > PERM_IN_GA_1 > delete_out_aga_2 8.09/2.93 8.09/2.93 and weight map: 8.09/2.93 8.09/2.93 delete_in_aga_1=1 8.09/2.93 U3_GA_1=1 8.09/2.93 PERM_IN_GA_1=3 8.09/2.93 ._2=0 8.09/2.93 delete_out_aga_2=1 8.09/2.93 U5_aga_2=0 8.09/2.93 8.09/2.93 The variable weight is 1 8.09/2.93 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (48) 8.09/2.93 Obligation: 8.09/2.93 Q DP problem: 8.09/2.93 P is empty. 8.09/2.93 R is empty. 8.09/2.93 The set Q consists of the following terms: 8.09/2.93 8.09/2.93 delete_in_aga(x0) 8.09/2.93 U5_aga(x0, x1) 8.09/2.93 8.09/2.93 We have to consider all (P,Q,R)-chains. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (49) PisEmptyProof (EQUIVALENT) 8.09/2.93 The TRS P is empty. Hence, there is no (P,Q,R) chain. 8.09/2.93 ---------------------------------------- 8.09/2.93 8.09/2.93 (50) 8.09/2.93 YES 8.40/3.04 EOF