Complexity and decidability for chain code picture languages. (English) Zbl 0565.68065

A picture description is a word over the alphabet \(\{\) u,d,r,l\(\}\), where u means ”go one unit line up from the current point”, and d,r, and l are interpreted analogously with down, right, and left instead of up. By this, a picture description describes a walk in the plane - its trace is the picture it describes. A set of picture descriptions describes a (chain code) picture language. This paper investigates complexity and decidability questions for these picture languages. Thus it is shown that the membership problem is NP-complete for regular picture languges (i.e., picture languages described by regular languages of picture descriptions), and that it is undecidable whether two regular picture description languages describe a picture in common. After this we investigate so-called stripe picture languages (all pictures are within a stripe defined by two parallel lines), providing ’better’ complexity and decidability results: Membership is decidable in linear time for regular stripe picture languages. Emptiness of intersection and equivalence is decidable for regular stripe picture languages.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Time and tape complexity of pushdown automaton languages, Inform. Control, 13, 186-206 (1968) · Zbl 0257.68065
[2] Culik, K.; Welzl, E., Two-way finite state generators, (Karpinsky, M., Foundations of Computation Theory. Foundations of Computation Theory, Lecture Notes in Computer Science, 158 (1983), Springer: Springer Berlin), 106-114 · Zbl 0528.68059
[3] Freeman, H., Computer processing of line-drawing images, Computing Survey, 6, 57-97 (1974) · Zbl 0287.68067
[4] Garey, M. R.; Johnson, D. S., Computers and Intractability — A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[5] Ginsburg, S., The Mathematical Theory of Context-Free Languages (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0184.28401
[6] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[7] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[8] Maurer, H. A., Theoretische Grundlagen der Programmiersprachen (1969), BI, Mannheim · Zbl 0204.31801
[9] Maurer, H. A.; Rozenberg, G.; Welzl, E., Using string languages to describe picture languages, Inform. Control, 54, 155-185 (1982) · Zbl 0523.68065
[10] Maurer, H. A.; Rozenberg, G.; Welzl, E., Chain code picture languages, (Ehrig, H.; Nagl, M.; Rozenberg, G., Graph Grammars and Their Application to Computer Science. Graph Grammars and Their Application to Computer Science, Lecture Notes in Computer Science, 153 (1983), Springer: Springer Berlin), 232-244 · Zbl 0522.68069
[11] Minsky, M. L., Recursive unsolvability of Post’s problem of “Tag” and other topics in the theory of Turing machines, Ann. Math., 74, 437-455 (1961) · Zbl 0105.00802
[12] Rosenfeld, A., Picture Languages—Formal Models of Picture Recognition (1979), Academic Press: Academic Press New York · Zbl 0471.68074
[13] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press London · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.