wiki_research

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

regular_expression_squaring_universality (330B)

      1 # Regular expression squaring universality
      2 
      3 It is [EXPSPACE_complete], cf https://cstheory.stackexchange.com/a/40250
      4 [meyer1972equivalence]
      5 
      6 Hence the same holds for [language_inclusion] and [language_equivalence]
      7 
      8 And the same holds for [regular_expression_repetition]
      9 
     10 Up: [language_universality], [regular_expression_squaring]