Archive for December 26, 2012

Wednesday, December 26, 2012 [Tweets] [Favorites]

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.