An undecidable problem about rational sets and contour words of polyominoes

DOI10.1016/0020-0190(91)90217-6zbMath0714.68055OpenAlexW2033191436MaRDI QIDQ751298

Danièle Beauquier

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90217-6

zbMATH Keywords

combinatorial problemsformal languages

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45)

Related Items

Decision problems for edge grammars ⋮ A codicity undecidable problem in the plane. ⋮ Polyomino tilings, cellular automata and codicity ⋮ Chain-code pictures and collages generated by hyperedge replacement ⋮ Decision problems and regular chain code picture languages ⋮ Frontier between decidability and undecidability: A survey ⋮ Undecidability of existential properties in picture languages ⋮ \(q\)-enumeration of convex polyominoes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tiling with polyominoes