Linear Problems in Valued Fields

A first-order formula over a valued field is called linear if it contains no products or reciprocals of quantified variables. We give quantifier elimination procedures based on test term ideas for linear formulas in the following classes of valued fields: discretely valued fields, discretely valued fields with a Z -group as the value group over a language containing predicates stating divisibility in the value group, and non-discretely valued fields. From the existence of the elimination procedures, it follows that the corresponding decision problems are in an alternating single exponential time-space (Berman) complexity class. We exhibit the substructure completeness of the considered classes of valued fields w.r.t. linear formulas.