| Current Trends in Theory and Practice of Computer Science |
| Home |
 |
|
|
Foundations of Computer Science Thursday, January 24, 15:30 - 17:00 Jarkko Kari Undecidability of the Tiling Problem A classical result by R.Berger (1964) states that it is undecidable
if a given set of tiles admits a valid tiling of the plane.
We give a new, simple proof of this result. Then we show how
our proof can be modified to demonstrate the undecidability
of the tiling problem on the hyperbolic plane, thus answering
an open problem asked by R.M.Robinson in 1971.
|
| SOFSEM 2008, January 19-25, High Tatras, Slovakia |