On reversal-bounded picture languages

DOI10.1016/0304-3975(92)90122-VzbMath0754.68068MaRDI QIDQ1200803

Ivan Hal Sudborough, Changwook Kim

Publication date: 16 January 1993

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

zbMATH Keywords

membership problem\(NP\)-completeness\(k\)-reversal-bounded picture language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On regular drawn symbolic picture languages ⋮ Retreat bounded picture languages ⋮ Unambiguous description of chain code 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

• 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
• Using string languages to describe picture languages
• `` Strong NP-Completeness Results
• Classes of picture languages that cannot be distinguished in the chain code concept and deletion of redundant retreats
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On reversal-bounded picture languages