wiki_research

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

automaton_primality (354B)

      1 # Automaton primality
      2 
      3 decide if an input DFA can be written as the [automaton_intersection] of input DFAs that all have strictly less states
      4 
      5 it in [NP_hard] to decide, see [spenner2026deciding]
      6 
      7 other related article: [jecker2020unary]
      8 
      9 also exists for [automaton_union], see [berry2026decomposition]
     10 
     11 Up: [automata_problems]
     12 
     13 Aliases: prime automaton