TREE GENERATING REGULAR SYSTEMS

被引：128

作者：

BRAINERD, WS

机构：

[1] Department of Mathematics, Naval Postgraduate School, Monterey

来源：

INFORMATION AND CONTROL | 1969年 / 14卷 / 02期

关键词：

D O I：

10.1016/S0019-9958(69)90065-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. © 1969 Academic Press, Inc.

引用

页码：217 / &