The paper develops EDITOR, a language for manipulating semistructured docum
ents, such as those typically available on the Web. EDITOR programs are bas
ed on two simple ideas, taken from text editors: "search" instructions are
used to select regions of interest in a document, and "cut & paste" instruc
tions to restructure them. We study the expressive power and the complexity
of these programs. We show that they are computationally complete, in the
sense that any computable document restructuring can be expressed in EDITOR
. We also study the complexity of a safe subclass of programs, showing that
it captures exactly the class of polynomial-time restructurings. The langu
age has been implemented in Java and is currently used in the ARANEUS proje
ct as a basis for a wrapper-generation toolkit. (C) 1999 Academic Press.