We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P-complete.

In this paper, we propose a mathematical model for one-dimensional finite linear cellular automata and show connections between our model and the classical one. We then demonstrate, through some examples, that our model is a useful tool for analyzing one-dimensional finite linear cellular automata. We also extend this model to the D-dimensional case and give an algebraic characterization for it.