Before revision:  and that QSG languages not in QLZG admit a reduction from the prefix problem for the monoid U_1, } which we conjecture cannot be maintained in O(1).
After revision:  and that QSG languages not in QLZG admit a reduction from the prefix problem for the monoid U_1, 0, 1} which we conjecture cannot be maintained in O(1).