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.



Last updated on 2025-14-10 at 09:46