wiki_research

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

automaton_query_complexity (613B)

      1 # Automaton query complexity
      2 
      3 The [query_complexity] of membership to the [formal_language] accepted by an [automaton]
      4 
      5 - [aaronson2019quantum] studies it for [quantum_complexity] and in particular talks about the fact that it is either constant or linear depending on the language
      6 - [automaton_query_complexity_nondeterministic]
      7 - [conditional_membership]: cf [amarilli2026conditional]
      8 
      9 Up: [query_complexity], [regular_language_membership]
     10 
     11 Aliases: query complexity regular language, regular language query complexity, query complexity regular language membership, regular_language membership query complexity