Kinetic oscillations occurring in the CO-NO reaction on Pt(100) at UHV conditions and relatively high temperatures are accompanied by adsorbate-induced surface restructuring. Employing the Monte Carlo technique, we show the type of spatio-temporal patterns which might be observed in this system on the nm scale. The model used to describe surface restructuring is based on the lattice-gas approximation and predicts the formation of restructured islands even at low adsorbate coverages. Simulations are executed with qualitatively realistic ratio between the rates of different steps involved in the game.