Complexity and decidability for restricted classes of picture languages

AbstractThe paper investigates complexity and decidability questions for two restricted classes of picture languages, called three-way picture languages and stripe picture languages. It is shown that (1) the picture membership problem can be solved in deterministic polynomial time for three-way context-free picture languages, (2) the equivalence and containment problems for picture languages are undecidable for a regular language L1 and a linear language L2, where both L1 and L2 describe three-way stripe picture languages, and (3) the intersection emptiness problem for picture languages is undecidable for two three-way stripe linear picture languages and is also undecidable for a regular language L1 and a linear language L2, where L1 describes a three-way stripe picture language and L2 describes a stripe picture language