β Scribed by Changwook Kim; Ivan Hal Sudborough
No coin nor oath required. For personal study only.
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 reversalbounded 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 leftmoveunbounded (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.
π SIMILAR VOLUMES
necessarily context-free) bounded languages by full AFL operations, or from any set of' bounded context-free languages by full AFL operations and substitution.
Left-derivation bounded languages are defined as those languages defined from context-free grammars by placing a bound on the number of nonterminals appearing in left-derivations. These languages are generated by left-derivation bounded grammars and form a full AFL not closed under reversal. The lef