wiki_research

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

crpq_containment (578B)

      1 # CRPQ containment
      2 
      3 [EXPSPACE_complete]: cf [calvanese2000containment]
      4 
      5 [morvan2025homomorphism] Proposition IV.5.1: [EXPSPACE_hardness] already holds:
      6 - on a fixed [alphabet]
      7 - for [Boolean_CRPQs]
      8 - the [formal_languages] are not empty and do not contain the [empty_word]
      9 - the [LHS] is just a single atom
     10 - the [RHS] is just a set of parallel atoms
     11 Reduction in [figueira2020containment] from a [tiling_problem]
     12 
     13 Different kind of [homomorphism] studied in [beaudou2023complexity], with an [EXPTIME] upper bound
     14 
     15 Up: [crpq], [query_containment]
     16 
     17 See also: [UCRPQ_containment]