P Colonies of Capacity One and Modularity

2. Definitions

Throughout the paper we assume that the reader is familiar with the basics of the formal language theory.

We use NRE to denote the family of the recursively enumerable sets of natural numbers. Let Σ be the alphabet. Let Σ* be the set of all words over Σ (including the empty word ε). We denote the length of the word w∈Σ* by |w| and the number of occurrences of the symbol a∈Σ in w by |w|_a.

A multiset of objects M is a pair M = (V, f), where V is an arbitrary (not necessarily finite) set of objects and f is a mapping f: V → N; f assigns to each object in V its multiplicity in M. The set of all multisets with the set of objects V is denoted by V*. The set U ⊆ V is called the support of M and is denoted by supp(M) if for all

x ∈U f(x)≠0 holds. The cardinality of M, denoted by |M|, is defined by |M| = Σ_a∈V f(a). Each multiset of objects M with the set of objects U = {a₁, …, a_n} can be represented as a string w over alphabet U, where

Obviously, all words obtained from w by permuting the letters represent the same multiset M. The ε represents the empty multiset.