  In this paper operator pencils $A(x,D,\lambda)$ are studied which act on a
manifold with boundary and satisfy the condition of $N$-ellipticity with
parameter, a generalization of the notion of ellipticity with parameter as
introduced by Agmon and Agranovich--Vishik. Sobolev spaces corresponding to a
Newton polygon are defined and investigated; in particular it is possible to
describe their trace spaces. With respect to these spaces, an a priori estimate
holds for the Dirichlet boundary value problem connected with an $N$-elliptic
pencil, and a right parametrix is constructed.
