/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern tautology(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 36 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 21 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 34 ms] (18) QDP (19) QDPQMonotonicMRRProof [EQUIVALENT, 332 ms] (20) QDP (21) QDPQMonotonicMRRProof [EQUIVALENT, 319 ms] (22) QDP (23) QDPQMonotonicMRRProof [EQUIVALENT, 167 ms] (24) QDP (25) QDPQMonotonicMRRProof [EQUIVALENT, 108 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) TRUE ---------------------------------------- (0) Obligation: Clauses: tautology(F) :- reduce(sequent([], .(F, [])), sequent([], [])). reduce(sequent(.(if(A, B), Fs), Gs), NF) :- reduce(sequent(.(+(-(B), A), Fs), Gs), NF). reduce(sequent(.(iff(A, B), Fs), Gs), NF) :- reduce(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF). reduce(sequent(.(*(F1, F2), Fs), Gs), NF) :- reduce(sequent(.(F1, .(F2, Fs)), Gs), NF). reduce(sequent(.(+(F1, F2), Fs), Gs), NF) :- ','(reduce(sequent(.(F1, Fs), Gs), NF), reduce(sequent(.(F2, Fs), Gs), NF)). reduce(sequent(.(-(F1), Fs), Gs), NF) :- reduce(sequent(Fs, .(F1, Gs)), NF). reduce(sequent(Fs, .(if(A, B), Gs)), NF) :- reduce(sequent(Fs, .(+(-(B), A), Gs)), NF). reduce(sequent(Fs, .(iff(A, B), Gs)), NF) :- reduce(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF). reduce(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) :- reduce(sequent(Fs, Gs), sequent(.(p(V), Left), Right)). reduce(sequent(Fs, .(+(G1, G2), Gs)), NF) :- reduce(sequent(Fs, .(G1, .(G2, Gs))), NF). reduce(sequent(Fs, .(*(G1, G2), Gs)), NF) :- ','(reduce(sequent(Fs, .(G1, Gs)), NF), reduce(sequent(Fs, .(G2, Gs)), NF)). reduce(sequent(Fs, .(-(G1), Gs)), NF) :- reduce(sequent(.(G1, Fs), Gs), NF). reduce(sequent([], .(p(V), Gs)), sequent(Left, Right)) :- reduce(sequent([], Gs), sequent(Left, .(p(V), Right))). reduce(sequent([], []), sequent(F1, F2)) :- intersect(F1, F2). intersect(.(X, X1), .(X, X2)). intersect(Xs, .(X3, Ys)) :- intersect(Xs, Ys). intersect(.(X4, Xs), Ys) :- intersect(Xs, Ys). yes1 :- tautology(+(-(p(1)), p(1))). yes2 :- tautology(*(+(-(p(1)), p(1)), +(p(1), -(p(1))))). yes3 :- tautology(*(+(-(-(-(p(1)))), p(1)), +(-(-(p(1))), -(p(1))))). yes4 :- tautology(-(-(','(p(1), *), p(1)))). no1 :- tautology(-(','(p(1), *), p(1))). no2 :- tautology(+(-(+(p(1), -(p(1)))), p(2))). no3 :- tautology(*(+(-(+(-(p(1)), +(-(p(2)), p(3)))), +(-(+(p(1), p(2))), p(3))), +(-(p(1)), +(+(-(p(2)), p(3)), -(+(-(+(p(1), p(2))), p(3))))))). no4 :- tautology(+(-(+(*(p(1), *(p(2), p(3))), -(','(-(p(1)), *), -(','(p(2), *), p(3))))), *(+(-(p(1)), *(+(-(p(2)), p(3)), +(p(2), -(p(3))))), +(p(1), -(*(+(-(p(2)), p(3)), +(p(2), -(p(3))))))))). Query: tautology(g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: tautology_in_1: (b) reduce_in_2: (b,b) intersect_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: TAUTOLOGY_IN_G(F) -> U1_G(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) TAUTOLOGY_IN_G(F) -> REDUCE_IN_GG(sequent([], .(F, [])), sequent([], [])) REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> U2_GG(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_GG(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> U7_GG(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_GG(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_GG(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_GG(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> U14_GG(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_GG(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) REDUCE_IN_GG(sequent([], []), sequent(F1, F2)) -> U16_GG(F1, F2, intersect_in_gg(F1, F2)) REDUCE_IN_GG(sequent([], []), sequent(F1, F2)) -> INTERSECT_IN_GG(F1, F2) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> U17_GG(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) INTERSECT_IN_GG(.(X4, Xs), Ys) -> U18_GG(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g TAUTOLOGY_IN_G(x1) = TAUTOLOGY_IN_G(x1) U1_G(x1, x2) = U1_G(x2) REDUCE_IN_GG(x1, x2) = REDUCE_IN_GG(x1, x2) U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x6) U3_GG(x1, x2, x3, x4, x5, x6) = U3_GG(x6) U4_GG(x1, x2, x3, x4, x5, x6) = U4_GG(x6) U5_GG(x1, x2, x3, x4, x5, x6) = U5_GG(x2, x3, x4, x5, x6) U7_GG(x1, x2, x3, x4, x5) = U7_GG(x5) U8_GG(x1, x2, x3, x4, x5, x6) = U8_GG(x6) U9_GG(x1, x2, x3, x4, x5, x6) = U9_GG(x6) U10_GG(x1, x2, x3, x4, x5, x6) = U10_GG(x6) U11_GG(x1, x2, x3, x4, x5, x6) = U11_GG(x6) U12_GG(x1, x2, x3, x4, x5, x6) = U12_GG(x1, x3, x4, x5, x6) U14_GG(x1, x2, x3, x4, x5) = U14_GG(x5) U15_GG(x1, x2, x3, x4, x5) = U15_GG(x5) U16_GG(x1, x2, x3) = U16_GG(x3) INTERSECT_IN_GG(x1, x2) = INTERSECT_IN_GG(x1, x2) U17_GG(x1, x2, x3, x4) = U17_GG(x4) U18_GG(x1, x2, x3, x4) = U18_GG(x4) U13_GG(x1, x2, x3, x4, x5, x6) = U13_GG(x6) U6_GG(x1, x2, x3, x4, x5, x6) = U6_GG(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: TAUTOLOGY_IN_G(F) -> U1_G(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) TAUTOLOGY_IN_G(F) -> REDUCE_IN_GG(sequent([], .(F, [])), sequent([], [])) REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> U2_GG(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_GG(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> U7_GG(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_GG(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_GG(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_GG(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> U14_GG(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_GG(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) REDUCE_IN_GG(sequent([], []), sequent(F1, F2)) -> U16_GG(F1, F2, intersect_in_gg(F1, F2)) REDUCE_IN_GG(sequent([], []), sequent(F1, F2)) -> INTERSECT_IN_GG(F1, F2) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> U17_GG(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) INTERSECT_IN_GG(.(X4, Xs), Ys) -> U18_GG(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g TAUTOLOGY_IN_G(x1) = TAUTOLOGY_IN_G(x1) U1_G(x1, x2) = U1_G(x2) REDUCE_IN_GG(x1, x2) = REDUCE_IN_GG(x1, x2) U2_GG(x1, x2, x3, x4, x5, x6) = U2_GG(x6) U3_GG(x1, x2, x3, x4, x5, x6) = U3_GG(x6) U4_GG(x1, x2, x3, x4, x5, x6) = U4_GG(x6) U5_GG(x1, x2, x3, x4, x5, x6) = U5_GG(x2, x3, x4, x5, x6) U7_GG(x1, x2, x3, x4, x5) = U7_GG(x5) U8_GG(x1, x2, x3, x4, x5, x6) = U8_GG(x6) U9_GG(x1, x2, x3, x4, x5, x6) = U9_GG(x6) U10_GG(x1, x2, x3, x4, x5, x6) = U10_GG(x6) U11_GG(x1, x2, x3, x4, x5, x6) = U11_GG(x6) U12_GG(x1, x2, x3, x4, x5, x6) = U12_GG(x1, x3, x4, x5, x6) U14_GG(x1, x2, x3, x4, x5) = U14_GG(x5) U15_GG(x1, x2, x3, x4, x5) = U15_GG(x5) U16_GG(x1, x2, x3) = U16_GG(x3) INTERSECT_IN_GG(x1, x2) = INTERSECT_IN_GG(x1, x2) U17_GG(x1, x2, x3, x4) = U17_GG(x4) U18_GG(x1, x2, x3, x4) = U18_GG(x4) U13_GG(x1, x2, x3, x4, x5, x6) = U13_GG(x6) U6_GG(x1, x2, x3, x4, x5, x6) = U6_GG(x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 18 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g INTERSECT_IN_GG(x1, x2) = INTERSECT_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *INTERSECT_IN_GG(.(X4, Xs), Ys) -> INTERSECT_IN_GG(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 *INTERSECT_IN_GG(Xs, .(X3, Ys)) -> INTERSECT_IN_GG(Xs, Ys) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) The TRS R consists of the following rules: tautology_in_g(F) -> U1_g(F, reduce_in_gg(sequent([], .(F, [])), sequent([], []))) reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U1_g(F, reduce_out_gg(sequent([], .(F, [])), sequent([], []))) -> tautology_out_g(F) The argument filtering Pi contains the following mapping: tautology_in_g(x1) = tautology_in_g(x1) U1_g(x1, x2) = U1_g(x2) reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) tautology_out_g(x1) = tautology_out_g REDUCE_IN_GG(x1, x2) = REDUCE_IN_GG(x1, x2) U5_GG(x1, x2, x3, x4, x5, x6) = U5_GG(x2, x3, x4, x5, x6) U12_GG(x1, x2, x3, x4, x5, x6) = U12_GG(x1, x3, x4, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) U5_GG(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(A, B, Fs, Gs, NF, reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(F1, Fs, Gs, NF, reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(Fs, A, B, Gs, NF, reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(V, Fs, Gs, Left, Right, reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(Fs, G1, Gs, NF, reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(V, Gs, Left, Right, reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(if(A, B), Fs), Gs), NF) U3_gg(A, B, Fs, Gs, NF, reduce_out_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) -> reduce_out_gg(sequent(.(iff(A, B), Fs), Gs), NF) U4_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) -> reduce_out_gg(sequent(.(*(F1, F2), Fs), Gs), NF) U5_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F1, Fs), Gs), NF)) -> U6_gg(F1, F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(F1, Fs, Gs, NF, reduce_out_gg(sequent(Fs, .(F1, Gs)), NF)) -> reduce_out_gg(sequent(.(-(F1), Fs), Gs), NF) U8_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(if(A, B), Gs)), NF) U9_gg(Fs, A, B, Gs, NF, reduce_out_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(iff(A, B), Gs)), NF) U10_gg(V, Fs, Gs, Left, Right, reduce_out_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) -> reduce_out_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) U11_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) -> reduce_out_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) U12_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G1, Gs)), NF)) -> U13_gg(Fs, G1, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(Fs, G1, Gs, NF, reduce_out_gg(sequent(.(G1, Fs), Gs), NF)) -> reduce_out_gg(sequent(Fs, .(-(G1), Gs)), NF) U15_gg(V, Gs, Left, Right, reduce_out_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) -> reduce_out_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) U6_gg(F1, F2, Fs, Gs, NF, reduce_out_gg(sequent(.(F2, Fs), Gs), NF)) -> reduce_out_gg(sequent(.(+(F1, F2), Fs), Gs), NF) reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(F1, F2, intersect_in_gg(F1, F2)) U13_gg(Fs, G1, G2, Gs, NF, reduce_out_gg(sequent(Fs, .(G2, Gs)), NF)) -> reduce_out_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) U16_gg(F1, F2, intersect_out_gg(F1, F2)) -> reduce_out_gg(sequent([], []), sequent(F1, F2)) intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg(.(X, X1), .(X, X2)) intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(Xs, X3, Ys, intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(X4, Xs, Ys, intersect_in_gg(Xs, Ys)) U17_gg(Xs, X3, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(Xs, .(X3, Ys)) U18_gg(X4, Xs, Ys, intersect_out_gg(Xs, Ys)) -> intersect_out_gg(.(X4, Xs), Ys) The argument filtering Pi contains the following mapping: reduce_in_gg(x1, x2) = reduce_in_gg(x1, x2) sequent(x1, x2) = sequent(x1, x2) .(x1, x2) = .(x1, x2) if(x1, x2) = if(x1, x2) U2_gg(x1, x2, x3, x4, x5, x6) = U2_gg(x6) iff(x1, x2) = iff(x1, x2) U3_gg(x1, x2, x3, x4, x5, x6) = U3_gg(x6) *(x1, x2) = *(x1, x2) U4_gg(x1, x2, x3, x4, x5, x6) = U4_gg(x6) +(x1, x2) = +(x1, x2) U5_gg(x1, x2, x3, x4, x5, x6) = U5_gg(x2, x3, x4, x5, x6) -(x1) = -(x1) U7_gg(x1, x2, x3, x4, x5) = U7_gg(x5) U8_gg(x1, x2, x3, x4, x5, x6) = U8_gg(x6) U9_gg(x1, x2, x3, x4, x5, x6) = U9_gg(x6) p(x1) = p(x1) U10_gg(x1, x2, x3, x4, x5, x6) = U10_gg(x6) U11_gg(x1, x2, x3, x4, x5, x6) = U11_gg(x6) U12_gg(x1, x2, x3, x4, x5, x6) = U12_gg(x1, x3, x4, x5, x6) U14_gg(x1, x2, x3, x4, x5) = U14_gg(x5) [] = [] U15_gg(x1, x2, x3, x4, x5) = U15_gg(x5) U16_gg(x1, x2, x3) = U16_gg(x3) intersect_in_gg(x1, x2) = intersect_in_gg(x1, x2) intersect_out_gg(x1, x2) = intersect_out_gg U17_gg(x1, x2, x3, x4) = U17_gg(x4) U18_gg(x1, x2, x3, x4) = U18_gg(x4) reduce_out_gg(x1, x2) = reduce_out_gg U13_gg(x1, x2, x3, x4, x5, x6) = U13_gg(x6) U6_gg(x1, x2, x3, x4, x5, x6) = U6_gg(x6) REDUCE_IN_GG(x1, x2) = REDUCE_IN_GG(x1, x2) U5_GG(x1, x2, x3, x4, x5, x6) = U5_GG(x2, x3, x4, x5, x6) U12_GG(x1, x2, x3, x4, x5, x6) = U12_GG(x1, x3, x4, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) U5_GG(F2, Fs, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G2, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(reduce_out_gg) -> reduce_out_gg U3_gg(reduce_out_gg) -> reduce_out_gg U4_gg(reduce_out_gg) -> reduce_out_gg U5_gg(F2, Fs, Gs, NF, reduce_out_gg) -> U6_gg(reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(reduce_out_gg) -> reduce_out_gg U8_gg(reduce_out_gg) -> reduce_out_gg U9_gg(reduce_out_gg) -> reduce_out_gg U10_gg(reduce_out_gg) -> reduce_out_gg U11_gg(reduce_out_gg) -> reduce_out_gg U12_gg(Fs, G2, Gs, NF, reduce_out_gg) -> U13_gg(reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(reduce_out_gg) -> reduce_out_gg U15_gg(reduce_out_gg) -> reduce_out_gg U6_gg(reduce_out_gg) -> reduce_out_gg reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(intersect_in_gg(F1, F2)) U13_gg(reduce_out_gg) -> reduce_out_gg U16_gg(intersect_out_gg) -> reduce_out_gg intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(intersect_in_gg(Xs, Ys)) U17_gg(intersect_out_gg) -> intersect_out_gg U18_gg(intersect_out_gg) -> intersect_out_gg The set Q consists of the following terms: reduce_in_gg(x0, x1) U2_gg(x0) U3_gg(x0) U4_gg(x0) U5_gg(x0, x1, x2, x3, x4) U7_gg(x0) U8_gg(x0) U9_gg(x0) U10_gg(x0) U11_gg(x0) U12_gg(x0, x1, x2, x3, x4) U14_gg(x0) U15_gg(x0) U6_gg(x0) U13_gg(x0) U16_gg(x0) intersect_in_gg(x0, x1) U17_gg(x0) U18_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: REDUCE_IN_GG(sequent(.(if(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(+(-(B), A), Fs), Gs), NF) REDUCE_IN_GG(sequent(Fs, .(if(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(+(-(B), A), Gs)), NF) REDUCE_IN_GG(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE_IN_GG(sequent(Fs, Gs), sequent(.(p(V), Left), Right)) REDUCE_IN_GG(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> REDUCE_IN_GG(sequent([], Gs), sequent(Left, .(p(V), Right))) Used ordering: Polynomial interpretation [POLO]: POL(*(x_1, x_2)) = x_1 + x_2 POL(+(x_1, x_2)) = x_1 + x_2 POL(-(x_1)) = x_1 POL(.(x_1, x_2)) = x_1 + x_2 POL(REDUCE_IN_GG(x_1, x_2)) = 2*x_1 POL(U10_gg(x_1)) = 0 POL(U11_gg(x_1)) = 0 POL(U12_GG(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U12_gg(x_1, x_2, x_3, x_4, x_5)) = 0 POL(U13_gg(x_1)) = 0 POL(U14_gg(x_1)) = 0 POL(U15_gg(x_1)) = 0 POL(U16_gg(x_1)) = 0 POL(U17_gg(x_1)) = 0 POL(U18_gg(x_1)) = 0 POL(U2_gg(x_1)) = 0 POL(U3_gg(x_1)) = 0 POL(U4_gg(x_1)) = 0 POL(U5_GG(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U5_gg(x_1, x_2, x_3, x_4, x_5)) = 0 POL(U6_gg(x_1)) = 0 POL(U7_gg(x_1)) = 0 POL(U8_gg(x_1)) = 0 POL(U9_gg(x_1)) = 0 POL([]) = 0 POL(if(x_1, x_2)) = 1 + x_1 + x_2 POL(iff(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(intersect_in_gg(x_1, x_2)) = 0 POL(intersect_out_gg) = 0 POL(p(x_1)) = 2 POL(reduce_in_gg(x_1, x_2)) = 0 POL(reduce_out_gg) = 0 POL(sequent(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) U5_GG(F2, Fs, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G2, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(reduce_out_gg) -> reduce_out_gg U3_gg(reduce_out_gg) -> reduce_out_gg U4_gg(reduce_out_gg) -> reduce_out_gg U5_gg(F2, Fs, Gs, NF, reduce_out_gg) -> U6_gg(reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(reduce_out_gg) -> reduce_out_gg U8_gg(reduce_out_gg) -> reduce_out_gg U9_gg(reduce_out_gg) -> reduce_out_gg U10_gg(reduce_out_gg) -> reduce_out_gg U11_gg(reduce_out_gg) -> reduce_out_gg U12_gg(Fs, G2, Gs, NF, reduce_out_gg) -> U13_gg(reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(reduce_out_gg) -> reduce_out_gg U15_gg(reduce_out_gg) -> reduce_out_gg U6_gg(reduce_out_gg) -> reduce_out_gg reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(intersect_in_gg(F1, F2)) U13_gg(reduce_out_gg) -> reduce_out_gg U16_gg(intersect_out_gg) -> reduce_out_gg intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(intersect_in_gg(Xs, Ys)) U17_gg(intersect_out_gg) -> intersect_out_gg U18_gg(intersect_out_gg) -> intersect_out_gg The set Q consists of the following terms: reduce_in_gg(x0, x1) U2_gg(x0) U3_gg(x0) U4_gg(x0) U5_gg(x0, x1, x2, x3, x4) U7_gg(x0) U8_gg(x0) U9_gg(x0) U10_gg(x0) U11_gg(x0) U12_gg(x0, x1, x2, x3, x4) U14_gg(x0) U15_gg(x0) U6_gg(x0) U13_gg(x0) U16_gg(x0) intersect_in_gg(x0, x1) U17_gg(x0) U18_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_GG(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) U5_GG(F2, Fs, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(.(F2, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(iff(A, B), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF) REDUCE_IN_GG(sequent(.(+(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, Fs), Gs), NF) REDUCE_IN_GG(sequent(.(-(F1), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(Fs, .(F1, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(iff(A, B), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(+(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, .(G2, Gs))), NF) REDUCE_IN_GG(sequent(Fs, .(-(G1), Gs)), NF) -> REDUCE_IN_GG(sequent(.(G1, Fs), Gs), NF) Used ordering: Polynomial interpretation [POLO]: POL(*(x_1, x_2)) = x_1 + x_2 POL(+(x_1, x_2)) = 2 + x_1 + x_2 POL(-(x_1)) = 1 + x_1 POL(.(x_1, x_2)) = x_1 + x_2 POL(REDUCE_IN_GG(x_1, x_2)) = 2*x_1 + x_2 POL(U10_gg(x_1)) = 0 POL(U11_gg(x_1)) = 0 POL(U12_GG(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + 2*x_3 + x_4 POL(U12_gg(x_1, x_2, x_3, x_4, x_5)) = 0 POL(U13_gg(x_1)) = 0 POL(U14_gg(x_1)) = 0 POL(U15_gg(x_1)) = 0 POL(U16_gg(x_1)) = 0 POL(U17_gg(x_1)) = 0 POL(U18_gg(x_1)) = 0 POL(U2_gg(x_1)) = 0 POL(U3_gg(x_1)) = 0 POL(U4_gg(x_1)) = 0 POL(U5_GG(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 + x_4 POL(U5_gg(x_1, x_2, x_3, x_4, x_5)) = 0 POL(U6_gg(x_1)) = 0 POL(U7_gg(x_1)) = 0 POL(U8_gg(x_1)) = 0 POL(U9_gg(x_1)) = 0 POL([]) = 0 POL(if(x_1, x_2)) = 0 POL(iff(x_1, x_2)) = 1 POL(intersect_in_gg(x_1, x_2)) = 0 POL(intersect_out_gg) = 0 POL(p(x_1)) = 0 POL(reduce_in_gg(x_1, x_2)) = 0 POL(reduce_out_gg) = 0 POL(sequent(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G2, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(reduce_out_gg) -> reduce_out_gg U3_gg(reduce_out_gg) -> reduce_out_gg U4_gg(reduce_out_gg) -> reduce_out_gg U5_gg(F2, Fs, Gs, NF, reduce_out_gg) -> U6_gg(reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(reduce_out_gg) -> reduce_out_gg U8_gg(reduce_out_gg) -> reduce_out_gg U9_gg(reduce_out_gg) -> reduce_out_gg U10_gg(reduce_out_gg) -> reduce_out_gg U11_gg(reduce_out_gg) -> reduce_out_gg U12_gg(Fs, G2, Gs, NF, reduce_out_gg) -> U13_gg(reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(reduce_out_gg) -> reduce_out_gg U15_gg(reduce_out_gg) -> reduce_out_gg U6_gg(reduce_out_gg) -> reduce_out_gg reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(intersect_in_gg(F1, F2)) U13_gg(reduce_out_gg) -> reduce_out_gg U16_gg(intersect_out_gg) -> reduce_out_gg intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(intersect_in_gg(Xs, Ys)) U17_gg(intersect_out_gg) -> intersect_out_gg U18_gg(intersect_out_gg) -> intersect_out_gg The set Q consists of the following terms: reduce_in_gg(x0, x1) U2_gg(x0) U3_gg(x0) U4_gg(x0) U5_gg(x0, x1, x2, x3, x4) U7_gg(x0) U8_gg(x0) U9_gg(x0) U10_gg(x0) U11_gg(x0) U12_gg(x0, x1, x2, x3, x4) U14_gg(x0) U15_gg(x0) U6_gg(x0) U13_gg(x0) U16_gg(x0) intersect_in_gg(x0, x1) U17_gg(x0) U18_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: REDUCE_IN_GG(sequent(.(*(F1, F2), Fs), Gs), NF) -> REDUCE_IN_GG(sequent(.(F1, .(F2, Fs)), Gs), NF) Used ordering: Polynomial interpretation [POLO]: POL(*(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(+(x_1, x_2)) = 1 POL(-(x_1)) = 2 + 2*x_1 POL(.(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(REDUCE_IN_GG(x_1, x_2)) = x_1 + 2*x_2 POL(U10_gg(x_1)) = 0 POL(U11_gg(x_1)) = 0 POL(U12_GG(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_4 POL(U12_gg(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_4 POL(U13_gg(x_1)) = 0 POL(U14_gg(x_1)) = 0 POL(U15_gg(x_1)) = 2 POL(U16_gg(x_1)) = 2 POL(U17_gg(x_1)) = 2 POL(U18_gg(x_1)) = 2 POL(U2_gg(x_1)) = 2 POL(U3_gg(x_1)) = 2 POL(U4_gg(x_1)) = 2 POL(U5_gg(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_4 POL(U6_gg(x_1)) = 2 POL(U7_gg(x_1)) = 0 POL(U8_gg(x_1)) = 0 POL(U9_gg(x_1)) = 0 POL([]) = 2 POL(if(x_1, x_2)) = 0 POL(iff(x_1, x_2)) = 1 POL(intersect_in_gg(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(intersect_out_gg) = 0 POL(p(x_1)) = 1 + x_1 POL(reduce_in_gg(x_1, x_2)) = x_1 + 2*x_2 POL(reduce_out_gg) = 0 POL(sequent(x_1, x_2)) = 2*x_1 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) U12_GG(Fs, G2, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(reduce_out_gg) -> reduce_out_gg U3_gg(reduce_out_gg) -> reduce_out_gg U4_gg(reduce_out_gg) -> reduce_out_gg U5_gg(F2, Fs, Gs, NF, reduce_out_gg) -> U6_gg(reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(reduce_out_gg) -> reduce_out_gg U8_gg(reduce_out_gg) -> reduce_out_gg U9_gg(reduce_out_gg) -> reduce_out_gg U10_gg(reduce_out_gg) -> reduce_out_gg U11_gg(reduce_out_gg) -> reduce_out_gg U12_gg(Fs, G2, Gs, NF, reduce_out_gg) -> U13_gg(reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(reduce_out_gg) -> reduce_out_gg U15_gg(reduce_out_gg) -> reduce_out_gg U6_gg(reduce_out_gg) -> reduce_out_gg reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(intersect_in_gg(F1, F2)) U13_gg(reduce_out_gg) -> reduce_out_gg U16_gg(intersect_out_gg) -> reduce_out_gg intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(intersect_in_gg(Xs, Ys)) U17_gg(intersect_out_gg) -> intersect_out_gg U18_gg(intersect_out_gg) -> intersect_out_gg The set Q consists of the following terms: reduce_in_gg(x0, x1) U2_gg(x0) U3_gg(x0) U4_gg(x0) U5_gg(x0, x1, x2, x3, x4) U7_gg(x0) U8_gg(x0) U9_gg(x0) U10_gg(x0) U11_gg(x0) U12_gg(x0, x1, x2, x3, x4) U14_gg(x0) U15_gg(x0) U6_gg(x0) U13_gg(x0) U16_gg(x0) intersect_in_gg(x0, x1) U17_gg(x0) U18_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: U12_GG(Fs, G2, Gs, NF, reduce_out_gg) -> REDUCE_IN_GG(sequent(Fs, .(G2, Gs)), NF) REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> REDUCE_IN_GG(sequent(Fs, .(G1, Gs)), NF) Used ordering: Polynomial interpretation [POLO]: POL(*(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(+(x_1, x_2)) = 0 POL(-(x_1)) = 0 POL(.(x_1, x_2)) = x_1 POL(REDUCE_IN_GG(x_1, x_2)) = x_1 + 2*x_2 POL(U10_gg(x_1)) = 2 POL(U11_gg(x_1)) = 2 POL(U12_GG(x_1, x_2, x_3, x_4, x_5)) = 2 + x_2 + 2*x_4 POL(U12_gg(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_4 POL(U13_gg(x_1)) = 2 POL(U14_gg(x_1)) = 2 POL(U15_gg(x_1)) = 2 POL(U16_gg(x_1)) = 2 POL(U17_gg(x_1)) = 0 POL(U18_gg(x_1)) = 0 POL(U2_gg(x_1)) = 2 POL(U3_gg(x_1)) = 2 POL(U4_gg(x_1)) = 2 POL(U5_gg(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_4 POL(U6_gg(x_1)) = 0 POL(U7_gg(x_1)) = 2 POL(U8_gg(x_1)) = 2 POL(U9_gg(x_1)) = 2 POL([]) = 0 POL(if(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(iff(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(intersect_in_gg(x_1, x_2)) = 2 POL(intersect_out_gg) = 0 POL(p(x_1)) = 0 POL(reduce_in_gg(x_1, x_2)) = 2 + 2*x_2 POL(reduce_out_gg) = 0 POL(sequent(x_1, x_2)) = x_2 ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: REDUCE_IN_GG(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_GG(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) The TRS R consists of the following rules: reduce_in_gg(sequent(.(if(A, B), Fs), Gs), NF) -> U2_gg(reduce_in_gg(sequent(.(+(-(B), A), Fs), Gs), NF)) reduce_in_gg(sequent(.(iff(A, B), Fs), Gs), NF) -> U3_gg(reduce_in_gg(sequent(.(*(if(A, B), if(B, A)), Fs), Gs), NF)) reduce_in_gg(sequent(.(*(F1, F2), Fs), Gs), NF) -> U4_gg(reduce_in_gg(sequent(.(F1, .(F2, Fs)), Gs), NF)) reduce_in_gg(sequent(.(+(F1, F2), Fs), Gs), NF) -> U5_gg(F2, Fs, Gs, NF, reduce_in_gg(sequent(.(F1, Fs), Gs), NF)) reduce_in_gg(sequent(.(-(F1), Fs), Gs), NF) -> U7_gg(reduce_in_gg(sequent(Fs, .(F1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(if(A, B), Gs)), NF) -> U8_gg(reduce_in_gg(sequent(Fs, .(+(-(B), A), Gs)), NF)) reduce_in_gg(sequent(Fs, .(iff(A, B), Gs)), NF) -> U9_gg(reduce_in_gg(sequent(Fs, .(*(if(A, B), if(B, A)), Gs)), NF)) reduce_in_gg(sequent(.(p(V), Fs), Gs), sequent(Left, Right)) -> U10_gg(reduce_in_gg(sequent(Fs, Gs), sequent(.(p(V), Left), Right))) reduce_in_gg(sequent(Fs, .(+(G1, G2), Gs)), NF) -> U11_gg(reduce_in_gg(sequent(Fs, .(G1, .(G2, Gs))), NF)) reduce_in_gg(sequent(Fs, .(*(G1, G2), Gs)), NF) -> U12_gg(Fs, G2, Gs, NF, reduce_in_gg(sequent(Fs, .(G1, Gs)), NF)) reduce_in_gg(sequent(Fs, .(-(G1), Gs)), NF) -> U14_gg(reduce_in_gg(sequent(.(G1, Fs), Gs), NF)) reduce_in_gg(sequent([], .(p(V), Gs)), sequent(Left, Right)) -> U15_gg(reduce_in_gg(sequent([], Gs), sequent(Left, .(p(V), Right)))) U2_gg(reduce_out_gg) -> reduce_out_gg U3_gg(reduce_out_gg) -> reduce_out_gg U4_gg(reduce_out_gg) -> reduce_out_gg U5_gg(F2, Fs, Gs, NF, reduce_out_gg) -> U6_gg(reduce_in_gg(sequent(.(F2, Fs), Gs), NF)) U7_gg(reduce_out_gg) -> reduce_out_gg U8_gg(reduce_out_gg) -> reduce_out_gg U9_gg(reduce_out_gg) -> reduce_out_gg U10_gg(reduce_out_gg) -> reduce_out_gg U11_gg(reduce_out_gg) -> reduce_out_gg U12_gg(Fs, G2, Gs, NF, reduce_out_gg) -> U13_gg(reduce_in_gg(sequent(Fs, .(G2, Gs)), NF)) U14_gg(reduce_out_gg) -> reduce_out_gg U15_gg(reduce_out_gg) -> reduce_out_gg U6_gg(reduce_out_gg) -> reduce_out_gg reduce_in_gg(sequent([], []), sequent(F1, F2)) -> U16_gg(intersect_in_gg(F1, F2)) U13_gg(reduce_out_gg) -> reduce_out_gg U16_gg(intersect_out_gg) -> reduce_out_gg intersect_in_gg(.(X, X1), .(X, X2)) -> intersect_out_gg intersect_in_gg(Xs, .(X3, Ys)) -> U17_gg(intersect_in_gg(Xs, Ys)) intersect_in_gg(.(X4, Xs), Ys) -> U18_gg(intersect_in_gg(Xs, Ys)) U17_gg(intersect_out_gg) -> intersect_out_gg U18_gg(intersect_out_gg) -> intersect_out_gg The set Q consists of the following terms: reduce_in_gg(x0, x1) U2_gg(x0) U3_gg(x0) U4_gg(x0) U5_gg(x0, x1, x2, x3, x4) U7_gg(x0) U8_gg(x0) U9_gg(x0) U10_gg(x0) U11_gg(x0) U12_gg(x0, x1, x2, x3, x4) U14_gg(x0) U15_gg(x0) U6_gg(x0) U13_gg(x0) U16_gg(x0) intersect_in_gg(x0, x1) U17_gg(x0) U18_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (28) TRUE