wiki_research

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

length_universality_automata (418B)

      1 # Length universality automata
      2 
      3 [computational_problem] on [automata] studied in [gawrychowski2020existential]: given an [automaton], is there an integer l such that Sigma^l is included in the language?
      4 - for [NFA] this is [NEXPTIME_complete] and the smallest l can be doubly exponential in the number of states
      5 - for [NFA] for a given l this is [PSPACE_complete]
      6 
      7 Up: [computational_problem], [universality_automata]