SUBRECURSIVE COMPLEXITIES ON GROUPS .2. HIGMANS EMBEDDING THEOREM FOR DECIDABLE GROUPS

被引：8

作者：

AVENHAUS, J ^{[1
]}

MADLENER, K ^{[1
]}

机构：

[1] UNIV KAISERSLAUTERN,FACHBEREICH MATH,D-6750 KAISERSLAUTERN,FED REP GER

来源：

ACTA INFORMATICA | 1978年 / 9卷 / 02期

关键词：

D O I：

10.1007/BF00289077

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Higman's embedding theorem states that every recursively presented (r.p.) group can be embedded in a finitely presented (f.p.) group. We use the results of part I together with an idea of Aanderaa [1] to show that the embedding can be realized preserving the complexity of the word problem of the r.p. group. © 1978 Springer-Verlag.

引用

页码：183 / 193

页数：11

共 7 条

[1]

AANDERAA S, 1975, WORD PROBLEMS, P1

[2]

AVENHAUS J, 1977, ACTA INFORM, V9, P87, DOI 10.1007/BF00263767

[3]

GATTERDAM RW, 1973, B AUSTRALIAN MATH SO, V8, P27

[4] SUBGROUPS OF FINITELY PRESENTED GROUPS [J].

HIGMAN, G .

PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL AND PHYSICAL SCIENCES, 1961, 262 (1310) :455-+

[5] DENSITY OF HONEST SUBRECURSIVE CLASSES [J].

MACHTEY, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1975, 10 (02) :183-199

[6] POLYNOMIAL AND ABSTRACT SUBRECURSIVE CLASSES [J].

MEHLHORN, K .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 12 (02) :147-178

[7]

ROTMAN JJ, 1973, THEORY GROUPS

← 1 →