Two undecidability results for chain code picture languages

DOI10.1016/S0304-3975(01)00195-5zbMath0988.68102WikidataQ128027722 ScholiaQ128027722MaRDI QIDQ5958344

Changwook Kim

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

formal languageschain codedecision propertiespicture languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision problems and regular chain code picture languages
• Complexity and decidability for restricted classes of picture languages
• Picture iteration and picture ambiguity
• Complexity and decidability for chain code picture languages
• The membership and equivalence problems for picture languages
• A transformation system for generating description languages of chain code pictures
• On reversal-bounded picture languages
• Picture words with invisible lines
• Retreat bounded picture languages
• Unambiguous description of chain code picture languages
• Leftmove-bounded picture languages
• Undecidability of existential properties in picture languages
• Using string languages to describe picture languages
• Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats

This page was built for publication: Two undecidability results for chain code picture languages