wiki_research

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

simple_regular_expressions (760B)

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