The NFA Segments Scan AlgorithmShare
- Author(s): Barkol, Omer; Lehavi, David
- HP Laboratories
- Keyword(s): formal languages; regular expression; automata
Abstract: We present a novel way for parsing text with non deterministic finite automatons. For "real life" regular expressions and text, our algorithm scans only a fraction of the characters, and performs a small number of operations for each of these characters (for synthetic worse case scenarios, it would perform worse than classical algorithms). Although there are similar approaches, our algorithm is far simpler and less resource consuming than the alternatives we are aware of.
- External Posting Date: February 21, 2014 [Fulltext]. Approved for External Publication
- Internal Posting Date: February 21, 2014 [Fulltext]