tdta (1131B)
1 # tDTA 2 3 Defined by a set of [states], an [initial_state], a set of [final_states], and a [transition_function] describing the state of the children of each tree node as a function of the state of the node and the label of the node. 4 5 [acceptance_condition]: all [leaves] are labeled with a [final_state] 6 7 The [tree_languages] that can be recognized by tDTAs are a proper subset of the [regular_tree_languages] 8 - In particular, if such an automaton accepts f(a,b) and f(a',b') then they accept f(a,b') and f(a',b) 9 10 To understand the [expressive_power] of such [automata]: they only depend on the [word_language] of the [paths] from the [root] to the [leaves] in the input [tree] 11 - A [tree] t is accepted by a tDTA A if and only if the set of root-to-leaf [paths] of t is included in the set of root-to-leaf paths of the [trees] accepted by A 12 13 Membership to the class of languages recognized by tDTAs is [decidable]. Generalization: [Boolean_closure_tDTA] 14 15 Generalization: [tDTA_set_acceptance] 16 17 Up: [tree_automaton_top_down], [automata_deterministic] 18 19 See also: [bDTA], [tNTA], [tUTA] 20 21 Aliases: deterministic top-down tree automaton