Regular Expressions with Numerical Constraints and Automata with Counters

Abstract

Regular expressions with numerical constraints are an extension of regular expressions, allowing to bound numerically the number of times that a subexpression should be matched. Expressions in this extension describe the same languages as the usual regular expressions, but are exponentially more succinct. We de ne a class of nite automata with counters and a deterministic subclass of these. Deterministic nite automata with counters can rec- ognize words in linear time. Furthermore, we describe a subclass of the regular expressions with numerical constraints, a polynomial-time test for this subclass, and a polynomial-time construction of deterministic nite automata with counters from expressions in the subclass.