Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Undecidability of the T...

On the Undecidability of the Tiling Problem

Jarkko Kari, On the Undecidability of the Tiling Problem. In: Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Navrat, Maria Bielikova (Eds.), SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Novy Smokovec, Slovakia, January 19-25, 2008, Proceedings, Lecture Notes in Computer Science 4910, 74–82, Springer, 2008.

Abstract:

The tiling problem is the decision problem to determine if a given finite collection of Wang tiles admits a valid tiling of the plane. In this work we give a new proof of this fact based on tiling simulations of certain piecewise affine transformations. Similar proof is also shown to work in the hyperbolic plane, thus answering an open problem posed by R.M.Robinson 1971 [9].

BibTeX entry:

@INPROCEEDINGS{inpKari_Jarkko08a,
  title = {On the Undecidability of the Tiling Problem},
  booktitle = {SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Novy Smokovec, Slovakia, January 19-25,  2008, Proceedings},
  author = {Kari, Jarkko},
  volume = {4910},
  series = {Lecture Notes in Computer Science},
  editor = {Geffert, Viliam and Karhumäki, Juhani and Bertoni, Alberto and Preneel, Bart and Navrat, Pavol and Bielikova, Maria},
  publisher = {Springer},
  pages = {74–82},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication