wiki_research

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

regular_expression_squaring (446B)

      1 # Regular expression squaring
      2 
      3 [regular_expression] augmented with [squaring] operator
      4 
      5 makes [language_inclusion] and [language_universality] [EXPSPACE_complete], cf [regular_expression_squaring_universality]
      6 
      7 but [intersection_nonemptiness] still in [PSPACE], like for [regular_expression_repetition], cf [regular_expression_repetition_intersection_nonemptiness]
      8 
      9 Up: [regular_expression], [squaring]
     10 
     11 See also: [regular_expression_repetition]