Undecidability of existential properties in picture languages

DOI10.1016/S0304-3975(97)00279-XzbMath0952.68083WikidataQ126644374 ScholiaQ126644374MaRDI QIDQ1575948

Denis Robilliard, David Simplot

Publication date: 23 August 2000

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

zbMATH Keywords

Post correspondence problemrational picture languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35)

Related Items (4)

On regular drawn symbolic picture languages ⋮ Adding symbolic information to picture models: definitions and properties ⋮ Two undecidability results for chain code picture languages ⋮ Perfectly quilted rectangular snake tilings

Cites Work

• Decision problems and regular chain code picture languages
• An undecidable problem about rational sets and contour words of polyominoes
• Complexity and decidability for chain code picture languages
• The membership and equivalence problems for picture languages
• On characterizations of recursively enumerable languages
• Composed figures of pixels and inverse monoid
• Using string languages to describe picture languages
• Recursive Unsolvability of a problem of Thue
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Undecidability of existential properties in picture languages