Speculative data-parallel algorithms for language recognition have been widely experimented for various types of FA (DFA and NFA) automata, often derived from regular expressions. Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks overall consistency. In chunk recognition it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. Existing data parallel DFA-based recognizers suffer from the excessive number of starting states, and the NFA-based ones from the number of nondeterministic transitions. Our data-parallel algorithm is based on the new FA type called reduced interface DFA (RI DFA), which minimizes the speculation overhead without incurring in the penalty of nondeterministic transitions or of impractically enlarged DFA machines. The algorithm is proved to be correct and theoretically efficient, because it combines the state-reduction of an NFA with the speed of deterministic transitions, thus improving on both DFA-based and NFA based existing implementations. The practical applicability of the RI-DFA approach is confirmed by a quantitative comparison of the starting state number for a large public benchmark of complex FAs. On multi-core architectures, the RI-DFA is much faster than the NFA-based one on all benchmarks, while it performs as well as the DFA-based one on some benchmarks and much better on some others.