wiki_research

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

tree_evaluation_problem (644B)

      1 # Tree evaluation problem
      2 
      3 You have a [tree] and you want to evaluate a [bottom_up_nondeterministic_tree_automaton] on the tree, in a [nonuniform] sense where each [node] is labeled by the transition function
      4 
      5 Covers in particular the evaluation of [Boolean_formulas] and the acceptance of a fixed [tree_automaton]
      6 
      7 Sometimes considered specifically on [complete_binary_trees] and on functions at the nodes given as input.
      8 
      9 It is in O(log n log log n), cf [cook2023tree] and [goldreich2024cook]
     10 => leading to [williams2025simulating]
     11 
     12 Up: [computational_problem] on [tree]
     13 
     14 Aliases: TreeEval, tree evaluation
     15 
     16 See also: [formula_value_problem]