Paper Info
Title
Complexity and decidability for restricted classes of picture languages
Abstract
The paper investigates complexity and decidability questions for two restricted classes of picture languages, called three-way picture languages and stripe picture languages. It is shown that (1) the picture membership problem can be solved in deterministic polynomial time for three-way context-free picture languages, (2) the equivalence and containment problems for picture languages are undecidable for a regular language L 1 and a linear language L 2 , where both L 1 and L 2 describe three-way stripe picture languages, and (3) the intersection emptiness problem for picture languages is undecidable for two three-way stripe linear picture languages and is also undecidable for a regular language L 1 and a linear language L 2 , where L 1 describes a three-way stripe picture language and L 2 describes a stripe picture language.
Year
DOI
Venue
1990
10.1016/0304-3975(90)90180-P
Theor. Comput. Sci.
Keywords
DocType
Volume
restricted class,picture language
Journal
73
Issue
ISSN
Citations 
3
Theoretical Computer Science
13
PageRank 
References 
Authors
0.92
7
1
Name
Order
Citations
PageRank
Changwook Kim110911.88