On the Power of One-Way Automata with Quantum and Classical States

We consider the model of one-way automata with quantum and classical states (QCFAS) introduced in [23]. We show, by a direct approach, that QCFAS with isolated cut-point accept regular languages only, thus characterizing their computational power. Moreover, we give a size lower bound for QCFAS accepting regular languages, and we explicitly build QCFAS accepting the word quotients and inverse homomorphic images of languages accepted by given QCFAS with isolated cut-point, maintaining the same cut-point, isolation, and polynomially increasing the size.