Complexity and decidability for restricted classes of picture languages

DOI10.1016/0304-3975(90)90180-PzbMath0694.68052WikidataQ126382608 ScholiaQ126382608MaRDI QIDQ909482

Changwook Kim

Publication date: 1990

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

zbMATH Keywords

complexitydecidabilitypicture languagesformal language theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (9)

On regular drawn symbolic picture languages ⋮ Retreat bounded picture languages ⋮ Picture iteration and picture ambiguity ⋮ Chain-code pictures and collages generated by hyperedge replacement ⋮ Decision problems and regular chain code picture languages ⋮ On reversal-bounded picture languages ⋮ Adding symbolic information to picture models: definitions and properties ⋮ Two undecidability results for chain code picture languages ⋮ Leftmove-bounded picture languages

Cites Work

• Picture iteration and picture ambiguity
• Complexity and decidability for chain code picture languages
• The membership and equivalence problems for picture languages
• Using string languages to describe picture languages
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity and decidability for restricted classes of picture languages