Reena Elangovan, Shubham Jain, et al.
ACM TODAES
It is shown that if a two-way probabilistic finite-state automaton (2pfa) M recognizes a nonregular language L with error probability bounded below 1/2 , then there is a positive constant b (depending on M) such that, for infinitely many inputs x, the expected running time of M on input x must exceed 2n(b) where n is the length of x. This complements a result of Freivalds showing that 2pfa's can recognize certain nonregular languages in exponential expected time. It also establishes a time complexity gap for 2pfa's since any regular language can be recognized by some 2pfa in linear time. Other results give roughly exponential upper and lower bounds on the worst-case increase in the number of states when converting a polynominal-time 2pfa to an equivalent two-way nondeterministic finite-state automaton or to an equivalent one-way deterministic finite-state automaton.
Reena Elangovan, Shubham Jain, et al.
ACM TODAES
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Khaled A.S. Abdel-Ghaffar
IEEE Trans. Inf. Theory