Tree generating regular systems Brainerd, Walter S.
Information and control,
01/1969, Letnik:
14, Številka:
2
Journal Article
Odprti dostop
Trees are defined as mappings from tree structures (in the graph-theoretic sense) into sets of symbols.
Regular systems are defined in which the production rules are of the form
Φ → ψ, where
Φ and
ψ ...are trees. An application of a rule involves replacing a subtree
Φ by the tree
ψ.
The main result is that the sets of trees generated by regular systems are exactly those that are accepted by tree automata. This generalizes a theorem of BÜchi, proved for strings.
A tree automaton is a system (
Q,
f
1, …,
f
k
,
F) where
Q is a set of states,
f
1, …,
f
k
are operations on
Q of arbitrary finite index, and
F ⊆
Q is a set of final states. The input to a tree ...automaton is a tree structure and thus the behavior of a tree automaton is a set of trees. These automata are generalizations of ordinary automata, in which all
f's are unary. An algorithm for constructing a minimal tree automaton is given.
PDF
