On the Computational Power of Programs over BA<inf>2</inf> Monoid

The PLP conjecture for monoids states that for every monoid M, either M is universal (that is, for every language L⊆ Σ∗ there is a program over M which accepts the language L) or it has the polynomial length property (that is, every program over the monoid M has an equivalent program of length poly(n) ). The conjecture has been confirmed (Tesson-Therien (2001)) for the case of groups and several subclasses of aperiodic monoids such as the variety DA and the monoids divided by the monoid U. However, the case of the set of monoids divided by the monoid BA2 is still open, which if resolved, confirms the conjecture for all aperiodic monoids. In this paper, we make progress towards confirming the conjecture for the case when the monoid is BA2. It is known (Tesson-Therien 2001) already that the monoid BA2 is not universal. Towards proving that the monoid BA2 has polynomial length property, we show the following results: we define a program over a monoid M to be a non-nullable program if there is no input for which the yield of the program is the zero of the monoid. We prove the following: If a program over BA2 is non-nullable, then there is an equivalent program with length at most poly(n).If a program over BA2 is nullable, then it should be exponentially non-nullable - that is there should be at least 2Ω(n) many inputs which send the output of the program to 0 of BA2. We show that for any program P over BA2, if the zeroes of the program have a witness subprogram of polynomial length, then there is a program of length poly(n) equivalent to program P. On the universality front, Tesson and Therien(2001) have already shown that PARITY cannot be computed by programs over BA2. We strengthen this in two ways. Firstly, we show that programs over BA2 cannot accept any subset of PARITY or PARITY¯ of size nω(1). Secondly, we generalize the model of programs to allow parity queries to the input instead of variables. We show that BA2 cannot compute parity of n input bits even when parity queries are allowed of size k<n3. In contrast, we show that there are polynomial length programs over BA2 to compute parity when queries are allowed as parity of n3 bits or higher.