Leftmove-bounded picture languages
Let Pi = {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 Pi. Imposing both retreat and reversal bounds on languages over Pi 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 Pi 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. (C) 2000 Elsevier Science B.V. All rights reserved.
picture languages formal languages chain code complexity