A1 Refereed original research article in a scientific journal
Many aspects of defect theorems
Authors: Harju T, Karhumaki J
Publisher: ELSEVIER SCIENCE BV
Publication year: 2004
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 324
Issue: 1
First page : 35
Last page: 54
Number of pages: 20
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2004.03.051
Abstract
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.
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.
UTU Research Portal