A Largest Common d-Dimensional Subsequence of Two d-Dimensional Strings

摘要

We introduce a definition for a largest common d -dimensional subsequence of two d -dimensional strings for d?≥?1. Our purpose is to generalize the well-known definition of a longest common subsequence of linear strings for dimensions higher than one. We prove that computing a largest common two-dimensional subsequence of two given two-dimensional strings is NP-complete. We present an algorithm for the case of the problem when the definition is weakened.