wiki_research

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

simple_regular_expressions (823B)

      1 # Simple regular expressions
      2 
      3 - notion of [STEs] from [martens2018evaluation]
      4 
      5 - version defined in [figueira2024boundedness]
      6   - allows w^* for a [word] w
      7   - allows [regular_expressions] without [Kleene_star]
      8   - allows [regular_expression_repetition]
      9 
     10 - version defined in [morvan2025homomorphism]
     11   - allows a^* for a letter a
     12   - allows a_1 + ... + a_m for letters a_1, ..., a_m
     13 
     14 - versions also defined in [figueira2020containmentb] "Containment of Simple
     15 Conjunctive Regular Path Queries"
     16   - considers various subsets of features of atom types:
     17     - a
     18     - a^*
     19     - A
     20     - A^*
     21   - hard feature is [disjunction] under [kleene_star], causes [query_containment] to go from [NP_complete] to [EXPSPACE_complete]
     22   - otherwise [query_containment] drops to [Pi_p_2] or [PSPACE]
     23 
     24 Up: [regular_expression]
     25 
     26 Aliases: SRE