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 / &

共 12 条

[1] Brainerd W. S., 1967, THESIS PURDUE U
[2] MINIMALIZATION OF TREE AUTOMATA
BRAINERD, WS
[J]. INFORMATION AND CONTROL, 1968, 13 (05): : 484 - &
[3] BUCHI JR, 1964, ARCH MATH LOQIK GRUN, V6, P91, DOI DOI 10.1007/BF01969548
[4] Chomsky N., 1959, INFORM CONTROL, V2, P137, DOI 10.1016/S0019-9958(59)90362-6
[5] Davis M., 1958, COMPUTABILITY UNSOLV
[6] DONER JE, 1967, 8 SYST DEV CORP SCIE
[7] GINSBURG S, 1966, MATHEMATICAL THEORY
[8] GORN S, 1965, SYSTEMS COMPUTER SCI
[9] MEZEI J, 1965, RC1528 IBM RES PAP
[10] FINITE AUTOMATA AND THEIR DECISION PROBLEMS
RABIN, MO
SCOTT, D
[J]. IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) : 114 - 125

← 1 2 →