The Membership and Equivalence Problems for Picture Languages
Abstract The paper describes two principal results: (1) there is a nondeterministic polynomial-time algorithm to determine whether an arbitrary picture is a member of a context-free picture language and (2) the equivalence problem for regular picture languages is not decidable (not even partially decidable). This solves open questions described in earlier publications. Furthermore, these results are best possible. That is, the membership problem for context-free picture languages was earlier shown to be NP-hard and the complement of the equivalence problem for regular picture languages is easily seen to be partially decidable.