Dag Hovland

The article Regular Expressions with Numerical Constraints and Automata with Counters (ICTAC 2009) describes a new algorithm for searching for strings matching regular epxressions with numerical constraints in text documents. The algorithm is implemented in a manner similar to Gnu egrep (http://www.gnu.org/software/grep). It lacks features to be a full replacement for grep.

The algorithm is, unlike the one used in GNU grep, polynomial time, but only extended regular expressions that are counter-1-unmabiguous are allowed. The program exits with a warning if given other epxressions. With the flag "-g" it outputs information about the "Finite Automaton with Counter" (FAC) which is constructed by the program, and how the FAC matches the string.

Run "make". You need at least flex, bison, bash and gcc.

The executable is "grep". The available flags are "-x" for exact matches, also called "line-regexp" (usually it returns a match if some part of a line matches) "-g" for printing out the full FAC and matching process, "-v" for inverted match, "-n" for printing line numbers of occurrences, "-E" for compatibility with grep (extended regular expressions are the standard) and "-c" for counting number of matches. Note that the regular expressions supported are those usually called "extended regular expressions".