Archive for December 26, 2012

Wednesday, December 26, 2012

Studying Finite Automata

This question on the Theoretical Computer Science Stack Exchange generated some good answers (via Nicolas Seriot):

So “why” exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)?

Incremental Regular Expressions

Eugene Kirpichov (via Hacker News):

In this article we further develop Piponi’s approach, which employs a number of beautiful algorithmic techniques from the world of functional programming, to build a Java library for incremental regular expression matching. This is also an interesting investigation into how the functional approach blends together with an imperative language.


“Incremental” means “match result is efficiently maintained under certain operations”, where the operations include concatenating two strings and splitting a string in part around an index. Obviously, these two operations form a basis for all kinds of rearrangements, such as inserting or deleting a word from the middle of a string, or appending characters to its back or front, etc.