Linear problems in valued fields

A first-order formula over a valued field is called linear if it contains n o products or reciprocals of quantified variables. We give quantifier elimi nation procedures based on test term ideas for linear formulas in the follo wing classes of valued fields: discretely valued fields, discretely valued fields with a z-group as the value group over a language containing predica tes stating divisibility in the value group, and non-discretely valued fiel ds. From the existence of the elimination procedures, it follows that the c orresponding decision problems are ill an alternating single exponential ti me-space (Berman) complexity class. We exhibit the substructure completenes s of the considered classes of valued fields w.r.t. linear formulas. (C) 20 00 Academic Press.