wiki_research

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

regular_expression_deterministic (2094B)

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