wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

regular_expression_deterministic (2142B)

      1 # Deterministic regular expression, aka "one-unambiguous"
      2 
      3 - position automaton is [automata_deterministic]
      4   - aussi [glushkov_automaton] is [automata_deterministic]
      5 
      6 [groz2012deterministic] and [groz2017efficient]
      7 - can check in [linear_time] if [regular_expression] is deterministic
      8 - can perform [regular_expression_matching] in O(n log log m + m)
      9   - [regular_expression_deterministic_matching]
     10 
     11 according to [freydenberger2019deterministic], also an algorithm in O(|Sigma| m + n)
     12 
     13 - notion used in [document_type_definition]
     14 
     15 - generalizations:
     16   - [DRX] with [backreferences] (no longer [regular_language])
     17   - [caron2017hierarchy], extensions within [regular_languages]:
     18     - [k_block_deterministic_regular_expression]: something about a block of k input symbols moving unambiguously to the next k positions of the regular expression
     19       - proper hierarchy
     20         - according to [han2008generalizations]
     21       - any block deterministic [unary_language] is deterministic regular expression
     22     - [k_lookahead_deterministic_regular_expression]: reading the k next symbols of the word makes the following position unique
     23       - proper hierarchy
     24     - notion of (k,l)-unambiguous
     25 
     26 Recognizes a subset of [regular_languages] according to [groz2017efficient]:
     27 - [bruggemannklein1998one]: (a+b)^* a (a+b) has no equivalent deterministic regular expression
     28 - [ping2015deciding] and [czerwinski2017deciding]: decide if an input [language] has an equivalent deterministic regular expression
     29   - [bruggemannklein1998one]: given a [deterministic_automaton], can be done in [ptime]
     30   - given a [nondeterministic_automaton], it is [PSPACE_complete]
     31 
     32 subclass: [regular_expression_strongly_deterministic] [gelade2009regular]
     33 - in the context of this, "deterministic" is called "weakly deterministic"
     34 
     35 - [language_intersection], [language_inclusion] problem for deterministic regexps
     36 
     37 Up: [regular_expression], [determinism]
     38 
     39 Aliases: deterministic regular expression, deterministic regular expressions, one-unambiguous regular expression, one-unambiguous regular expressions, 1-unambgiuous regular expression, 1-unambiguous regular expressions