Complexity and decidability for chain code picture languages
type: Item
instance of: scholarly article
title: Complexity and decidability for chain code picture languages
zbMATH Open document ID: 0565.68065
DOI: 10.1016/0304-3975(85)90041-6
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3902058
zbMATH Keywords: picture description
zbMATH Keywords: membership problem
zbMATH Keywords: regular languages
Wikidata QID: Q54310034
author: I. H. Sudborough
author: Emo Welzl
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90041-6
OpenAlex ID: W1967134973
cites work: Time and tape complexity of pushdown automaton languages
cites work: Q3309090
cites work: Q4775507
cites work: Q4198056
cites work: Q5576254
cites work: Q4198075
cites work: Q5592246
cites work: Q5602929
cites work: Using string languages to describe picture languages
cites work: Q3673129
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: Q3926078
cites work: Q5678435
description: scientific article; zbMATH DE number 3902058