9 

    10 

    11 %% POSIX specification------------------------

    12 @InProceedings{Okui10,

    13 author="Okui, Satoshi

    14 and Suzuki, Taro",

    15 editor="Domaratzki, Michael

    16 and Salomaa, Kai",

    17 title="Disambiguation in Regular Expression Matching via Position Automata with Augmented Transitions",

    18 booktitle="Implementation and Application of Automata",

    19 year="2011",

    20 publisher="Springer Berlin Heidelberg",

    21 address="Berlin, Heidelberg",

    22 pages="231--240",

    23 abstract="This paper offers a new efficient regular expression matching algorithm which follows the POSIX-type leftmost-longest rule. The algorithm basically emulates the subset construction without backtracking, so that its computational cost even in the worst case does not explode exponentially; the time complexity of the algorithm is O(mn(n{\thinspace}+{\thinspace}c)), where m is the length of a given input string, n the number of occurrences of the most frequently used letter in a given regular expression and c the number of subexpressions to be used for capturing substrings. A formalization of the leftmost-longest semantics by using parse trees is also discussed.",

    24 isbn="978-3-642-18098-9"

    25 }

    26 

    27 %% POSIX specification------------------------

    28 

    29 %% Brzozowski ders------------------------

    30 @article{Berglund14,

    31 author = {Berglund, Martin and Drewes, Frank and Van Der Merwe, Brink},

    32 year = {2014},

    33 month = {05},

    34 pages = {},

    35 title = {Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching},

    36 volume = {151},

    37 journal = {Electronic Proceedings in Theoretical Computer Science},

    38 doi = {10.4204/EPTCS.151.7}

    39 }

    40 

    41 @InProceedings{Berglund18,

    42 author="Berglund, Martin

    43 and Bester, Willem

    44 and van der Merwe, Brink",

    45 editor="Fischer, Bernd

    46 and Uustalu, Tarmo",

    47 title="Formalising Boost POSIX Regular Expression Matching",

    48 booktitle="Theoretical Aspects of Computing -- ICTAC 2018",

    49 year="2018",

    50 publisher="Springer International Publishing",

    51 address="Cham",

    52 pages="99--115",

    53 abstract="Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, and we analyse the complexity of regular expression matching when using Boost semantics.",

    54 isbn="978-3-030-02508-3"

    55 }

    56 

    57 

    58 @inproceedings{Chen12,

    59 author = {Chen, Haiming and Yu, Sheng},

    60 year = {2012},

    61 month = {01},

    62 pages = {343-356},

    63 title = {Derivatives of Regular Expressions and an Application},

    64 volume = {7160},

    65 doi = {10.1007/978-3-642-27654-5_27}

    66 }

    67 

    68 

    69 

    70 %% Brzozowski ders------------------------

    71 

    72 

    73 %% look-aheads------------------------

    74 @article{Takayuki2019,

    75   title={Derivatives of Regular Expressions with Lookahead},

    76   author={Takayuki Miyazaki and Yasuhiko Minamide},

    77   journal={Journal of Information Processing},

    78   volume={27},

    79   number={ },

    80   pages={422-430},

    81   year={2019},

    82   doi={10.2197/ipsjjip.27.422}

    83 }

    84 

    85 %% look-aheads------------------------

   617 

   618