wiki_research

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

automaton_intersection (488B)

      1 # Automaton intersection
      2 
      3 can be done with [product_construction]
      4 
      5 [computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine]
      6 - connections to [3SUM] and [triangle_detection]
      7 - also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness])
      8 
      9 Up: [automaton_constructions], [intersection]
     10 
     11 See also: [regular_expression_conjunction]