A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Many aspects of defect theorems
Tekijät: Harju T, Karhumaki J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2004
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 324
Numero: 1
Aloitussivu: 35
Lopetussivu: 54
Sivujen määrä: 20
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2004.03.051
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali