  We explore bounds of {\em time-space tradeoffs} in language recognition on
{\em two-way finite automata} for some special languages. We prove: (1) a
time-space tradeoff upper bound for recognition of the languages $L_{EQ}(n)$ on
{\em two-way probabilistic finite automata} (2PFA): $TS={\bf O}(n\log n)$,
whereas a time-space tradeoff lower bound on {\em two-way deterministic finite
automata} is ${\bf \Omega}(n^2)$, (2) a time-space tradeoff upper bound for
recognition of the languages $L_{INT}(n)$ on {\em two-way finite automata with
quantum and classical states} (2QCFA): $TS={\bf O}(n^{3/2}\log n)$, whereas a
lower bound on 2PFA is $TS={\bf \Omega}(n^2)$, (3) a time-space tradeoff upper
bound for recognition of the languages $L_{NE}(n)$ on exact 2QCFA: $TS={\bf
O}(n^{1.87} \log n)$, whereas a lower bound on 2PFA is $TS={\bf \Omega}(n^2)$.
  It has been proved (Klauck, STOC'00) that the exact one-way quantum finite
automata have no advantage comparing to classical finite automata in
recognizing languages. However, the result (3) shows that the exact 2QCFA do
have an advantage in comparison with their classical counterparts, which has
been the first example showing that the exact quantum computing have advantage
in time-space tradeoff comparing to classical computing.
  Usually, two communicating parties, Alice and Bob, are supposed to have an
access to arbitrary computational power in {\em communication complexity} model
that is used. Instead of that we will consider communication complexity in such
a setting that two parties are using only finite automata and we prove in this
setting that quantum automata are better than classical automata and also
probabilistic automata are better than deterministic automata for some well
known tasks.
