Programs over semigroups of dot-depth one

The notion of a p-variety arises in the algebraic approach to Boolean circu it complexity. It has great significance, since many known and conjectured lower bounds on circuits are equivalent to the assertion that certain class es of semigroups form p-varieties. In this paper, we prove that semigroups of dot-depth one form a p-variety. This example has the following implicati on: if a Boolean combination of Sigma(1) formulas, using arbitrary numerica l predicates, defines a regular language, one can then find an equivalent S igma(1) formula all of whose numerical predicates are regular. (C) 2000 Els evier Science B.V. All rights reserved.