Many aspects of defect theorems



: Harju T, Karhumaki J

Publisher: ELSEVIER SCIENCE BV

: 2004

 Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 324

: 1

: 35

: 54

: 20

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2004.03.051


We give a survey and a unified presentation of the defect theorem, its generalizations and recent aspects of interest. In its basic form, the defect theorem states that if a set of n words satisfies a nontrivial relation, then these words can be expressed simultaneously as products of at most n - I words. In other words, dependency of words causes a defect effect. There does not exist just one defect theorem, but several ones depending on the restrictions that are put to the n - I words. The defect theorem is closely related to equations of words, and in this way to the compactness theorem for systems of word equations. (C) 2004 Elsevier B.V. All rights reserved.


codes, defect theorem, free monoid, independent equations, tilings, word equations



Last updated on 14/10/2025 09:46:42 AM