Picture languages: is a given set of tiles a maximal code?

The following question is motivated by the recent results of this paper:

http://link.springer.com/chapter/10.1007%2F978-3-642-38771-5_6

A picture is a rectangular array of letters. Given a set S of pictures, let S* stand for the set of those pictures that can be "decomposed" into a composition of members of S as in the following example:

a b c c b a a a b

is a member of the star of S = {

a b

,

c a

,

b

}.

(For formal definitions, see the paper.) 

Now S is a code if every picture in S* can be decomposed in a unique way (with respect to S ofc).

The set S above is a code since there is at most one element of S fitting to the top-left cell of any labeled polyomino (if it's a, we have to use the first domino, if b, the third and if c, the second, iterate).

A code S is maximal if no proper superset of S is a code. (The above S is not maximal since by adding a horizontal domino (a c) we still get a code.)

The question is to determine the complexity of the following problem:

• input: a finite set S of pictures,
• output: YES iff S is a maximal code.

Alternatively, the input can be assumed to be a code.
From the results of the paper we know it's decidable. But is it in P? or coNP-hard?