Regular Expressions with Numerical Constraints and Automata with Counters
Chapter, Peer reviewed
MetadataVis full innførsel
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.
Proceedings from the 6th International Colloquium Kuala Lumpur, Malaysia, August 16-20, 2009
SerieLecture Notes in Computer Science