Paper Info
Title
Retreat bounded picture languages
Abstract
A well-known string-encoding of 2D pictures is to use the picture alphabet π = { u , d , r , l }, where u ( d, r , and l ) means “draw a unit-line by moving the pen up (down, right, and left) from the current point”. A word over π is k -retreat-bounded ( k ⩾0) if it describes a picture in such a manner that the maximum distance of left-moves, ignoring up- and down-moves, from a rightmost point of any partially drawn picture is bounded by k . A set of such words forms a k -retreat-bounded language. A k-retreat-bounded picture language is a set of pictures described by a k -retreat-bounded language. There is a 1-retreat-bounded regular picture language (1-retreat-bounded vertical-stripe linear picture language) for which the membership problem is NP-complete. The membership problem can be solved in O ( n 4 ) time for each k -retreat-bounded nonvertical-stripe context-free picture language. The inclusion and intersection-emptiness problems are undecidable for a 1-retreat-bounded regular picture language and a 2-retreat-bounded regular picture language. The equivalence and ambiguity problems are undecidable for 2-retreat-bounded regular picture languages. The picture recognition algorithm presented is the first polynomial-time algorithm in the literature for a reasonably large subclass of context-free picture languages and the NP-completeness and undecidability results improve the previously known such results for regular picture languages with no structural restriction imposed.
Year
DOI
Venue
1994
10.1016/0304-3975(94)90228-3
Theor. Comput. Sci.
Keywords
DocType
Volume
bounded picture language
Journal
132
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
6
PageRank 
References 
Authors
0.51
10
1
Name
Order
Citations
PageRank
Changwook Kim110911.88