Subrekursive Komplexität bei Gruppen

Acta Informatica 9, 183 - 193 (1978)

�9 by Springer-Verlag 1978

Subrekursive Komplexit it bei Gruppen II. Der Einbettungssatz yon Higman fiir entscheidbare Gruppen

J. Avenhaus und K. Madlener

Fachbereich Informatik und Fachbereich Mathematik der Universit~it, Postfach 3049, D-6750 Kaiserslautern, Germany (Fed. Rep.)

Subrecursive Complexities on Groups

II. Higman's Embedding Theorem for Decidable Groups

Summary. 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.

Der Einbettungssatz von Higman besagt in seiner klassischen Form [4], dab jede rekursiv dargestellte (r.d.) Gruppe in eine endlich dargestellte (e.d.) Gruppe eingebettet werden kann. In dieser Arbeit soll dieser Satz auf den subrekursiven Bereich iibertragen und versch~irft werden: Ist aug eine zul~issige Komplexit~itsklasse [2] und G eine JU-entscheidbare r.d. Gruppe, so l~il3t sich effektiv eine ~r entscheidbare e.d. Gruppe H angeben, in die G JU-eingebettet ist.

Fiir spezielle Komplexit~itsklassen (die Klasse der primitiv rekursiven Funktio- hen und die Grzegorczyk-Klassen g,(A) ftir n>4) hat Gatterdam [3] auf v611ig anderem Weg schon ein solches Ergebnis erzielt. Die hier betrachteten Komplexi- t~itsklassen umfassen auch g3 und allgemeiner die von Machtey [5] eingeftihrten gutartigen Klassen, die bekanntlich innerhalb der Grzegorczyk-Hierarchie und auch innerhalb der Klasse der rekursiven Funktionen dicht liegen.

Mit leichten Modifikationen des Beweises l~il3t sich das Ergebnis auch auf die von Mehlhorn [6] eingefiihrten polynomialen Klassen iibertragen.

Wit verwenden hier eine Idee von Aanderaa [-1], um den Higmanschen Satz mit Hilfe yon Britton-Erweiterungen zu beweisen. Mit Hilfe der in [-2] erzielten Resultate Hil3t sich aus einer geeigneten Darstellung von G eine e.e. Gruppe H explizit angeben, in die G eingebettet ist. Dies gelingt bei der Konstruktion in [3] nicht.

Dies ist der zweite Teil einer Arbeit, die mit [-2] begonnen wurde. Es wurden daher die Bezeichnungen und einige Ergebnisse von dort tibernommen. Wir setzen voraus, dal3 der Leser damit vertraut ist. Dieser Teil hat zwei Kapitel.

0001 - 5903/78/0009/0183/$02.20

184 J. Avenhaus und K. Madlener

In Kapitel 1 wird das Hauptergebnis formuliert und bewiesen, w~ihrend Kapitel 2 den Beweis zu dem technischen Lemma 1.3 enthiilt.

1. Der Einbettungssatz von Higman fiir ~tf-entscheidbare Gruppen

Es sei T eine endliche Menge und L __T*. Eine Gruppe G = (T; L ) hei[3t rekursiv dargestellt (r.d.), wenn L rekursiv aufz~ihlbar ist.

Definition 1.1. Es seien G = (T; L ) und H = (S; M) zwei e. e. Gruppen. G heigt in H eingebettet, falls es eine Abbildung 2: _T*~_S* mit 2(e)=e gibt, so dab for alle u, vs_T* gilt

2(uv)=2(u)2(v) in H,

2(u)=2(v) in H ~ u = v in G.

2 heil3t eine ~f-Einbettung, falls 2 e ~ und 2(G) in H oU-entscheidbar ist. Unser Ziel ist der folgende Satz:

Satz 1.1. Es sei 4U eine Komplexit~itsklasse und G = ( T ; L ) eine r.d. X- entscheidbare Gruppe. Dann gibt es eine e.d. ~-entscheidbare Gruppe H = ( T 1 ; L1), in die G ~-eingebettet ist.

Wit k/Snnen o.B.d.A, voraussetzen, dab L oU-entscheidbar ist und nut positive W6rter (L c T*) enth~ilt. Ist dies n~imlich nicht der Fall, so gehen wir zuerst zur Darstellung G = ( T; R) tiber, wobei R die Menge aller Relatoren von (T; L ) ist. (R ist rekursiv aufz~ihlbar und nach Voraussetzung X-entscheidbar.) Dann gehen wir zur Darstellung (S; M ) von G tiber, wobei S = Tw T' mit T ' = {t': t e T} und M =R'w{tt ': tE T} ist. Hier entsteht R' aus R, wenn man in jedem Wort w e R die Buchstaben ~ durch t' ersetzt. Mit R ist auch M rekursiv aufziihlbar und X- entscheidbar.

Es sei also G = (T; L ) mit L _ T* und )~L e ~ . Wit konstruieren zun~ichst wie in Kapitel 1 von [-2] eine TM-Halbgruppe F = (S w Q;/7) mit T _ S und dann wie in Kapitel 2 yon [2] die Gruppen Go, G~ . . . . . G 5 . Die Gruppe G 5 ist dann e.d. und Jf- entscheidbar.

Es ist nun ntitzlich, ftir G s eine andere Darstellung zu w~ihlen. Mit p--qo und neuen Symbolen to, k o l'tihren wir einige Tietze-Transformationen dutch

Gs=(G3,t,k; -txt=x, fcxk=x, fcqtqk=gltq, -irt=r, f~rk=r (r~R))

~ ( G 5 ,to ,ko; to=(~p )-1 t(hp), k o=hkh)

~ ( G 3, t o, ko; (hptoOh)a(f~PtoPh)=a (ae {x} uR),

(hfcoh) a(hkoh ) = a (a~ {x} u R),

(f~fr h) ~f~p toIjhq (hk oh) = ghp to~hq)

:G 6 --= ( 8 6 ; M).

Es ist S 6 = S u Q u R ~ {x, to, ko} und M besteht aus den definierenden Rela- tionen von G3 und den oben explizit angegebenen Relationen. G 6 ist e.d. und ~ -

Subrekursive Komplexit~it bei Gruppen. II 185

entscheidbar, und aus Lemma 1.2 und Lemma 4.10 von [2] entnimmt man, dab ffir ein Wort w~ T* gilt

w~Lcc.hpwh=q in F~ko(w-ltoW)=(W-ltow)ko in G 6.

Es sei To=Tu{to} und

F = ( T o ; ~)

EL=(w- atoW: wcL) in F

F o = (F, ko; ko (w- a to w) k o = w- 1 to w (w ~ L)) .

F o ist eine Britton-Erweiterung yon F m i t stabilem Buchstaben k o. Fiir die von T o und ko Toko erzeugte Untergruppe von F o gilt also

(To, koToko)=(To) * (/~o Toko), E L = ~o E L ko

d.h., sie ist freies Produkt mit amalgamierten Untergruppen E L--- koELko .

Lemma 1.1 (Aanderaa). F o ist in G 6 durch die Identit~it eingebettet. Die von T o, ko erzeugte Untergruppe v o n G 6 hat also die Darstellung (To, ko; f~oW-~towko = w- ~ to w (w s L)) ; insbesondere gilt in G 6

(To, F:oToko)=(To) * (koToko). E L = kO E L k o

Mit diesem Lemma ist das wesentliche Hilfsmittel bereitgestellt. Wir k6nnen nun eine e.d. Gruppe angeben, in die G •-eingebettet ist. Dazu bilden wir zun~ichst G 6 • G. Diese Gruppe ist nicht e.d., da sie die unendlich vielen Relatoren yon G enth~ilt. Aber zwei Britton-Erweiterungen f'dhren zum Ziel: Wir werden zeigen, dab G in die in Definition 1.2 definierte Gruppe H X-eingebettet ist.

Es sei T'={t': t~T} eine Kopie yon T und w'ET_'* die Kopie von w~T* . Weiter sei E={w': w~L} und K=(T';E>. Dann ist G~-K.

Definition 1.2. Die Gruppen Ho, H 1, n 2 , H seien definiert durch

H o - - G 6 • K--- ($6, T ' ; M, E, at'=t'a (aES6, t '~ T ' ) ) ,

H a = ( H o , d; cltt'd=t, [tf%tkod=kotko (t~ T), Cltod=to, [tfCotokod=fcotoko> ,

H 2 = ( H i , z; ~tz=t, ~fcotkoz=~:otk o (tE T), ~toZ=tod, YlCotokoz=kotokod ). H = ( T a ; LI> entsteht aus H2, indem man die Relatoren L' fortl~iBt.

Lemma 1.2. a) H a ist eine Britton-Erweiterung von H o.

b) H 2 ist eine Britton-Erweiterung yon H 1.

c) H ist eine e.d. Gruppe mit H=H 2.

Beweis. a) Es ist zu zeigen, dab die Isomorphiebedingung erffillt ist: Die von A ={tt', kotko (t~T), to, lcotoko} und B1={t, lcotk o (t~T), to,~Cotoko} erzeugten


Untergruppen yon H o sind unter der Abbildung ebl(tt')=t, eb,(kotko)=kotko, (I91 (tO) = to, (~ff l (ko toko) =fr toko isomorph.

~1 ist die Einschr~inkung des kanonischen Homomorphismus Ho--.G 6 auf (Ax) und somit wohldefiniert. Zum Nachweis der Isomorphie geben wir einen Homomorphismus 431: <BI>--,<Ax> an, der zu ~1 invers ist. Sei 431(t)=tt', 431(to) =to, ~l(kotko)=kotko, ~l(kotoko)=Eotoko �9 Es ist <B~> = (To, koToko). Wegen Lemma 1.1 mug f'tir den Nachweis der Wohldefiniertheit 431 (v)= cb 1 (kovko) in Ho ffir alle v e EL gezeigt werden. Da die w - ' to w (w e L) die Gruppe E L frei erzeugen, reicht es, 43i(w-'toW)=431(f%w-ltowko) f'tir w s L zu zeigen. Da die t m i t den t' kommutieren, gilt 43 1 (w) = w w' in Ho, und Rir w e L gilt w' = e in Ho. Also haben wir 431(w- ItoW)=(ww' )- 'toWW' = w - ' toW=f%w- i towko=43,(f%w- 'towko) in H o. Offenbar ist 431 invers zu ~ , ~1 also ein Isomorphismus.

b) Zu zeigen ist, dab die von A 2 = {t, f%tk o (t ~ T), t o, kotoko} und B E = {t, f%tk o (t ~ T), rod, kotokod } erzeugten Untergruppen von H 1 unter der Abbildung ~2(t) =t, CrPE(to)--tod , qbE(kotko)=kotko, ~2(kotoko)=kotokod isomorph sind.

Wegen (A 2 ) = ( To, f% To ko) muB zum Nachweis der Wohldefiniertheit von ~2 wie in a) gezeigt werden, dab ~2(w-ltoW)=qb2(kow-' towko) in H l ffir alle w e L gilt. In H 1 gilt d w = w w ' d und kowkod=dkowk o Rir w6_T* und w'=e ftir w e L . Daraus folgt ~2 (w-i to W)=w-i to d w = w - l to w w ' d = w - l to w d=ko W-l to w ko d = cb z (~oW- a to wko) in H 1 ftir w ~ L. Also ist ~2 wohldefiniert. Um zu zeigen, dab ~b 2 ein l somorphismus ist, definieren wir einen Homomorphismus 7': H t-* Hi , so dab die Einschr~inkung 432: = 7JI<B~> invers zu ~2 ist. Sei 5~ = e, ~(t') = e ftir t' ~ T' und ~(a) = a ffir a ~ S 6. 5 u erhalt alle Relationen von H , und ist somit wohldefiniert. Man sieht sofort, dab 432 invers zu ~z ist.

c) H ist endlich dargestellt, denn die Menge der Erzeugenden T1 = S 6 ~ T 'w {d, z} ist endlich und die Menge der definierenden Relationen L, - sie besteht aus M und den in der Definition von H0, Ha, H E explizit angegebenen Relationen - ist endlich. Zu zeigen bleibt, dab w' = e in H ftir alle w' 6 E gilt. Es sei w' e E, also w 6 L. Dann gilt ko w- 1 towko= w- a to w in G6, und dies 1N3t sich somit allein aus den Relationen in M herleiten. Also gilt die Gleichheit auch in H. Daraus folgt aber

~ k o w - i t o w k o z = f % w - l t o w k o d = w - l t o w d in H,

~ f % w - i t o w k o z = f w - l t o W Z = W - l t o d w = w - l t o w w ' d in H,

also w - l t o w d = w - ' t o w w ' d in H, also w'=e in H. Hoist als direktes Produkt der Jff-entscheidbaren Gruppen G und K selbst Jt ~-

entscheidbar. Wir wollen zweimal Satz 3.2 yon [-2] mit der ansehliegenden Bemerkung anwenden und zeigen, dag H 2 X-entscheidbar ist und Ho, also auch G, in H z ~)ff-eingebettet ist. Dazu muB gezeigt werden, dal3 die Untergruppen (Ai> und <Bi) von H i_ 1 (i = 1, 2) ~{'-entscheidbar sind und dab sich die Isomorphismen cI) i : < Ai) --* < Bi) und I~ i : ( Bi) ~ ( Ai) polynomial beschr~inkt realisieren lassen. Das gelingt mit Hilfe des folgenden Lemmas, dessen Beweis etwas l~inglich und sehr technisch ist und daher auf Kapitel 2 verschoben wird.

Lemma 1.3. <To, fr Toko> ist eine Jff-entscheidbare Untergruppe yon G6, und es gibt eine Jff-Funktion f . S6"-+S 6 mit

Subrekursive Komplexittit bei Gruppen. II 187

(a) ffir alle weS~ gilt f (w)=w in G6, (b) ffir alle we(To, koToko) gilt f(w)e(To, koToko)*,

(c) f i s t polynomial beschrtinkt.

Wir vereinbaren noch folgende Bezeichnung: Sind X und Y endliche Mengen mit X ___ Y, so ist IIx: _Y*---,X* die kanonische Projektion von Y* auf X*. Offenbar gilt Hx ~ ~.

Lemma 1.4. H1 ist ~-entscheidbar und H o ist durch die Identit~it in n 1 JY('- eingebettet.

Beweis. Es ist nach Satz 3.2 yon [-2] und der Bemerkung dazu zu zeigen, dal3 (A l> und (B~> ~-entscheidbare Untergruppen von H o sind, und dab sich die Isomorphismen 4~i: (AI>~(BI> und 431: (B1)---~(A1) durch eine polynomial beschr~inkte ~,~-Funktion realisieren lassen. Wir konstruieren zun~ichst eine Hilfsfunktion h, die ein Wort w~B_._~_~=(t (t E T), to, ko Toko)* in sein ~l-Bild aus (AI> =(tt ' (t~ T), to, koToko) umschreibt:

h(e)=e,

h (w t~o) - h (w) t~o,

h(w k~o) = h(w) k"o,

h . . . . . (h(w) ff falls w-UfCoV , v~T~ ~wt )=]h(w)(tt'y sonst.

Offenbar gilt h~oYg und h realisiert ~1 auf B~'.

Sei nun w~(S6w T')* und w I =Hs6(W), w2==-IIr,(w). Es gilt

w~(Bi>,~wi~(To, koToko) /X w2=e in K,

we(Al>,**,w1~(To,[coToko>/xw=h(f(wi) ) in H o.

Also sind (AI> und (BI> in Ho Jf-entscheidbar. Die Funktionen

(P 1, (9 1 : ($6 k..) T')* ~ (S 6 k..) T ' ) *

(~ f (wl ) sonstWE(A1)

(9 l(w)=_~h(f(w,)) we <Bl> Lw sonst

realisieren die Isomorphismen (A, > ~ (B 1 > und (B, > --* (A, >; sie liegen in ~ und sind polynomial beschdinkt, da f u n d h in 9ff liegen und polynomial beschr~inkt sind. Damit ist Lemma 1.4 bewiesen.

Lemma 1.5. H 2 ist ~-entscheidbar und H I i s t durch die Identit~it in H 2 ~ - eingebettet.

Beweis. Es ist H = H 2. Wie im Beweis zu Lemma 1.4 ist zu zeigen, dab die Untergruppen (A2> und (B2> yon H a 3ff-entscheidbar sind und dab sich die

188 J. Avenhaus u n d K . Madlener

I s o m o r p h i s m e n (J52: (A2)---*(B2) und q32: (B2)'--*(A2) polynomia l beschr~inkt realisieren lassen. Wir definieren wieder zun~ichst eine Hilfsfunktion h, die ein Wor t weA~=(T, to, f%Tk o, kotoko) * in das q~2-Bild yon w in ( B 2 ) = ( T , tod, koTko, kotoko d) umschreibt :

h (e) - e,

h(wt~)-h(w)t ~,

W ~, ( h ( ) t o falls w-ukov , v eT* h(wt~ sonst ,

h(wko)- h(w) ko, W i . . . . [h ( )kod falls w=-ukov, vE T~, H,o(v)-t~d...t~o "

ntW~Co)=~ . . . . - - ~ntW~o sonst, i=ex + ... +%

Offenbar gilt h e ~ ( und h realisiert 4~ 2 auf A__~. Es sei

we(SawT'w{d})* und wl-lIs~(W).

Wir zeigen

we(A2),e>wl e(To, koToko) A W=W x in H 1,

we(Bz)c* .wae(To, f%Toko) Aw=h(f(wO) in Ha.

Dann sind nach L e m m a 1.4 und 1.5 die Un te rg ruppen ( A 2 ) und ( B 2 ) off- entscheidbar.

Im Beweis zu L e m m a 1.2b) war schon gezeigt, dab der H o m o m o r p h i s m u s ~ : H a--*G6 mit ~ (d) = e, ~( t ' ) = e ftir t' e r ' und ~ (a) = a f'tir a e S 6 wohldefiniert ist und dab ~2 = ~[<s2> zu (])2 invers ist. Ist w e (A2) , so gibt es ein v s A ~ mit w = v in H 1 und

es gilt w 1 = ~P(w)= 7J(v)= v = w in H1, also w 1 e (Az) = ( T o, f:o Toko) und w =w~ in H~. Ist w~ e ( A 2 ) und w=wa in H~, so ist we(A2) . Ist wE(B2> , SO gibt es veB~ und v 1 eA* mit w=v in H a und w 1 = ~ ( w ) = 7~(v)= vl. Also ist w x ~ ( T o, koToko) und w=q~2(TJ(w))=q~z(WO=~2(f(wl))=h(f(wl)) in H a. Ist schlieBlich w = h(f(wO) in H1, so ist we(B2) , da alle h-Bilder in ( B 2 ) liegen.

Die Funkt ionen q~2, q32:($6 w T ' w {d})*---~(S 6 ~ T ' u {d})*

, , (h(f(wt)) w e ( A 2 ) ~02 tw~- ] w sonst

q)z(w)=-{fw (wl) sonstWe (B2)

realisieren die I somorph i smen (A 2 ) ~ (B z> und (B 2)--" (A 2), sie liegen in oU und sind po lynomia l beschr~inkt.

Aus den L e m m a t a 1.2, 1.4 und 1.5 ergibt sich nun unmit te lbar Satz 1.1.

2. Beweis zu L e m m a 1.3

G s und G 6 stellen dieselbe G r u p p e dar, man braucht nur die Erzeugenden t, k und to ,k 0 gem~ig to*--,(hp)-at(fzp) und ko~--~hkh zu vertauschen. Wir verlagern den


Beweis zu Lemma 1.3 in G 5 und betrachten t o und k o als W6rter t o-= (~p)-i t(hp), k o = h k h~S_~. Wir verwenden die Bezeichnungen aus Kapitel 4 yon [2], speziell ist S~ die Erzeugendenmenge und f die Reduktionsfunktion der Gruppe G~ (i = 0, 1 . . . . . 5). Wir zeigen

Lemma 2.1. Es sei t o = ( h p ) - X t ( h p ) u n d k o - h k h . Dann ist (T, to, ko) eine ~ - entscheidbare Untergruppe yon Gs, und es gibt eine :,~-Funktion f : S 5 ~S~_ mit folgenden Eigenschaften

(a) f0r alle w~S_~ gilt f ( w ) = w in G 5,

(b) ffir alle w ~ (T, to, ko) gilt f (w ) ~ (7, to, ko)* und f (w ) ist reduziert, (c) f i s t polynomial beschr~inkt, d.h., es gibt c, n e N , so dab fiir alle w sS_J_ gilt I f (w) l<c ' Iwl".

Aus Lemma 2.1 entnimmt man leicht, dab auch (To, ko Toko) )~-entscheidbar ist. Es gilt n~imlich

w s ( T o , k o T o k o ) c ~ E s gibt ui, vi~ T~ und

f (w) =- uokov 1 koux kovzko.., fCou, kov .

und wegen f s oU ist die rechte Seite oU--entscheidbar. Um die obige Aquivalenz zu zeigen, habe zun~ichst f (w ) die angegebene Gestalt. Dann liegt f (w) und wegen (a) auch w in (To, ko To k o). Gilt w ~ ( T o, ko To k0), so gibt es ein w ' ~ ( T o, ko To k o)* von

minimaler k-L~inge mit w = w ' in G 5. Dann ist w' k-reduziert. Wegen (b) ist auch f (w ) k-reduziert und aus w' = f (w) in G 5 folgt mit Lemma 3.1 von [-2], dab f die angegebene Gestalt hat.

Es reicht also, Lemma 2.1 zu beweisen. Beim Beweis von Lemma2.1 wird immer wieder von folgender Tatsache

Gebrauch gemacht: k-Pinche haben die Form k - ~w U mit w ~ ( R, x, q tq ) , und es gilt k - ~w k ~ = w in

G 5. t-Pinche haben die Form t -~wt ~ mit w ~ ( R , x ) , und es gilt t - ' w t ~ = w in G 4.

Beweis yon Lemma 2.1. Sei w ~ S_~_~ = (x, S, Q, R, t, k)*, k o = h k h, t o = (hp)- 1 t(hp). Gilt w s ( T , to, ko), so gibt es ein ve(T , to,ko)* mit v w = e in G 5. W~ihlt man v mit minimaler ko-L~inge, so ist v k-reduziert. Sei w '= - w o U 1 w l . . . U"w, (w i E S__~, e i = + 1) durch systematische Elimination der k-Pinche aus w entstanden. Dann ist w = w' in G 5, w' ist k-reduziert und Iw'l___<fwl. Weiterhin kann w' aus w durch eine oU- Funktion gewonnen werden (s. Kapitel 4 [2]).

Wir betrachten das auf S* definierte Pr~idikat P: "-'5

P ( w ) * : , w e ( T , to ,ko) in G 5.

Dann gilt wegen Lemma 3.1 von [2]

P(w)~,P(w')

"r162 Vo, Vl , . . . , VnGZ~':

1) v = v , ko'" . . .vxko~'Vo ist k-reduziert en 2) vnko '" . . .Vlko ' IVoWoU~Wl. . .k wn=e in G 5


�9 r Vo, Vl, ..., Vn~T~:

1) hvowo, hvl VoWoWl ..... hr,_ 1... VoWo... w,_ x ~ (R, x, 7:ttq)

2) Wo... w, e (T, to) in G 4.

Wit ftihren zun~ichst die auf S_.~ definierten Teilpfiidikate P' und P" von P ein

P'(u) ~*3vET~': hvu~(R,x, gttq) in G4,

P"(u)*>u~(To) in G 4

und suchen Funktionen f ' , f " auf $4" mit

f'(u)6T~' Ahf'(u)u6(R,x, qtq), falls P'(u)

und

f"(u)~T*Af"(u)=u in G4, falls P"(u);

dabei sollen if(u) und f"(u) frei reduziert sein. Dann gilt

n--1

P(w)~ /~ P'(wo...wi) /x P"(Wo...w,) i = 0

und die vi erh~ilt man mit Hilfe yon f ' und f " . Setzt man n~imlich vo-f'(wo),

vi-p(f'(Wo...wi)f'(wo...wi_l) -1) O<_i<_n

und

v,=-P(f"(Wo".w,) - l f ' (WO' ' 'Wn-- 1)-- 1)

(hierbei und im folgenden ist p die freie Reduktion), so l~igt sich die Funktion f definieren durch

f ( w ) - t ; ~ 1 7 6 1 7 6 sonst, falls P(w)

Sind P, f ' , f " in ~ , so ist auch f ~ : U und fiir alle w~S_~ ist f(w)=w in G 5 und f'tir w e < T o, ko> gilt

f(w)~(To, ko)* und f(w) ist reduziert.

Fiir die L~inge von f(w) gilt:

n 1

If(w)l<lw[+ 2 ~ If'(Wo...wi)l+lf"(Wo...w,)l. i = 0

Sind also f ' und f " polynomial beschfiinkt, so ist es auch f . Wir untersuchen nun das Pr~idikat P'. Fiir u e S_~ gilt

P'(u)*~veT~': hvue(R,x, Tqtq) in G 4

~.3VeTo*,y~(R,x, qtq)*: yhvu=e in G 4.

Gilt P'(u) und w~ihlt man v und y so, dab yhvu = e in G 4 und yhv minimale t-L~inge hat, so ist yhv t-reduziert. Welter kann man zu jedem u e s_S_~ durch einen ~-Prozel3 ein t-reduziertes Wort u' bestimmen mit u=u' in G 4 und [u'[<lul. Sei u ' = Uot~'Ul ...t~nu, (uieS_~ ~, ei= _1). Dann gilt

Subrekursive Komplexit~it bei Gruppen. II

P'(u)c:>P'(u')r veT~', ye(R,x , 71tq)*" yhvu'=e in G4

<:>3re<n; Vo .... ,v~e T_*, y . . . . . . y, eR*x mit

1) yhv-y,77t-~"qy,_t...y~_177t . . . . ~ - - ~ qymhvmto ...vlto~Vo ist t-reduziert

2) yhvu'=e in G 4

r m<n; v', v o, ..., vm e_T*; y,,, ..., y,_ 1 e R__~*:

1) hpvi...VoUo...ui~(R~) in G3 ( 0 < i < m )

2) ' - V ~-Um. . .UlV 0

3) - ' qyi.. .ymhvuo...ui~(R~) in G 3 (m<i<n)

4) hv'uo.. .u,e(R~).

Wir betrachten folgende auf S__~ definierte Teilpr~idikate von P ' :

P;(u)c*3v6T*: hpvue(Rx) in G3,

Pd(u)~3ye(R___z~)*: qyhue(Rx) in G3,

P~(u).*~3veT-*: hvue(Rx) in G 3.

191

Wir erhalten dann:

P~(u)<:~3 veT*, yeR__z~*" hpvuy=e in G 3

<~.3veT*, yeR___z~*" uy=v-afih in G 3

~ 3 v e T - * , Y e R x * ' f 3 ( u y ) = v - l ~ h in G 3.

Die rechte Seite der letzten Gleichung ist R-frei, d.h., u mug sich durch R- Elimination am Ende von u in ein R-freies Wort umformen lassen. Mit Lemma 4.7 und Lemma 3.1 yon I-2] sowie u'=-f3(u) schliel3en wir also weiter:

r veT_*, yeR___~x*" f3(uy) ist R-frei A f3(uy)=v-l~h in G 3

,croqueT-*, Wo, WleS._~_~; ieTZ: f3(g'(u'))=WofiW 1 Ahpvwofiwlxi=e in G 2

~3veT_*, Wo, WleS_~_~; ieTi:f3(g'(u'))=Wo~W 1AVwo=hwlxi=e in G1

.r w0, w 1 eS__.~_~; ieZ: f3(g'(u'))=Wol2Wl A IIs(Wo)e T*

A Fls(wo)=W 0 in G1 Af l (hwO=x i.

Also ist/'1' o~-entscheidbar. Es sei f~' e 6 ~ definiert durch

f~(u)=-{He s(w~ Pl(u'A f3(g'(u'))=--w~

Sei ge 8, die in 4.7 [2] eingeftihrte Funktion (R-Elimination am Anfang von u durch Multiplikation yon links mit Elementen aus R_~*) und g' sei definiert durch g , (u)=g(u- 1)- 1 f'tir ueS~. Dann ist g ' e g und g' f'tihrt die R-Elimination am Ende von u durch Multiplikation yon rechts mit Elementen aus R___z~* durch.

192 J. A v e n h a u s u n d K . M a d l e n e r

Dann ist f ; (u) e_T* frei reduziert und hpf; (u) u e (Rx) in G3, falls P; (u). Wir zeigen, dab f~' polynomial beschrhnkt ist: In der obigen Kette von ~iquivalenten Aussagen kann man o. B. d. A. y e Rx* frei reduziert, also auch R-reduziert w~hlen. Dann folgt lylR<l u- 1 v- 1/3hla = [u-~-R aus y = u - 1 v- lffh in G 3. Mit Lemma 4.5 [2] ergibt sich

t t If~'(u)1-117s(Wo x)L =lWo 1Is = If3(g (u))ls=lG(uy)ls

< luyls + (~ + 1)lUylR luyle < lUls + 2(~ + 1)lUlR lule

<3(~+l ) lu l 2.

Ganz analog wird das Pfiidikat P~ untersucht: FiJr u eS_~ und u' =f3(u) gilt

P~(u)'**'3 veT*: hvue <R~>'r 3 veT*: hvf3(g'(u'))e <x>

~ weS_~*; i, je2Z,: f3(g'(u'))-whx i/~ wz(T,x)*A f l(hlIs(W- 1)whxi)=-xJ.

Also ist P~ 8-entscheidbar. Sei f~ e ~ definiert durch

f~(u)={~e s(w-1) P~(u) A u~S~.

Wie bei f~ zeigt man, dab f~ p_olynomial beschriinkt ist, und wenn P~(u) gilt, so ist f~(u)eT* frei reduziert und hf~(u)ue(R~) in G 3. Fiir P~ gilt nun:

P~(u),c~3yeR___z~*" q y h u e ( R ~ ) in G 3

, ~ 3 y l , y 2 e R z * : qy lhuy2=e in G 3

,*~ P (u- 1 h).

Hier ist /5 das in Lemma 4.7 von [2] untersuchte 3f-Pr~idikat. P~ ist also 3f- entscheidbar.

Ffir P' ergibt sich jetzt mit u=u'=uot'~Ul...t""u, in G4 (u' entsteht durch systematische t-Reduktion aus u)

m - - 1 n - 1

P'(u)r /~ P;(Uo...Ui) A /~ P~(f~(Uo...u,)uo...ul) A P~(uo...u,). i = 0 i=m

Damit ist auch P' ~Gentscheidbar. Zur Definition yon if(u), falls P'(u) gilt, bestimmt man zunhchst m durch

m = # [ A P~(f;(uo...u.)uo...uj)] i n > j > i

und setzt dann vo-f~(uo), vi-p(f~(Uo...ui)f~(uo.. .ui_O -1) fiir O < i < m und vm- p(f~(Uo...u,) f ; (Uo...u,,_ 1)- 1).

Definiert man nun fiir u e S__~

f , , , (Vmto~Vm_l...t~"'Vo P'(U) t u ) = ~ e sonst,

dann ist f ' e Y{ und f ' hat die gewiinschten Eigenschaften, n~imlich f '(u) e TJ" ist frei reduziert, polynomial beschr~inkt und falls P'(u) gilt, ist hf'(u) u e (R, x, qtq) in G 4 �9


Es bleibt nur noch die Untersuchung von P" und die Definition von f " iibrig. Sei u6S__~ und u'-Uot~lul ...t'"u,, u=u' in G 4 wie oben. Dann gilt

P"(u)c~u~(To) in G 4

r in G 4

�9 r Vo, . . . . v n E T *

-'"...vlto~iVo ist t-reduziert 1) V, to 2) -~" -~ Vnt 0 . . .V l t 0 VoUote~Ul...te"Un=e in G 4

~ : ~ Vo, . . . ,vn~T_*

1) hpvi...VoUo...ui~(Rx) (O<i<n)

2) Uo...u,~(T) n- -1

�9 r /~ P;(Uo...ui) AUo...u,,~(T). i=O

Ffir u 6 S.~ gilt aber

u~(T) in G3.~ f~(f3(u)flr(f3(u)-l))-~e.

Da P; ~-entscheidbar war, ist auch P" ~-entscheidbar. Setzt man

Vo~_f;.(Uo), vi~-p(f;(Uo...ul)f;(Uo...ui_a) -1) (O<i<n)

v, =-p(Hr(f3(uo...u,)- t) f; (uo...u,_ 1)- 1) und

f,,(u)=~Vo lt~o'vll ...t~O~Vn 1 P"(u) sonst,

dann ist f " e X, polynomial beschr~inkt und ftir u mit P"(u) gilt f"(u)~Tg" und u = f " ( u ) in G4.

Somit ist auch P ~#-entscheidbar und die Funktion f hat alle in Lemma 2.1 geforderten Eigenschaften.

Literatur

1. Aanderaa, S.: A proof of Higman's embedding theorem, using Britton extension of groups. In: Word problems (W.W. Boone, F.B. Cannonito, R. Lyndon, eds.), pp. 1 - 17. Amsterdam-London: North Holland 1975

2. Avenhaus, J., Madlener, K.: Subrekursive Komplexit~it bei Gruppen. I. Gruppen mit vorgeschriebe- ner Komplexit~it. Acta Informat. 9, 8 7 - 104 (1977)

3. Gatterdam, R.W.: The computability of group constructions II. Bull. Austral. Math. Soc. 8, 2 7 - 6 0 (1973)

4. Higman, G.: Subgroups of finitely presented groups. Proc. Roy. Soc. London Ser. A 262, 455 - 475 (1961)

5. Machtey, M.: On the density of honest subrecursive classes. J. Comput. System Sci. 10, 183-199 (1975)

6. Mehlhorn, K.: Polynomial and abstract subrecursive classes. J. Comput. System Sci, 12, 147-178 (1976)

7. Rotman, J.J.: The theory of groups, 2nd ed. Boston: Allyn & Bacon 1973

Eingegangen am 12. April 1976

Documents

Subrekursive Komplexität bei Gruppen