Paper Info
Title
Leftmove-bound picture languages
Abstract
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. Keywords Formal languages Chain code Picture languages Complexity References [1] H. Abelson A. deSessa Turtle Geometry 1986 The MIT Press Cambridge, MA [2] J.-C. Birget Strict local testability of the finite control of two-way automata and of regular picture description languages Internat. J. Algebra Comput. 1 1991 161 175 [3] K. Culik II E. Welzl Two-way finite state generators M. Karpinski Foundations of Computation Theory, Lecture Notes in Computer Science vol. 158 1983 Springer Berlin 106 114 [4] J. Dassow Convexity and simplicity of chain code picture languages Rostock. Math. Kolloq. 34 1988 53 60 [5] J. Dassow Graph-theoretical properties and chain code picture languages J. Inform. Process. Cybern. EIK 25 1989 423 433 [6] J. Dassow A. Habel S. Taubenberger Chain-code pictures and collages generated by hyperedge replacement J. Cuny H. Ehrig G. Engels Proc. 5th Internat. Workshop on Graph Grammars and their Application to Computer Science, Lecture Notes in Computer Science vol. 1073 1996 Springer Berlin 412 427 [7] J. Dassow F. Hinz Decision problems and regular chain code picture languages Discrete Appl. Math. 45 1993 29 49 [8] H. Freeman Computer processing of line drawing images Comput. Surveys 6 1974 57 97 [9] K.S. Fu Syntactic Pattern Recognition and Applications 1982 Prentice-Hall Englewood Cliffs, NJ [10] R. Gutbrod A transformation system for generating description languages of chain code pictures Theoret. Comput. Sci. 68 1989 239 252 [11] M.A. Harrison Introduction to Formal Language Theory 1978 Addison-Wesley Reading, MA [12] F. Hinz Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats B. Monien R. Cori STACS 89, Lecture Notes in Computer Science vol. 349 1989 Springer Berlin 132 143 [13] F. Hinz J. Dassow An undecidability result for regular languages and its applications to regulated rewriting EATCS Bull. 38 1989 168 173 [14] C. Kim Picture iteration and picture ambiguity J. Comput. System Sci. 40 1990 289 306 [15] C. Kim Complexity and decidability for restricted classes of picture languages Theoret. Comput. Sci. 73 1990 295 311 [16] C. Kim Retreat bounded picture languages Theoret. Comput. Sci. 132 1994 85 112 [17] C. Kim Unambiguous description of chain code picture languages Inform. Process. Lett. 58 1996 75 79 [18] C. Kim I.H. Sudborough The membership and equivalence problems for picture languages Theoret. Comput. Sci. 52 1987 177 191 [19] C. Kim I.H. Sudborough On reversal-bounded picture languages Theoret. Comput. Sci. 104 1992 185 206 [20] H.A. Maurer G. Rozenberg E. Welzl Using string languages to describe picture languages Inform. Control 54 1982 155 185 [21] G. Păun A characterization of recursively enumerable languages EATCS Bull. 45 1991 218 222 [22] A. Rosenfeld Picture Languages — Formal Models for Picture Recognition 1979 Academic Press New York [23] A. Rosenfeld R. Siromoney Picture languages — a survey Languages Des. 1 1993 229 245 [24] K. Slowinski Picture words with invisible lines Theoret. Comput. Sci. 108 1993 357 363 [25] I.H. Sudborough E. Welzl Complexity and decidability for chain code picture languages Theoret. Comput. Sci. 1936 1985
Year
DOI
Venue
2000
10.1016/S0304-3975(98)00164-9
Theor. Comput. Sci.
Keywords
DocType
Volume
Leftmove-bound picture language
Journal
237
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
2
PageRank 
References 
Authors
0.38
10
2
Name
Order
Citations
PageRank
Changwook Kim110911.88
Ivan Hal Sudborough2585193.20