Regular Expressions with Numerical Constraints and Automata with Counters
Chapter, Peer reviewed
MetadataShow full item record
Original versionIn: Leucker, M.; Morgan, C. (eds.), Theoretical Aspects of Computing - ICTAC 2009: 231-245 https://doi.org/10.1007/978-3-642-03466-4_15
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
SeriesLecture Notes in Computer Science