The Inclusion Problem for Regular Expressions
Chapter, Peer reviewed
MetadataShow full item record
Original versionIn: Dediu, A.-H.; Fernau, H.; Martín-Vide, C. (eds.), Language and Automata Theory and Applications - LATA 2010: 309-320 https://doi.org/10.1007/978-3-642-13089-2_26
This paper presents a new polynomial-time algorithm for the inclusion problem for certain pairs of regular expressions. The algorithm is not based on construction of finite automata, and can therefore be faster than the lower bound implied by the Myhill-Nerode theorem. The algorithm automatically discards unnecessary parts of the right-hand expression. In these cases the right-hand expression might even be 1- ambiguous. For example, if r is a regular expression such that any DFA recognizing r is very large, the algorithm can still, in time independent of r, decide that the language of ab is included in that of (a+r)b. The algorithm is based on a syntax-directed inference system. It takes arbitrary regular expressions as input, and if the 1-ambiguity of the right-hand expression becomes a problem, the algorithm will report this.
Proceedings from the 4th International Conference, LATA 2010 Trier, Germany, May 24-28, 2010
SeriesLecture Notes in Computer Science
Copyright 2010 Springer-Verlag. All rights reserved.