Name
Abstract | ||
|---|---|---|
Regular expressions play an important role in various fields in computer science. However, handling many regular expressions in parallel requires huge computation resources. Therefore, it is necessary to find and eliminate overlapping regular expressions. In this paper, we consider a special type of regular expressions: expressions comprised of characters and variable-length gaps between such characters. Specifically, we propose a bit-parallel solution to determine whether the languages of two expressions X and Y with variable-length gaps have a common string. The time complexity of our algorithm is O (min (LX 2|Σ|, LX LY)/w) where Σ is the alphabet from which X and Y are drawn, LX and LY are the lengths of the longest strings that respectively match X and Y, and w is the size of the computer word. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2513228.2513299 | RACS |
Keywords | Field | DocType |
common string,computer word,bit-parallel solution,variable-length gap,overlapping regular expression,lx ly,computer science,huge computation resource,regular expression,expressions x | Generalized star height problem,Discrete mathematics,Computer vision,Regular expression,Expression (mathematics),Computer science,Algorithm,Bit parallelism,Artificial intelligence,Time complexity,Computation,Alphabet | Conference |
Citations | PageRank | References |
2 | 0.42 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juan Mendivelso | 1 | 13 | 2.81 |
| Yoan J. Pinzon | 2 | 158 | 16.81 |
| Inbok Lee | 3 | 58 | 10.49 |