کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708671 | 1012829 | 2012 | 5 صفحه PDF | دانلود رایگان |
In this work we study the following implication problem for regular expressions: “Given a set of regular expressions R and a regular expression SS, is it true that every string which matches the regular expressions in R also matches SS?” 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.
Journal: Applied Mathematics Letters - Volume 25, Issue 10, October 2012, Pages 1394–1398