Efficient testing and matching of deterministic regular expressions

作者：

Highlights：

• We prove that determinism of a regular expression (RE) can be decided in linear time.

• We give linear time matching algorithms for large classes of deterministic REs.

• We extend these results to REs with numerical occurrence indicators.

摘要

•We prove that determinism of a regular expression (RE) can be decided in linear time.•We give linear time matching algorithms for large classes of deterministic REs.•We extend these results to REs with numerical occurrence indicators.

论文关键词：Deterministic regular expression,Matching time complexity,Testing determinism,Numerical occurrence indicators

论文评审过程：Received 19 February 2015, Revised 9 January 2017, Accepted 28 May 2017, Available online 20 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.05.013