The Art Gallery Guardian

Regular expression for a interval of non-negative integers

Let m,nNm,n \in \N and mnm\leq n. I wrote a program in Haskell that generate a regular expression that matches all decimal representation of some number in between aa and bb inclusive. The regular expression would have length O(lognloglogn)O(\log n \log \log n). I also included a simple version, which shows how the algorithm is done.

The code was made for the decimal system, but of course it can be generalized to any base.


matchIntRange 123 4321


The main idea is to consider a set of tries. Each one contain strings with the same length. The regular expression has a structure closely related to this trie. It be nice if there is a polytime algorithm to generate the shortest regular expression for this problem if all we can use is (), |.

It is important to also handle cases where we will have repeated elements

matchIntRange 12121212 12121212


This is done by recursively try to compress a free monoid element with the FreeMonoidCompress module.

Posted by Chao Xu on .
Tags: Haskell, regular expression.