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?

Off we go

Hi there,

I've created this blog devoted to various problems in theoretical computer science.

The purpose of the posts here is threefold:

1. I wanted for a long time to have these things all together.
2. I hope it will serve as a basis for students to have some problems to work on if they wish. Students of Uni Szeged can always drop me a few lines, should they become interested in any of these problems -- I'm pretty sure we can arrange a BSc / MSc thesis based on any of these topics.
3. I plan to post (at least occasionaly) a few stories on partial results whenever I succeed to have some progress :) (and also maybe post every now and then on the failures :P ) Think of it as PR. (Theoretical computer science badly needs PR nowadays..)

For all of you readers, welcome and feel free to leave comments, suggestions, ideas etc -- I will be grateful for them.

Cheers,

--szabivan