@techreport{TR-IC-14-07,
   number = {IC-14-07},
   author = {Fernando Granha Jeronimo and Arnaldo Vieira Moura},
   title  =  {{On  the  Quantum-Classical  Separation  of  Marking and
                   Multi-Head Automata}},
   month = {May},
   year = {2014},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 20 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       A  2QCFA  is  an  automata  model  that  combines constant size
       quantum  and  classical  memories.  This model is more powerful
       than  any  2DFA  since  it recognizes some non-regular and even
       non-context  free  languages.  In the classical paradigm, it is
       possible to increase the computational power of a 2DFA by using
       markers (pebbles) or augmenting the number of heads. Therefore,
       it  is  natural to investigate their quantum analogues. In this
       work,  we  propose a new general marking automaton based on the
       2QCFA model. We prove that this model is more powerful than its
       classical  analogues  in terms of computability and complexity.
       Moreover, we answer affirmatively to an open question regarding
       the  quantum-classical  computability  separation of multi-head
       2QCFA and 2DFA.
  }
}