Highly Undecidable Problems about Recognizability by Tiling Systems

DOI10.3233/FI-2009-0045MaRDI QIDQ3634001zbMATH OpenFDO

Authors Olivier Finkel

Publication date 23 June 2009

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/FI-2009-0045

zbMATH Keywords

analytical hierarchydecision problemsdegrees of undecidable problemsinfinite picturesrecognizable languagestwo-dimensional words

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35) Formal languages and automata (68Q45)

Recommendations

• Decision problems for recognizable languages of infinite pictures
• ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES
• Highly Undecidable Problems For Infinite Computations
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Some remarks on tiling recognizable languages

Cited in

(4)

• The complexity of computing the behaviour of lattice automata on infinite trees
• Decision problems for recognizable languages of infinite pictures
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES

This page was built for publication: Highly Undecidable Problems about Recognizability by Tiling Systems

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