Affordable Access

Publisher Website

Implication of regular expressions

Authors
Journal
Applied Mathematics Letters
0893-9659
Publisher
Elsevier
Volume
25
Issue
10
Identifiers
DOI: 10.1016/j.aml.2011.12.009
Keywords
  • Regular Expressions
  • Incomplete Information
  • Complexity

Abstract

Abstract In this work we study the following implication problem for regular expressions: “Given a set of regular expressions R and a regular expression S, is it true that every string which matches the regular expressions in R also matches S?” The problem comes in two flavors: “non-disjoint” and “disjoint”. We show that both of them are PSPACE-complete. While the complexity for the first variant is not surprising–the problem is coNP-complete even for very simple patterns (given by wildcards)–the complexity result for the second variant represents a big jump since the problem is in PTIME for the case of patterns with wildcards. Towards the goal of charting the boundary of tractability, we then present an analysis of when the problem remains in PTIME.

There are no comments yet on this publication. Be the first to share your thoughts.