Elegant number-theoretic techniques are used to answer a very natural, decades-old open problem regarding probabilistic finite automata. The author shows that the languages recognized by probabilistic finite automata can be recognized in deterministic logarithmic space. (The result is generalized and extended to probabilistic automata with nonconstant but very slow-growing space bounds.)
Like most previous space-efficient simulations of probabilistic finite automata, Macarie’s work makes heavy use of the Chinese remainder theorem. One of the main technical contributions is a nice construction of an algorithm to determine, given two numbers x and y expressed in Chinese remainder representation, whether x < y.
Some fundamental questions about the complexity of probabilistic finite automata still remain open. One deserving special mention is the question of whether these machines can be simulated by bounded fan-in Boolean circuits of logarithmic depth. (That is, are the languages accepted by probabilistic finite automata in the complexity class NC1?)