Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!ylfink From: ylfink@water.UUCP Newsgroups: ont.events,uw.talks Subject: Some New Results About Tiling the Plane. Message-ID: <1117@water.waterloo.edu> Date: Wed, 23-Sep-87 14:18:34 EDT Article-I.D.: water.1117 Posted: Wed Sep 23 14:18:34 1987 Date-Received: Fri, 25-Sep-87 05:38:17 EDT Distribution: ont Organization: U of Waterloo, Ontario Lines: 71 Keywords: Prof. M. Nivat, Thurs., Sept. 24/87, 3:30PM, MC 6091A. Xref: utgpu ont.events:716 junk:5818 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES THEORY SEMINAR - Thursday, September 24, 1987 Professor Maurice Nivat visiting the Department of Computer Science, will speak on ``Some New Results About Tiling the Plane''. TIME: 3:30 PM ROOM: MC 6091A ABSTRACT The tiles we consider are polyominoes or connected subsets of unit squares which contain no hole. Given a finite set of finite tiles of this kind, which can be only translated but are in infinite supply, it is undecidable whether - there exists a rectangle which can be exactly covered using these tiles, - there exists a figure of any shape which can be covered in two different ways. We characterize the tiles which are exact, that is, the whole plane can be covered by such a tile alone: a tile is exact iff it is a pseudo-parallelogram which means that there exists four points x , x , x , x on - - - - 1 2 3 4 the border satisfying - the vectors x , x and x , x are equal (so - - - - 1 4 2 3 that x , x , x , x are indeed the vertices of - - - - 1 2 3 4 a real parallelogram, - the segments [x , x ] and [x , x ] of the - - - - 2 4 2 3 border are equal (these segments are words on - - {h, h, v, v} representing the broken line from -- - - -- September 22, 1987 - 2 - one point to another), - the segments [x , x ] and [x , x ] are - - - - 1 2 4 3 conjugate words. September 22, 1987