Leftmove-bounded picture languages

Let Π={u, d, r, l} be the chain-code picture alphabet such that u(d, r, l) denotes the graphics command to move the drawing pen up (down, right, left) in the 2D Cartesian plane. It is known that the picture membership problem can be solved in polynomial time for each context-free language over {u, d, r} and is NP-complete for a so-called retreat-bounded regular (or reversal-bounded linear) language over Π. Imposing both retreat and reversal bounds on languages over Π results in the leftmove-bounded languages whose words describe pictures by making no more than a bounded number of left moves. The picture membership problem can be solved in polynomial time for each leftmove-bounded context-free language over Π and is NP-complete for a leftmove-unbounded (but retreat-bounded) linear language over {u, d, lr}. There exists a context-sensitive language over {u, d, r} (or {u, d, lr}) for which the picture membership problem is undecidable.

Authors

• Changwook Kim
• Ivan Hal Sudborough

Keywords

• Formal languages
• Chain code
• Picture languages
• Complexity