הגדרות

הגדרה: תהי S קבוצת סימנים. מערכת ריצוף מעל S הינה זוג (A=(C,c0

כאשר CεS×S×S×S קבוצת אריחים סופית.

coεC – אריח התחלתי (לפינה השמאלית התחתונה).

הגדרה: תהי A מערכת ריצוף. ריצוף בעזרת A הינה פונקציה f: N×N→C.

השאלה של ריצוף קיר היא בעצם השאלה, האם אפשר לרצף קיר אינסופי.

האם יש חסם על קיר כלשהו.

הגדרה: תהי A מערכת ריצוף מעל קבוצה S . ויהי f ריצוף ל-A  .נאמר כי f הינו ריצוף תקין ל-A ,

אם מתקיימים התנאים הבאים:

1)                                        f(0,0)=co

2)                                        לכל iεN ולכל jεN אם:

       f(i,j)=(S1,S2,S3,S4)

            f(i+1,j)=(S1',S2',S3',S4')

אזי: S2=S4'

3)                                        לכל iεN ולכל jεN אם:

       f(i,j)=(S1,S2,S3,S4)

f(i,j+1)=(S1',S2',S3',S4')

אזי: S1=S3'

הגדרה: שפת הריצוף הינה השפה:T

{A מערכת ריצוף, ול-A ריצוף תקין ברביע הראשון האינסופי|T  =  {A