The membership and equivalence problems for picture languages

DOI10.1016/0304-3975(87)90107-1MaRDI QIDQ1098327zbMATH OpenOpenAlexFDO

Authors Changwook Kim, I. H. Sudborough

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0304-3975(87)90107-1

zbMATH Keywords

context-free picture languageequivalence problempattern recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10)

Recommendations

• scientific article; zbMATH DE number 18634
• Picture iteration and picture ambiguity
• Complexity and decidability for restricted classes of picture languages
• Complexity and decidability for chain code picture languages
• Decision problems and regular chain code picture languages

Cites work

• Complexity and decidability for chain code picture languages
• scientific article; zbMATH DE number 3839348 (Why is no real title available?)
• scientific article; zbMATH DE number 3825216 (Why is no real title available?)
• scientific article; zbMATH DE number 3827229 (Why is no real title available?)
• scientific article; zbMATH DE number 3738961 (Why is no real title available?)
• scientific article; zbMATH DE number 3451488 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Using string languages to describe picture languages

Cited in

(21)

• The complexity of some decision problems about two-dimensional array grammars
• A transformation system for generating description languages of chain code pictures
• On reversal-bounded picture languages
• Retreat bounded picture languages
• Unambiguous description of chain code picture languages
• Leftmove-bounded picture languages
• Undecidability of existential properties in picture languages
• Decidability of the consistency problem for regular symbolic picture description languages
• Simple picture processing based on finite automata and regular grammars
• On regular drawn symbolic picture languages
• Satisfiability via smooth pictures
• scientific article; zbMATH DE number 4005638 (Why is no real title available?)
• scientific article; zbMATH DE number 18634 (Why is no real title available?)
• scientific article; zbMATH DE number 1543317 (Why is no real title available?)
• Adding symbolic information to picture models: definitions and properties
• Recognizing picture languages by reductions to string languages
• Two undecidability results for chain code picture languages
• On the equivalence of descriptions of iterated pictures
• Decision problems and regular chain code picture languages
• Complexity and decidability for restricted classes of picture languages
• Picture iteration and picture ambiguity

This page was built for publication: The membership and equivalence problems for picture languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098327)