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 [J].

BRAINERD, WS .

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 [J].

RABIN, MO ;

SCOTT, D .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) :114-125

← 1 2 →