Solving most problems of natural language processing is based on using certain linguistic resources, represented by corpora, lexicons, etc. Usually, these collections of data constitute an enormous volume of information, so processing them requires much computational resources. A reasonable approach for obtaining e±cient solution is that based on applying parallelism; it has started to be promoted already in 1970s. For instance, the possibilities of applying massive parallelism in Machine Translation are considered in [4, 1]. We mention that many of the stages of text processing (from tokenization, segmentation, lematizing to those dealing with natural language understanding) can be carried out by parallel methods. This justi¯es the interest to applying methods o®ered by the biologically inspired models, and by membrane computing in particular. However, there are some issues that by their nature do not allow complete parallelization, yet exactly they are often those \computational primitives" that are inevitably used during solving major problems, like the elementary arithmetic operations are always present in solving di±cult computational problems. Among such \primitives" in the computational linguistics there are handling of the dictionaries, e.g., dictionary lookup and dictionary completion. Exactly these problems constitute the subject of the present paper. In our approach we speak about dictionary represented by a pre¯x tree. Membrane systems are a convenient framework of describing computations on trees. Since membrane systems are an abstraction of living cells, the membranes are arranged hierarchically, yielding a tree structure.