Subrekursive Komplexität bei Gruppen

Acta Informatica 9, 87- 104 (1977) infUrmtica �9 by Springer-Verlag 1977

Subrekursive Komplexitiit bei Gruppen I. Gruppen mit vorgesehriebener Komplexitiit

J. Avenhaus und K. Madlener

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

Subrecursive Complexities on Groups I. Groups of Given Complexity

Summary. A finitely presented (f.p.) group has a .~-decidable word problem for a complexity class 3( if the group operations are 3(-functions. Using a construction of Boone and Britton [-153 we show that for two complexity classes 3( and 3( ' with 3( _= 3( ' a f.p. group can be constructed with 3(- but not 3('-decidable word problem.

As a consequence of this result it is shown that there is a f.p. E-decidable group with generalized word problem of

complexity 3(, there is no universal 3(-decidable f.p. group, there is a r.p. not ,;U-decidable simple group (3( ~ ~).

In den letzten Jahren haben seit der Arbeit von Rabin 1-14] Komplexit~itsfragen berechenbarer algebraischer Systeme eine immer gr013ere Bedeutung erlangt. Sie haben sich als besonders reichhaltig f'tir die Realisierung abstrakter Komplexi- t~itsklassen erwiesen.

Wir untersuchen in dieser Arbeit die Komplexit~it endlich dargestellter (e.d.) Gruppen. Will man in einer Gruppe G effektiv rechnen, so ist der natiJrliche Weg, die Gruppenelemente als W0rter (Produkte) in den Erzeugenden von G und deren Inversen darzustellen. Da diese Darstellung aber nicht eindeutig ist, w~ihlt man in der Aquivalenzklasse der W6rter, die das gleiche Gruppenelement darstellen, einen Repr~isentanten aus, etwa das lexikographisch erste Wort der )~quivalenzklasse. G heil3t berechenbar, wenn man zu je zwei Repr~isentanten u, v den Repr~isentanten re(u, v) des Produkts bestimmen kann. Man sieht leicht, dab dies ~iquivalent zur L6sbarkeit des Wortproblems ist, d.h. der Frage, ob ein gegebenes Wort das Einselement der Gruppe darstellt. Diese )kquivalenz gilt auch komplexit~itserhaltend. Ist 3( eine Komplexit~itsklasse, die die elementaren Funktionen g enth/ilt, so ist G genau dann 3(-berechenbar (d.h. m~3(), wenn das Wortproblem 3(-entscheidbar ist. Ist G3(-berechenbar, so ist auch die Inversenbildung ein 3(-Prozel3.

88 ~J. Avenhaus und K. Madlener

Boone und Novikov haben unabh~ingig voneinander gezeigt, daI3 das Wort- problem i.allg, rekursiv unl6sbar ist. In [2, 7] wurden dann e.d. Gruppen mit vorgegebenem Unentscheidbarkeitsgrad des Wortproblems konstruiert. Da man aber auch von einer ganzen Reihe yon Gruppen weiB, dab sie ein 16sbares Wortproblem haben (s. etwa Miller [13]), stellt sich die Frage nach geeigneten subrekursiven Komplexit~itshierarchien und nach der Einordnung bekannter Gruppen mit 16sbarem Wortproblem in diese Hierarchien.

Cannonito u. Gatterdam [5, 6, 9] haben gezeigt, dab es in jeder verallgemei- nerten Grzegorczyk-Hierarchie g,(A) fiir jedes n>4 eine e.d. Gruppe gibt, die g,(A)-, aber nicht ~,_ 1 (A)-entscheidbar ist.

Meyer u. Ritchie [12] und Machtey [11] haben die Grzegorczyk-Hierarchie erweitert und bewiesen, dab man die rekursiven Funktionen in dichte und unvergleichbare Hierarchien von zul~issigen Komplexit~itsklassen einteilen kann.

Wir zeigen in dieser Arbeit, dab zu je zwei zul~tssigen Komplexit~itsklassen o~ff und ~f', so dab ~ nicht in ~ ' enthalten ist, eine e.d. 3((-, aber nicht 3(('- entscheidbare Gruppe existiert und geben sie explizit an.

Bei bisher bekanntgewordenen Komplexit~itsuntersuchungen fiir Gruppen werden die Gruppenelemente in der Menge der nattirlichen Zahlen verschliisselt und es wird dann die Theorie der arithmetischen rekursiven Funktionen verwen- det. Diese Codierung ist unnattirlich und kann in unteren Komplexit~tsklassen (etwa unterhalb g) zu Verlusten ftihren.

Wir schlagen daher die Verwendung von Wortfunktionen vor [16] und glauben, dab sie die vorkommenden Algorithmen nattirlicher beschreiben und die Komplexit~itsuntersuchungen erleichtern.

Die Idee der Konstruktion einer e.d. Gruppe G mit X-, aber nicht ~ ' - entscheidbarem Wortproblem ist v611ig anders als die bei Cannonito und Gatterdam. Wir folgen der Idee von Boone und konstruieren zun~ichst eine Turing-Maschinen-Halbgruppe F, deren spezielles Wortproblem die gewtinschte Komplexit~it hat und aus C dann explizit die Gruppe G.

In einem zweiten Teil dieser Arbeit soll gezeigt werden, dab sich mit den angegebenen Methoden und Ergebnissen der Einbettungssatz yon Higman komplexit~itserhaltend iibertragen l~il3t: Zu jeder rekursiv dargestellten X-entscheidbaren Gruppe G l~il3t sich eine e.d. o~ff-entscheidbare Gruppe H angeben, in die G ,~-eingebettet ist. Zur Herleitung dieses Ergebnisses wird eine Beweis- idee yon Aanderaa [1] benatzt.

Die vorliegende Arbeit ist in vier Kapitel unterteilt. In Kapitel 1 werden die zul~issigen Komplexit~itsklassen eingeftihrt, ihre wichtigsten Eigenschaften und ihre Charakterisierung mit Hilfe von Turing-Maschinen angegeben. Dann wird eine T.M.-Halbgruppe mit speziellem Wortproblem geeigneter Komplexi- t~it konstruiert. In Kapitel 2 werden die ~-entscheidbaren Gruppen eingeftihrt und die Ergebnisse formuliert, die nach Bereitstellung einiger gruppentheoreti- scher Hilfsmittel in Kapitel 3 dann in Kapitel 4 bewiesen werden.

1. Zul~issige Komplexit~itsklassen und Turing-Maschinen-Halbgruppen

Es sei S = {si, ..., s.} eine endliche Menge. Wir bczeichnen mit S* die Mcnge aller W6rter fiber S und mit e das leere Wort. Wciter ist - die Identit~it auf S*

Subrekursive Komplexitiit bei Gruppen. I 89

und [w[ die L/inge yon weS*. Sind f u n d g zwei Funktionen von S*k--).S :g, so heigt f durch g beschr/inkt, falls [f(w 1 . . . . . Wk)[<=[g(w 1 . . . . . Wk) [ fiir alle w I . . . . . WkeS* gilt. Die kleinste Funktionenklasse ~v(S), die die Ausgangsfunk- tionen

e: S * 0 ~ S* K o n s t a n t e e,

pj:S*--*S* w ~ w s s j = l , 2 , . . . , n,

k . s , k _ . . ) . S : # (w1, W k ) - - 3 , W i 1 < i N k 7~ i . . . . ,

enth~ilt und abgeschlossen ist gegeniJber der Substitution, der primitiven Rekur- sion und der Minimierung, heiBt die Klasse der partiell-rekursiven Funktionen. ~ ( S ) = { f ~ v ( S ) : f total} heiBt die Klasse der rekursiven Funktionen fiber S (s. z.B. [16, 17]). Wir betrachten nur totale Funktionen.

Bekanntlich ist eine Wort-Funktion f auf S genau dann rekursiv, wenn sie auf einer deterministischen Turing-Maschine M=(So, Q, qo, T ) mit einem Ar- beitsband berechnet werden kann (S ~ So).

Eine Funktionenklasse ~r(S)c_~(S) heiBt Rechenzeit-abgeschlossen [12], wenn es zu jedem feJ{ ' (S) ein g e ~ ( S ) und eine Turing-Maschine (TM) gibt, die f berechnet und zur Berechnung von f ( w 1 . . . . . Wk) nicht mehr als [g(w 1 . . . . . Wk)[ Rechenschritte ben/~tigt. JU(S) heiBt eine zul~issige Komplexit~itsklasse, wenn sie Rechenzeit-abgeschlossen ist, abgeschlossen ist gegenfiber der Substitution und der beschr~inkten Rekursion und die Klasse g(S) der elementaren Funktionen enth~ilt. Beispiele flit zul~issige Komplexit~itsklassen sind die Grzegorczyk-Klas- sen g,(S) fiir n > 3 [16]. Weitere Beispiele sind die yon Meyer u. Ritchie [12] eingeffihrten elementar gutartigen Klassen und allgemeiner die yon Machtey [11] untersuchten gutartigen subrekursiven Funktionenklassen. Diese Klassen sind zun~ichst als Klassen arithmetischer Funktionen definiert, ihre wichtigsten Eigenschaften (sie liegen dicht, sie sch6pfen die rekursiven Funktionen ganz aus, es gibt unvergleichbare Klassen), lassen sich direkt auch fiir Wortfunktionen nachweisen.

Wir betrachten in dieser Arbeit nur zuliissige Komplexit~itsklassen und lassen daher den Zusatz ,,zul/issig" weg. Weiter schreiben wir kurz ~ statt ~(S), wenn S aus dem Zusammenhang bekannt ist.

Eine Menge L c_S* heiBt of-entscheidbar, falls fiir die charakteristische Funktion X/~o~f gilt. XL l~igt sich dann in einer Rechenzeitschranke g e ~ auf einer TM berechnen. Diese TM 15.Bt sich so modifizieren, dab sie bei Eingabe von weS* genau dann einen akzeptierenden Zustand q, annimmt, wenn weL gilt, und dab es zu jeder Konfiguration uqiv mit u, yeS*, qieQ ~-entscheidbar ist, ob aus der Konfiguration uqiv heraus der Zustand qa erreichbar ist. Diese Modifikation ist recht einfach, aber - wie bei T-Maschinen fiblich - nur Sehr umst~indlich zu beschreiben. Die Hauptidee besteht darin, den Arbeitsplatz auf dem Band durch Endmarken zu beschr~inken, so dab erkennbar wird, ob die Konfiguration uq~ v in eine Schleife ffihrt oder nicht. Aul3erdem wird ausgenutzt, dab Y Rechenzeit-abgeschlossen ist.

Ist M=(So, Q, q0, T) die so modifizierte TM zur Erkennung von L u n d ist qaeQ der akzeptierende Zustand, so liigt sich zu M in bekannter Weise [8] eine Turing-Maschinen-Halbgruppe F = ( S o wQ w {h, q}; 17) mit den endlich vielen

90 J. Avenhaus und K. Madlener

Erzeugenden So w Q w { h , q} und den definierenden Relationen H zuordnen. Dabei besteht H aus folgenden Relationen (So ist Leerzeichen von M)

qi Sk = q j St

qt Sk = Sk qj

qt h = s o qj h

St qi Sk = q j st Sk

hqt s k = hqj s o s k

q~ s t = q., s t q. h

h q . h = q ,

falls qi Sk Sl qj in T,

falls qi Sk Rq j in T,

falls qi So Rq j in T,

falls qt Sk Lq2 in T,

falls qi Sk Lqj in T,

= % h t'fir alle steSo,

H besteht also aus endlich vielen Relationen der Form F~ % G t = H iqt~ Kt mit Fi, Gt, H i, Kt~(S o w {h})*, qt,, qt~6Q w {q}. Es gilt - 2 =< ]FiGi] - [HiKt l <= 2.

Das folgende Ergebnis ist wohlbekannt, s. etwa [8] oder [15]: M erreicht aus der Konfiguration uqtv heraus den Zustand q, genau dann, wenn huqt vh =q in F gilt. Speziell gilt f'fir alle w~S*: w ~ L . c ~ h q o w h = q in F.

Wir definieren auf (S o w Q u {h, q})* das Pr~idikat P

P(w) r w = q in F.

P heiBt das spezielle Wortproblem yon F. Nach Konstruktion yon Mis t P.g#- entscheidbar. Es ergibt sich nun folgender Satz:

Satz 1.1. Sind • und ~ ' KomplexitMsklassen und ist L ~_ S* f - , aber nicht )ff'- entscheidbar, so gibt es eine Turing-Maschinen-Halbgruppe F = (S 1 w Q,;/7) mit S c S 1 und endlich vielen Erzeugenden und endlich vielen definierenden Relatio- nen, so dab das spezielle Wortproblem P yon F JY-, aber nicht 3(('-entscheidbar ist.

Man beachte, dab bei den oben angeffihrten Hierarchien (Grzegorczyk- Klassen, elementar gutartige Klassen, primitiv-rekursive Klassen) die Existenz einer 3(('-, aber nicht s(("-entscheidbaren Menge L gesichert ist, falls ,~ keine Teilklasse yon Off' ist [ l l , 12, 16].

Wir bemerken noch, dab f'tir Satz 1.1 nur die Rechenzeit-Abgeschlossenheit von 3(, nieht abet die von J ( ' ausgenutzt wurde. Die Rechenzeit-Abgeschlos- senheit wird im folgenden nicht mehr ben/Stigt. Hat man also eine T M - Halbgruppe F, f'fir die das spezielle Wortproblem ~{'-, aber nicht ~ ' -entscheidbar ist, so bleiben alle weiteren Uberlegungen richtig, auch wenn ~ und s/t" nieht Reehenzeit-abgesehlossen sind.

2. Hauptergebnisse

Es sei S e ine Menge, S={~-:seS} eine Kopie von S, S = S u S und A~_S_*. Mit ( S ; A ) bezeichnen wir die Gruppe, die durch die Erzeugenden S und die definierenden Relatoren A gegeben ist. Jedes Wort weS* stellt ein Element aus (S ;A> dar, Astellt das zu s inverse Element und e das Einselement dar. Stellen u, vQS* gleiche Elemente von (S; A> dar, so schreiben wir u = v in ( S ; A >.

Subrekursive KomplexitS.t bei Gruppen. I 91

Eine Gruppe G hat eine Darstellung (S; A), falls G~- (S; A) ist. G heil3t endlich erzeugt (e.e.) bzw. endlich dargestellt (e.d.), wenn S bzw. S und A endlich sind.

Im folgenden beschr~inken wir uns auf e.e. Gruppen. Mit - und -1 bezeich-

nen wir die B-Funktionen _S*--._S*, die durch sl s2 ... s, ---sl s 2 ... 3-,, gi-=Si und (S lS2 . . . s , ) -~=-~, . . . s2s t gegeben sind. Es sei o~ff eine Komplexit~itsklasse.

Definition 2.1. Die Gruppe ( S ; A ) heil3t X-entscheidbar, falls die Menge der Relatoren R = {we_S*: w = e in (S; A)} K-entscheidbar ist. Eine Gruppe G heil3t Y-entscheidbar, wenn sie eine ,~-entscheidbare Darstellung hat.

Das folgende Lemma zeigt, dab die o~-Entscheidbarkeit einer Gruppe unabh~ingig von der Darstellung ist.

Lemma 2.1. Ist G ~,%entscheidbar, so sind alle e.e. Darstellungen von G ~ff- entscheidbar.

Beweis. Nach Voraussetzung gibt es eine e.e. Darstellung ( S ; A ) von G, so dab die Menge R der Relatoren ~-entscheidbar ist. Da G isomorph zu (S; A) ist, gibt es eine surjektive Abbildung q~:S*-~ G mit

q~(uv) = q~(u) q,(v)

q~(u)=q~(v),~u=v in ( S ; A ) f'tir alle u, yeS*.

Sei ( T ; O ) eine zweite e.e. Darstellung von G, sei R' die Menge der Relatoren in (T; O) und ~ : T * ~ G die surjektive Abbildung entsprechend zu ~0. Dann gibt es zu jedem t e T ein wteS* mit O(t)=~o(wt). Sei f:_T*~_S* definiert durch

f(e) - e f (u t) - f ( u ) w t f (u ~) =-f(u) w;- 1.

Dann gilt I f ( u ) l ~ c . lul mit c=max{lwtl : teT} , also f e B . Weiter gilt O(u) = ~o(f(u)) ftir alle ue_T*. Daraus folgt ueR' r Da R ~-entscheidbar ist, ist es auch R'.

Man tiberlegt sich leicht, dab endliche, freie und alle Gruppen, fiir die Dehns Algorithmus anwendbar ist, ~ff-entscheidbar sind. Das direkte und das freie Produkt zweier ,XC-entscheidbarer Gruppen ist x(-entscheidbar.

Wir betrachten nur noch Gruppen, die durch Erzeugende und definierende Relatoren gegeben sind. Wir verwenden auch definierende Relationen, statt Relatoren, wo dies zweckmN3ig erscheint und behutzen die Bezeichnung G' =(G,S ' ;A ' ) , falls G = ( S ; A ) und G ' = ( S w S ' ; A w A ' ) ist.

Wir ftihren nun wie Rotman [15] eine etwas modifizierte Boone-Konstruk- tion durch und erhalten eine Gruppe, deren Wortproblem die gleiche Kom- plexit~it hat wie das Problem P in F.

Sei F = ( S u Q ; I I ) - S = S 1 w {h}, Q =Q1 ~ {q}-e ine rM-Halbgruppe mit den endlich vielen definierenden Relationen Fiqi~ Gi=Hiqi~ Ki; F i , Gi, Hi, KieS* , qi,, q i~Q ( i= 1, 2 . . . . . N). Ist R = {ra . . . . . rN} und sind x, t u n d k neue Symbole, so


werden die Gruppen Go bis G 5 wie folgt definiert:

Go=<X;~>, G 1 =<Go, S ;gxs=x 2 (s~S)>,

G2=<G1, Q;~J>,

G 3 =<G2,R;~ifflq~Giri=lqlqi~Ki,~isxri =s~(1 <i<N, ssS)>,

G4=(G3, t ;{x t=x, t r t=r (reR)>,

G 5 =(G4, k ;kak=a (a~{x, Kttq} uR)>.

Offenbar sind die Gruppen G O bis G 5 endlich dargestellt. Es gilt der folgende zentrale Satz, der im n~ichsten Paragraphen bewiesen wird:

Satz 2.1. a) Die Gruppen G O bis G 4 sind g-entscheidbar.

b) Das Wortproblem yon G 5 hat die gleiche Komplexitiit wie das spezielle Wortproblem P yon F; d.h., G s ist genau dann o~-entscheidbar, wenn P ~ - entscheidbar ist.

Geht man bei dieser Konstruktion yon einer TM-Halbgruppe aus, deren spezielles Wortproblem W-, aber nicht gf '-entscheidbar ist, so ist auch G s )if-, aber nicht ~('-entscheidbar.

Satz 2.2. Sind J~ff und o~ff' zwei Komplexitiitsklassen, und gibt es eine formale Sprache L, die ,~(-, aber nicht JY~'-entscheidbar ist, so gibt es auch eine e.d. Gruppe, die W-, aber nicht o~'-entscheidbar ist.

Wit untersuchen dieses Ergebnis etwas genauer im Fall der Grzegorczyk- Klassen ~,. Es ist bekannt [16], dab es t'fir jedes n__>3 eine formale Sprache L gibt, die g,-, aber nicht o~,_ 1-entscheidbar ist. Beim Beweis yon Satz2.2 wird nicht die Zul/issigkeit der Komplexit~itsklasse ~ ' ausgenutzt, man braucht nut, dab die ~'~'Entscheidbarkeit einer Gruppe unabh~ingig ist yon der Darstellung. Dies gilt, falls man ~2 ftir s ( ' w/ihlt. Man hat also

Satz 2.3. Zu jedem n__> 3 gibt es eine e.d. Gruppe, die d~ aber nicht ~,_ 1- entscheidbar ist.

Das verallgemeinerte Wortproblem ftir eine Gruppe G=(S;A> und eine Untergruppe H von G besteht darin, zu entscheiden, ob ein Wort we_S* ein Element aus H darstellt. Wir sagen dann: H ist in G entscheidbar. Der Beweis zu Satz 2.1 liefert folgende Versch~irfung des Resultats I yon Boone [2]:

Satz 2.4. a) Unter den Voraussetzungen von Satz2.2 gibt es eine e.d. g3- entscheidbare Gruppe G mit einer e.e. Untergruppe H, so dab H in G .~(-, aber nicht ~ff'-entscheidbar ist.

b) Zu jedem Unentscheidbarkeitsgrad D gibt es eine e.d. r Gruppe G mit einer e.e. Untergruppe H, so dab H in G vom Unentscheidbar- keitsgrad Dist .

Da man mit Hilfe etwa der elementar gutartigen Klasse die rekursiven Funktionen aussch6pfen kann [12], aber keine dieser Klassen gleich den rekursiven Funktionen ist, erh~ilt man mit Satz 2.2 einen neuen Beweis f'tir die Nicht- Existenz einer universellen e.e. oder e.d. entscheidbaren Gruppe; d.h., eine e.e.

Subrekursive Komplexit~it bei Gruppen. I 93

oder e.d. Gruppe, in der jede e.d. entscheidbare Gruppe eingebettet ist, kann nicht entscheidbar sein.

Machtey hat in [11] gezeigt, dab jede gutartige Klasse g ( # 8 3 sich als Vereinigung aller echt in ~" liegenden gutartigen Klassen darstellen 15_Bt. Man erh~ilt somit:

Satz 2.5. a) Es gibt keine universelle e.d. entscheidbare Gruppe.

b) Es gibt keine universelle ~,U-entscheidbare Gruppe, d.h., es gibt keine e.e. ~ - entscheidbare Gruppe, in der jede 3ff-entscheidbare Gruppe eingebettet ist.

Boone u. Higman [3] haben gezeigt, dab man zu jeder Gruppe G mit 16sbarem Wortproblem eine einfache Gruppe H und eine e.d. Gruppe K mit 16sbarem Wortproblem angeben kann, so dal3 G in H und H in K eingebettet ist. Es wird dort auch erw~hnt, dab H e.e. und rekursiv dargestellt gew~ihlt werden kann. Rekursiv dargestellte einfache Gruppen haben bekanntlich [3] 16sbare Wortprobleme. Aus Satz 2.2 folgt nun, dab sie nicht alle 3ff-entscheidbar sind

Ffir eine zul~ssige Komplexit~tsklasse ~ gilt nach Definition stets g3 ~ ~ . Auf Anregung des Referenten haben wir untersucht, ob die Konstruktion auch fiir kleinere Klassen durchftihrbar ist, etwa •r die polynomialen Klassen oberhalb yon ~2 (s. Mehlhorn [18]). Dies ist in der Tat m8glich, wenn man eine TM-Halbgruppe konstruiert, deren spezielles Wortproblem die geforderte Kom- plexit~t hat. Der Beweis wird jedoch etwas umst~ndlich, da sich die Komplexit~t der (noch einzufiihrenden) Reduktionsfunktionen fiir die einzelnen Britton-Er- weiterungen nicht mehr einheitlich mit Hilfe yon Satz 3.2 beschr~nken l~Bt. Vielmehr muB jede Reduktion einzeln polynomial beschr~nkt realisiert werden, bei der Gruppe G 1 durch geeignete Kodierung der x-Potenzen.

3. Gruppentheoretische Hilfsmittel

Es sei G = (S; A) eine Gruppe. Eine Funktion f:_S*--*S* ist eine Entscheidungs- funktion ftir G, falls gilt

f ( w ) = w in G,

f ( w ) - e, falls w = e in G.

Offenbar ist G genau dann 3ff-entscheidbar, wenn es eine Entscheidungsfunktion f ~ ftir G gibt.

c * {w] 1 . w , . w i ~ A , ei _+1} u n d ( A ) = { w e S * : 3 v E A * w Ist A _ S , so sei A*= '"" = = v in G}. (A) ist also die von A erzeugte Untergruppe, genauer: die Menge der W6rter, die ein Element aus der von A erzeugten Untergruppe darstellen. Ist G'= (S ' ;A ' ) eine weitere Gruppe mit S ~ S', so schreiben wir G < G', falls far alle weS* genau dann w = e in G' gilt, wenn w = e in G gilt, und sagen, Gis t in G' eingebettet. Ist weiterhin (S) in S'* 3(-entscheidbar, so ist G in G' 3ff-eingebettet.

Das wesentliche gruppentheoretische Hilfsmittel dieser Arbeit ist das Kon- zept der Britton-Erweiterung. Wir stellen hier einige Fakten zusammen, die spgter ben6tigt werden. Fiir fehlende Beweise sei auf [15] verwiesen.


Definition 3.1. Es sei G = ( S ; A ) eine Gruppe und P = {p~: ieI} eine Menge mit Pn_S=~; es seien weiterhin ftir alle ieI Teilmengen A~={aij: jeJ~} und B~ = {bij: jeJi} von _S* gegeben. Dann heil3t G'=(G,P;~iaijpi=bij , iel , J~Ji) eine Britton-Erweiterung von G mit stabilen Buchstaben P, falls ftir jedes ieI die von A~ und B~ erzeugten Untergruppen yon G unter der Abbildung 4)i(a~j)=bii isomorph sind.

Ist ue_S*, so heil3t ein Wort der Form p?~up~ ein Pinch, falls 5=1 und ue(A~) oder 5= - 1 und u~(Bi) gilt. Ist ~up~ ein Pinch, so gilt natiJrlich fiiupi =qSi(u ) in G'. Ein Wort we(_S~_P)* heil3t P-reduziert, falls es keinen Pinch als Teilwort enth~ilt.

Satz 3.1. Ist G' eine Britton-Erweiterung von G = (S; A) mit stabilen Buchstaben P und we(S_wP)* mit w=e in G', so gilt entweder weS* und w=e in G oder w enth~ilt einen Pinch als Teilwort. AuBerdem gilt G < G'.

Aus Satz 3.1 folgt unmittelbar

Lemma 3.1. Sei G' eine Britton-Erweiterung von G = (S; A) mit stabilen Buch- staben P, seien U-Uop]'u I . . . . p~Fu, und v=-voq~ ' .. qmrtmV,, (ui, vi~S*, Pi, qi eP, el, th = _+1) P-reduzierte W6rter und gelte u=v in G'. Dann gilt n=m, pi=q~ und 5 i =q~ f'tir i= 1, 2 . . . . . n und p ~ ' u o lvop], ist ein Pinch.

Definition 3.2. a) Seien Gi=(Si;Ai) , i=0, 1 . . . . . m Gruppen mit Si=S ~_ l WPi, so dab G~ eine Britton-Erweiterung von G~_ 1 mit stabilen Buchstaben P~ ist. Dann heiBt G O < G 1 < . . . < G,, ein Britton-Turm.

b) Ein Wort we_S* (i> 1) heil3t reduziert, falls es keinen Pinch p-~up ~ in Gj ( j<i) als Teilwort enthiilt.

c) Eine Funktion f~:_S* ~ S* (i > 1) heil3t eine Reduktionsfunktion ftir G~, falls f'tir alle wQS* gilt: (1)f/(w)=w in Gi, (2) fi(w) ist reduziert, (3)fi(w)=e, falls w=e in Gi und (4)fi(w)= w, falls w reduziert und nicht w = e in G i ist.

Eine Reduktionsfunktion f~ ftir G i ist also auch eine Entscheidungsfunktion von G~. Wir untersuchen nun, wann eine Britton-Erweiterung einer ~f'-entscheidbaren Gruppe wieder X-entscheidbar ist.

Definition 3.3. a) Eine Britton-Erweiterung G' von G = ( S ; A ) mit stabilen Buchstaben P = {pi:iel} heil3t X-zul~issig, falls ftir alle ieI gilt

1) (Ag) und (B~) sind .;f-entscheidbar in S*.

2) Es gibt gleichm~il3ig linear-beschr~inkte Funktionen ~0~, ~b~eo~f, die die Isomorphismen ( Ai) ~ ( Bi) und ( Bi) ~ ( Ai) realisieren.

b) Ein Britton-Turm G O < G 1 < . . . < G,, heil3t o~f'-zul~issig, falls G~ eine JY'-zul~issige Britton-Erweiterung von Gi 1 ist ( i= 1 . . . . . m).

Satz 3.2. Ist Go<G ~<.. .<G,. ein ~-zul~issiger Britton-Turm und ist Go oU- entscheidbar, so gibt es Reduk t ions funk t ionenf j e~ ffir G j, d.h., die Gruppen G~ sind ~-entscheidbar (j = 1 . . . . . m). Weiterhin ist G i in Gj f -e ingebet te t f'tir i <j.

Beweis. Der Beweis erfolgt durch Induktion nach j.

Subrekursive Komplexittit bei Gruppen. I 95

Sei j =0. Nach Voraussetzung ist G O 3(-entscheidbar. Bezeichnet p die freie Reduktion auf _S~' und setzt man

e w = e in G O fo(w) = p(w) sonst

so ist fo eine Jf-Entscheidungsfunktion f'tir G o. Weiterhin gilt: (1) fo(W)=W in Go, (2) fo(w) ist frei reduziert, (3)fo(w)=-e, falls w = e in Go, und (4) ist w frei reduziert und w # e in Go, so is t fo(w)=-w. D.h. fo hat die Eigenschaften einer Reduktionsfunktion. Sei j > 0 und fj_ 1 eine Reduktionsfunktion f'tir G j_ 1. Wir benutzen die Bezeichnungen von Definition 3.3 mit G ' = G j und G = G j 1. Zun~ichst wird eine Hilfsfunktion h auf S* definiert:

h (e ) - e ,

h ( w s ) - h(w)s seS_j_ 1,

h, , _ (vepi(u) h(w)=vpi u , twPO = ).h(w)p i sonst,

h'w -"-(vq31(u) h(w)-=vplu' PO=]h(w)~i sonst.

yeS*, u~S_ 7_ 1, ue(A,)

yeS_*, ueS* 1, ue(Bi)

Wir zeigen durch Induktion nach Iwl, dab Ih(w)l~2 ~lwl gilt. Ftir w = e ist diese Behauptung trivial. Der Induktionsschritt von w nach w x ist leicht, falls h(wx) = h(w)x ist. Wir betrachten nun den Fall h(wpi ) = v~oi(u). Es gibt, da die ~Pi, q3~ gleichmtil3ig linear beschr~inkt sind, ein c > l , so dab ffir alle iEI und alle ue_S*_ a I,pi(u)l__<c-lul und I~(u) l<clul gilt. Nach Induktionsvoraussetzung gilt Ih(w)l <2 ~lwl, also

Ih(wpi)f = Ivl + I~oi(u)l ~ [vl + clul ~ clv~iul

= c Ih(w)l ~ c2 clwl < 2 clwl +c = Ulwp, i.

Analog wird der Fall h(wFi ) =-v~bi(u ) behandelt. Da h durch beschdinkte Rekur- sion mit s(-Funktionen definiert ist, gilt dann h~,~.

Offenbar f'tihrt h die PiReduktion durch, d.h., h(w) ist Pfreduziert und h(w) = w in G'.

Definiert man fj durch fj(w)=-fj_l(Wo)P?fj_l(Wl).. .p~n"fj_l(Wn), falls h ( w ) - w o p]~ w 1 ~, ... p, w,, so priift man leicht nach, dab fj eine X-Reduktions- funktion ffir Gj ist.

Bemerkung. Die lineare Beschr~inktheit ist eine starke Forderung an die Funk- tionen ~oi, ~b~. Diese Forderung wird zwar bei den sp~iteren Anwendungen immer erfiillt sein. Es sei jedoch bemerkt, dab auch die polynomiale Beschr~inktheit als Voraussetzung ausreicht. Gilt n~imlich fiir, alle i~I, ueS*_alq~i(u)l<clul", IOi(u)J <clul", so gilt im obigen Beweis Ih(w)l <2 2~"rwl, d.h., h ist wieder durch eine a%Funktion beschr/inkt und somit h e ~ , also auch f i e f . Diese Bemerkung wird spiiter beim Beweis des Higmanschen Einbettungssatzes benStigt.


4. Beweis von Satz 2.1

Rotman [15] zeigt, dab die Gruppen Go . . . . . G 5 einen Britton-Turm bilden. Zum Beweis von Teil a) des Satzes 2.1 zeigen wir, dal3 der Turm Go<G 1 < ... ~ G 4 ~- ZuI~issig ist. Da G o als freie Gruppe g-entscheidbar ist, folgt die Behauptung dann aus Satz 3.2.

Wir benutzen folgende Bezeichnungen: S iist die Menge der Erzeugenden der Gruppe G i ( i=0,1 , . . . ,5) . Ist Tc:=S i u n d we_S*, so sei Iwlr (=Anzahl der Buchstaben von w aus T) die T-L~inge von w. ]'lr ist nattirlich eine g-Funktion. u~S* heil3t ein positives, u~ST* heiBt ein negatives Wort.

Lemma 4.1. Ftir i = 1, 2 ist G~ eine g-zul~issige Britton-Erweiterung von G~_ 1. Es gibt also eine Reduktionsfunktion f~E8 f'tir G~.

Der Beweis ist leicht und wird tibergangen.

Lemma 4.2. G 3 ist eine g-zul~issige Britton-Erweiterung yon G2. Es gibt also eine Redukt ionsfunkt ionf3~g f'fir G 3.

G 3 ist eine Britton-Erweiterung von G2 mit stabilen Buchstaben R = {r 1 . . . . . rN}. Mit den Bezeichnungen von Definition 3.1 gilt A~={~qi lG i, s i x . . . . . sux} , Bi = {Fliqi2Ki, sl~, .... SMY}. Es reicht zu zeigen, dab die Untegruppen <Ai) und <Bi) von G2 g-entscheidbar sind und dab es linear beschr~inkte Funktionen ~o~, ( b i ~ gibt, die die Isomorphismen ( A i ) ~ < B i ) bzw. <Bi)~<Ai) realisieren (i = 1, 2 . . . . . N). Zun~ichst ein vorbereitendes Lemma.

Lemma 4.3. Es sei we_S* und 1 < i < N . Ist w~<Ai) (bzw. w~<Bi)), so gibt es ein w'e_A* (bzw. w'e_B*) mit w=w' in G 2 und Iw'l _-<~lwl. Dabei ist ~= 1 +m ax {IFjGjl, IHjKjI: 1 < j < N}.

Beweis. Wir beweisen nur die Aussage fiber A~, die tiber B~ ergibt sich analog. Es sei T = { s l x , . . . , sMx } und

t _ _ - - ~ / ( . . . w =Vo(~q~,G3 vl (~q~iGi)""v., visT* ==-: VoD l q']~ Ely1 ... D,q'],T E, v,

ein Element aus _A* von ktirzester L~inge mit w=w' in G2: Wir zeigen zun~ichst, dab w' Q-reduziert ist: Enth~ilt w' einen Pinch ~ uq~, so enth~ilt es ein Teilwort u'-(~q~, G~) -1 vi(~q,, G,) mit u-F~ -1 v j ~ = e in GI, also u'=e in G2. Ersetzt man in w' das Teilwort u' durch e, so entsteht ein kiirzeres Wort, das auch gleich w in G 2 ist. Das ist aber ein Widerspruch zur Wahl von w'. Ebenso kann w' auch keinen Pinch q~ ucTi~ enthalten; also ist w' Q-reduziert.

Die vj sind S-reduziert: Enth~lt n~imlich v I einen S-Pinch, so enth~ilt es ein Teilwort sx~5 oder . ~ s x mit seS. Ein solches Teilwort kann aber weggelassen werden und damit verkfirzt sich v~, also auch w'. Das ist aber wegen der minimalen L~inge von w' nicht mSglich.

Ist vj~e, so ist Ejv~Dj+ 1 S-reduziert: Da v~ S-reduziert ist, kann ein S-Pinch nur auf der Grenze E~-v j oder vj-Dj+~ liegen. Da F~ und G i positive WSrter sind, ist D~+ 1 ein negatives und Ej ein positives Wort. Ein S-Pinch auf einer der Grenzen mtil3te also die Form sxY oder s23-haben. Dies sind aber keine Pinche.


Sei nun w" aus w dutch Reduktion entstanden

w"=f2(w)=--Uoq~l ~ u 1 ... q~"U,n , ujeS_*, qjeQ.

Da w' =w" in G 2 gilt und da w', w" Q-reduziert sind, folgt aus Lemma 3.1 m = n und ej=rlj, qj=qi, fiir j = 1 , 2 . . . . . n. Weiter folgt, dab qi-~"~UolVoDlq~ ein Q- Pinch ist, dab also u~ 1roD ~ = e in Ga und daher Uo=VoD1 in Ga ist. Setzt man Eo-Dn+~ =-e, so gilt uj=EjvjDj+~ in G1 ftir j = 0 , 1, ...,n. Wir zeigen, dab fiir die S-L~ingen IVjls<lUjls gilt. Fiir v j - e ist das trivial. Fiir v j ~ e ist EjvjDj+ 1 S- reduziert. Da auch uj als Teilwort des reduzierten Wortes w" S-reduziert ist, folgt aus Lemma 3.1 [ujls=lEjls+lvjls+lDj+lls, also [vjls<lujls . Aus der Ge- stalt yon w' entnimmt man

Iw'l~=lw'lo~lwlQ,

Iw'ls = ~ Ivjls + Iw'l~" I~q,l Gils < Z lujls + (~- 1)lw'le j=O j=O

= Iw"ls + (~ - 1)Iw"lQ __< Iwls + (~ - 1)Iwl~,

Iw'[<2 ~ Ivjls+lw'l&~<=2 ~ lujls+~lw'le j=O " j=O

= 2 Iw"ls + ~ Iw'% _-< ~(Iwls + Iwl~) _-< ~ Iwl,

Die Ungleichungen Iw"ls<lWls und Iw'le~fwlQ folgen aus w " - f 2 ( w ) und der Tatsache, dab bei der x, S- und Q-Reduktion durchf2 die S- und Q-Liinge yon w nicht gr6Ber werden k/Snnen. Nun ist [w'l<ctlwl gezeigt und Lemma 4.3 ist bewiesen. Man beachte auch, dab w' durch w eindeutig bestimmt ist.

Zum Beweis von Lemma 4.2 geben wir jetzt ein Entscheidungsverfahren fiir w e ( A i ) an und definieren dabei auch q~i. Das Entscheidungsverfahren f'tir w e ( B i ) und die Defni t ion von (Pi verlaufen analog.

Es sei weS* und

w"=-fE(w)=--uoq~lu I ... qn~" Un ujeS_*.

Weiter seien EjeS* und DjeS* definiert durch

Eo=--Dn+l =-e,

1 ~G~-I e j = - i J - ~ V / - 1 e j = - I j = l , 2 . . . . . n.

Wir benutzen die Bezeichnungen aus dem Beweis zu Lemma 4.3. Dort entnimmt man, dab w genau dann in (Ai> liegt, wenn q l - "'" =--qn--qil gilt und es WOrter Vo, Vl,...,vneT_* mit uj=EjvjDj+a in G 1 gibt. Zu testen ist also, ob E f l u j D f a l e ( T > gilt. Dazu definieren wir eine Funktion ga auf _S~' mit den Eigenschaften:

(a) g l ( u ) - v z w mit re_T* weS*, z neues Zeichen.

(b) Ist ueS* S-reduziert, so ist auch v S-reduziert, und es gilt g l (u ) -vzxJ .~ , u = v x j in G 1 ; speziell also u e ( T ) .~ g 1 (u) - v z.


(c) Igl(u)l~2 I"1, also g l s g .

Wir setzen g l ( e ) - z ,

g 1,, e~ f vZXj+~ I~'"X ) - - lg l (U)Xe

(VSXZX2J- 1 gl(us)-- lgl(u) s

f v~Y~z x j gl (us-)=-- ~ gl(u)g-

gl(U)=--VZX j j e7 l sonst,

gl(u) = vzx j j e Z sonst,

gl(u)=vzx2J- 1 j 6 Z

sonst.

Der Nachweis, dab gl die Eigenschaften (a) bis (c) hat, sei dem Leser fiberlassen. Mit gl k6nnen wir testen, ob die vj in ( T ) liegen und sie dann in W6rter aus

_T* umsehreiben. Zum Test, ob w in (Ai) liegt, und zur Umschreibung von w in w'~_Aj* definieren wir zwei weitere g-Hilfsfunktionen g2 auf_S* und g3.i auf_S*:

v gl (A (u ) ) - vz gz(u)- gl(fl(u)) sonst,

ga,i(w)=vo(~qlGi)~'Vl ...(ffiq, Gi)~"v, falls W=Uoq]lUl ... q~#u,

und vj =_ g2 (El 1 uj Dfl l ) .

Aus dem Beweis zu Lemma 4.3 folgt dann

w e ( A i ) , e ~ , g 3 , i ( f 2 ( w ) ) e ( S w {x, q6})*, w e ( A i ) :=~ g3,i( f2(w)) ~ w ' '

Damit ist also (Ai) g-entscheidbar und die Umschreibung von w e ( A i ) in w'e_A* m6glich. Die Umschreibung von w' in das entsprechende Wort aus B* ist einfach: Setze (Pi(w)= w, falls w r und

qki(W) ~ V'o(ffiiqizKi) E' V'l ... (fliqizKi)e"v'n,

falls w e ( A i ) und g3,i(f2(w)) =-w'- Vo(~qil Gi) ~l Vl ... (~qi, Gi)~"v, �9 Dabei entsteht vj aus v j, indem man x ~ durch x ~ ersetzt. Dann ist q'i eine g-Funktion, die den Isomorphismus ( A i ) ~ (Bi) realisiert. Zu zeigen bleibt, dab qh linear beschr~inkt ist. Wegen IHigil < I/~Gil +2 gelten fiir w e ( A i ) die Ungleichungen

I~odw)le = Iw'le < Iw[~,

I~oa(w)ls < Iw'ls + 2 Iw'le < Iwls + (~ + 1)Iwl~,

[~i(w)l <= Iw'l + 2 Iw'le < ~(Iwls + Iwlo) + 2 Iwl _-< (~ + 2)Iwl.

Speziell gilt fiJr alle w e_S~, 1 <i<-N die Ungleichung koi(w)l_-__(~ + 2)[w[, d.h., die ~ol sind gleichmaBig linear beschr~inkt und Lemma 4.2 ist vollstandig bewiesen.

Als Nebenresultat dieses Beweises erhalten wir noch

Lemma 4.4. Es gibt ftir i= 1, 2, ..., N auf_S~ definierte Funktionen h~, h leg mit

hi(w) = wxJe (A i ) hi(w) =- VjeTl:wxJf~(Ai) z VjeZ:wxJ(:_(Bi).

Subrekursive Komplexit~it be/Gruppen. I 99

Beweis. Wir konstruieren nur h/;/t i wird analog gebildet. Ist ue_s* S-reduziert, so gilt uxJe(T> genau dann, wenn g~(u) die Gestalt g ~ ( u ) - v z x -~ hat. Ist weS* reduziert und j # 0 , so gilt also wxJe(A/> genau dann, wenn g3,/(w) die Gestalt g 3 , i ( w ) - v z x -~ mit re(S1 w{qi~})* hat. Definiert man also

! we<A~> hi (w) - J g3,1(f2(w))=-vzx ~

sonst ve(S 1 k..) {q/l})*

so/st h/eine g-Funktion und hat die gewtinschte Eigenschaft. Zur sp/iteren Verwendung ben6tigen wir auch noch das folgende Lemma:

Lemma 4.5. Ftir die Reduktionsfunktion f3 von G gilt ftir we_s~

If3(w)ls < Iwls + (c~ + 1)IwlR" Iwlo.

Beweis. Wir verfolgen den Induktionsschritt von j = 2 nach j = 3 im Beweis zu Satz 3.2. Es wird zun~ichst eine Hilfsfunktion h auf_S] definiert durch

hie ) =- e,

h(wz) - h(w) z zeS_2,

_= S v h(w) - v?iu , h(wri)

{ h(w)r i sonst,

h(wfi)=~v~bi(u) h (w)-vr lu , (h(w)fl sonst.

ue_s,, ue<A/>

ue_s,, ue<Bi>

Mit Hilfe von h /s t dann f3 definiert durch

f3(w)=-fz(uo)r~fz(ul) . . , r~Sfz(u,), falls h(w) =_ Uori le, b l 1 . . . ri,~" u,.

Durch die x-, S- und Q-Reduktion in f2 kann sich die S-L~inge nicht verl~ingern, es gilt also [f2(uj)ls<l@s und damit If3(w)ls<lh(w)Js . Zum Beweis von Lem- ma4.5 reicht es also, [h(w)ls<lWls+filWlR. IwlQ zu zeigen. Dabei/st fl=c~+ 1.

Zun~ichst sieht man leicht: Hat h(w) die Gestalt h(w)=_vfiu, so 1/iBt sich w zerlegen in W - W o ~ W 1 mit h ( w o f 3 - v f i und h(Wl)=_u. Wir zeigen durch Induk- t/on nach Iwl

Ih(w)lo~lwlo Ih(w)ls~lwfs-+-~lwlo'lwlR

Fiir w - e / s t die Behauptung trivial und ftir h ( w z ) - h ( w ) z iibertriigt sie sich von w auf wz. Wir betrachten den Fall h(wri)-vq~i(u). Dann gilt h ( w ) - v ~ u , also w - WofiW 1 mit h(wofi) =- vfi und h(wO - u. Mit der Induktionsvoraussetzung und [q~i(u)lQ __< [u[~ und [~o~(u)[ s__< [Uls + fllulQ ergibt sich

Ih(wri)lQ = Ivle + I~oi(u)le < Iv~lo + lul~

= Ih(wo ~)le + Ih(w~)lo < Iwo~le + Iwlle = Iwlo = ]wrile,


Ih(wrl)ls = IVls + Iq~i(u)ls ~ Iv~ls + luls + ~lUIQ

= Ih(wo~)ls + Ih(wl)ls +/~lh(w 1)[~

_-_% Iwo~ils + IWlls+~(Iwo~ilRIwo~l~+ IwIlR" IWll~ + Iw~le)

< Iwls+13(IwlR+ 1)lw[Q=lwrils+~lwrilR" IwrilQ.

Analog wird der Fall h(w~)=v~i(u ) behandelt. Damit ist Ih(w)ls<lwls +/~lwl~. IwlR gezeigt und Lemma 4.5 ist bewiesen.

Lemma 4.6. G4 ist eine r Britton-Erweiterung von G3. Es gibt also eine Redukt ionsfunkt ionj4~8 ffir G4.

Beweis. G4 ist eine Britton-Erweiterung von G3 mit einem stabilen Buchstaben t. Ist A = B = R u { x } , so reicht es, zu zeigen, dab (A ) eine o~-entscheidbare Untergruppe yon G3 ist. Die Identit~t auf_S* realisiert n~imlich die Isomorphis- men ( A ) ~ ( B ) und ( B ) ~ ( A ) , sie ist eine r und linear beschr~inkt. Die Behauptung folgt dann aus Satz 3.2.

Es sei Rx=Rw{x} . Ist w~_S~ und w'- f3(w ), so liegt w, also auch w', genau dann in (A) , wenn es ein frei reduziertes Wort v~R~* gibt mit vw'=e in G2. In [-15] wird gezeigt, dab ein frei reduziertes Wort aus _R* auch reduziert in G3 ist. Wir suchen zun~ichst notwendige Bedingungen fiir we(A) . Ist w' nicht R-frei, so muB vw' einen R-Pinch ri~uor~ enthalten, der wegen der R-Reduziertheit yon v und w' nur auf der Grenze v - w ' liegen kann. Es gilt dann Uo~(Ai), falls e = l und Uo~(Bi), falls e= - 1 .

Gilt w'=uriw" mit u~_S*, d.h. u ist R-frei, so hat v die Gestalt V=VoF~X ~ mit j~Z, es ist Uo-XJU und Uo~(Ai), also auch u- lx -J~(Ai ) . Daher gilt hi(u-1)=-x-J und x -~ ist aus w' berechenbar. Es folgt w' =--uriw"=x-JririxJuri w'' =x-Jrl .q~i(xJu)w '' in G 3. Also ist ~oi(xJu)w"e(A), und es ist q~i(x~u)w '' R- reduziert und ]W'[R > kOi(XJU) w"ln.

Gilt w'=u~i w'' mit ue_S~, so gilt analog mit hi(u-~)=x-~: ~i(xJu)w"e(A), ~i(x ~ u) w" ist R-reduziert und IW'IR > I(~g(X~ U) W"IR.

Ist schlieBlich w' R-frei, so ist auch v R-frei, und es gilt w'=f3(w)=-x ~ mit jeTZ.

Entsprechend diesen Oberlegungen definieren wir g auf S~"

g (e) - e,

g(wy)-g(w)y y~S_2,

(wr,)_ (tpi(xJg(w)) g(w)~S~ /x hi(g(w )- 1 ) - x - J g " ='~g(w) r i sonst,

. . . . (~i(xJg(w)) g(w)~S~/x hi(g(w )- 1 ) - x - J g tw ri) = ~g (w) rii sonst.

Die Funktion g i s t ein Analogon zur Funktion gl, nut lieferte gl zugleich eine Umschreibung eines Wortes u ~ ( T ) in ein Wort v~T*. Die Umschreibung eines Wortes w~(A) in ein Wort w~A_* wird nicht ben6tigt.

Lemma 4.7. a) Es gilt g~5 ~. b) Es gibt ein u~_R* mit g(w)=uw in G 3.


c) Ist we_S] R-reduziert, so gibt es kein ue_R*, so dab ug(w) einen Pinch auf der Grenze u -g(w) enth~ilt.

d) Ist we S~R-reduziert und gilt g(w)=ur~v mit ueS_*, veS_~, so hat w die Gestalt w - u ' r f v mit u'~_S~.

Beweis. a) Es reicht, zu zeigen, dab ]g(w)l~(c~+2) rwl gilt, g also durch eine g- Funktion beschr~inkt ist. Im Beweis zu Lemma 4.2 wurde for xJue(Ai} die Ungleichung [q)i(xJu)l <(~+2)(IxJuls+ IxJule)=(~ +2)([Uls+ lu[ o) gezeigt. Der Beweis f'fir Ig(w)l<(~+2)lwl ergibt sich nun leicht durch Induktion nach Iwl. Ebenso beweist man die Aussagen b ) - d ) durch Induktion nach Iwl.

Aus Lemma 4.7 ergibt sich, dab ein R-reduziertes we_S~ genau dann in (A} liegt, wenn g(w) R-frei ist und in (x ) liegt. Ist n~imlich g(w)=x i in G3, so ist g(w)e(A)=(Rx} und nach 4.7b) auch we(A}. Ist we(A) , so ist nach 4.7b) auch g(w)E(A}. Nach 4.7c) und d) mug dann g(w) R-frei sein, also g(w)=x J in G2 gelten. Ffir ein beliebiges we_S~ gilt also

we(A) ,=,g(f3(w))s{x}*.

Also ist (A} d~ und Lemma 4.6 ist vollst~indig bewiesen. Von dem Hauptsatz 2.3 ist jetzt Teil a) bewiesen. Vor dem Beweis von Teil b)

geben wir ein Lemma an, das das auf S] definierte Pr~idikat P

P(u),ce,3Wl, W2e.._R*x:WlUW2=q in G 3

in Beziehung setzt zum speziellen Wortproblem P von F. Es zeigt sich, dab das Wortproblem in der Gruppe G5 auf/~ und dab P auf P zuriickgeftihrt werden kann. Damit ist G5 dann 3(-entscheidbar, falls P ~-entscheidbar ist.

Lemma 4.8. a) Es sei u~_S* reduziert und v =g(g(u)-l)-1. Dann gilt P(u)c:,v~S_* und/~(v). ~,

b) Es sei re_S* reduziert und es sei v' aus v durch Streichen aller x, ~ entstanden. Dann gilt

/5(v)r X, YES*, qjeQ: v ' - 2 q1Y A P(X qj Y).

c) Es sei X, YES*, q~eQ. Dann gilt

P(_~ qj Y),c~.P(X qj Y).

Beweis. a) Nach Lemma 4.7 gibt es Wl, w2eR._~ ~ mit u=wl uw 2 in G3, also gilt P(u),~P(v).

Die Richtung , ,~" ist jetzt trivial. ,,=-": Aus P(u) folgt /5(v), es gibt also reduzierte W6rter wl, w2eR_~,* mit wl vw2 =q in G3. Enthielte vein r, so enthielte wl vw2 gl nach Satz 3.1 einen R-Pinch, der wegen der Reduziertheit yon wl und w z nur ganz in v oder auf einer der Grenzen w l - v oder V-WE liegen kann. Auf den Grenzen kann er wegen Lemma 4.7c) nicht liegen und in v kann er nicht liegen, weil er sonst nach Lemma 4.7 d) auch in u liegen mtiSte, im Widerspruch zur Reduziertheit von u. Also enth~ilt v kein r, d.h. ve_S~.


b) Wegen der definierenden Rela t ionen S X S = X 2 gilt X 2i S = S X i in G 2 und S X 2i

=x~s in G2 (i~1~); man kann also x -Po tenzen von auBen in ) (q j Y hineinschie- ben. H a t v' die Gesta l t ' - " ' v ==-Xqj I1, so gibt es daher i,j~TI, so dab v = x ' v ' x J in G 2. Daraus folgt dann P(v)~a.P(v'). Die Richtung , , ~ " ist jetzt wieder trivial. , , ~ " : Wir zeigen, dab jedes ve_S~ mit if(v) die Gesta l t v - g l q j v 2 hat, wobei vl, v2e(Sva{x,~})* gilt, d.h. Vl, V2 nur posit ive s enthalten: Es gilt dann v ' = X q j Y mit X, YeS* und aus der Vort iber legung folgt P(v').

Nach Vorausse tzung gibt es reduzierte W/Srter Wl, w2eR_R~,* mit w I vw2 =q in G3. D a v R-frei ist, gilt twl[a=[W2]n . Wir f'tihren Induk t ion nach ]wlln. Ist ]WI[R =0 , SO gilt Wl =X i, W2=X j mit i, jc7l und wl vw2eS*. D a wl vw2 Q-reduziert ist, gilt nach L e m m a 3.2 ]wlvw2[Q=]VlQ=l, also v- -g lq jv2 mit vl, v2ES*. Aus x i ~ l q j v 2 x J = q in G2 folgt x~6~=e in G1 und VzXi=e in G1. Mit v sind auch zT~ und v2 reduziert, also gilt Vl=X i und v2=-x J, also Vl, v2e(Sw{x, ff})*. Es sei jetzt IW~]R>0, etwa wl =-w3 r f~x ~ mit a e Z , e = ___1. Wir bet raehten nur den Fall g = l , der Fall e = - i verl~iuft analog. D a n n gilt W2=xbr~wa mit be:~, WlVW2--w3Fix"vxbr lw4=q in G 3 und r-ix"vxOri ist ein R-Pinch, also x"vxbe(Ai ) . D a v Q-reduziert ist, gibt es ein weA* mit X~VXb=W in G 2 und [v]o=lw[o (s. den Beweis zu L e m m a 4.3). w'=-q~i(w) ist dann auch Q-reduziert, und es gilt w3w'w 4 = q in G 3. D a ]W3[R<[W,]R ist, gibt es nach Indukt ions- vorausse tzung y, ze(Svo {x, if})* und ein qjeQ mit w ' = y q j z in G 2. Da raus folgt Iw'le=lwl~=lvl~=l, also V=--fflqmV2 mit 1) l , U2~S_~, w=-ut(~qqGi)~u2 mit ua, u2eT*, T={sx : ssS}, und die u~ k6nnen als S-reduziert a n g e n o m m e n werden. Also gilt w'=(pi(ut)(HiqiKi)~qgi(u2), und aus w' - =yq~z in G z folgt e = 1, q i=qi~, ~=q)i(u~)ffIi in G1 und z=Kiqgi(u2) in G~. Mit u 2 ist auch ~o/(u2) also auch K iq~i(u2) S-reduziert. D a z nur positive s enth~ilt, ist z S-reduziert und nach L e m m a 3.2 kann ~o~(u~), also auch u2, nur positive s enthalten. Ebenso zeigt man, dab u~ nur negative s enthNt. Wegen x" VXb=W in G2 folgt nun x" gl qm vz xb = u~ ~ qi~ Gi/A2 in G2, also x ~ b~ = u~/~ in Ga und u 2 X b = G i u 2 in G~. D a v2 und G~u 2 S-reduziert sind und da Giu 2 n u r posit ive s enth~ilt, enth~ilt auch v z nur posit ive s. Ebefiso enthiilt g~ nur negative, v~ also nur positive s. Es gilt also v - g ~ % vz mit v~, Vze(Sw{x, ~})*.

c) Den Beweis findet man in [15], Seite 2 9 9 - 3 0 0 und L e m m a 12.18.

Wir nehmen jetzt an, dab das Pr~idikat P in F ~ - e n t s c h e i d b a r ist. Nach L e m m a 4.8 ist dann auch t5 ~ -en t sche idbar .

L e m m a 4.9. G 5 ist eine J{-zul~issige Br i t ton-Erwei terung von G4. Es gibt also eine Redukt ionsfunkt ion f5 ~ g ( f'tir G 5.

Beweis. G5 ist eine Br i t ton-Erwei terung v o n G 4 mit einem stabilen Buchstaben k. Setzt man / i = B = R ~ { x , 71tq}, so reicht es, zu zeigen, dab ( ,4 ) eine ~ - entscheidbare Un te rg ruppe v o n G 4 ist. Die Identit~it auf _S* realisiert die I somorph i smen ( / ] ) - -* ( /3) und ( / ~ ) ~ ( / ] ) und ist l inear beschriinkt.

Es sei weS* und w' =f4(w)=-Uo t ~1 Ul ...'t ~" u, mit uieS_*. Es liegt w, also auch w', genau dann in ( / ] ) , wenn es ein Wor t v - v t (qtq)"' ... Vl(qtq) ~' Vomit vi~R_~* gibt, so dab vw'=e in G4. W~ihlt man 1 minimal , so ist v t-reduziert, und es gilt n = l und r h = - e i ( i = 1 , 2 . . . . . n). Es gilt also w e ( A ) genau dann, wenn es


v o . . . . . v, eR_~* gibt mit

v,(qtq) ~"...vl(77tq)-~lVo. U o t ~ ' u l . . . t ~ " u , = e in G4.

Ist w e ( J ) , so mul l da v' und w reduziert sind, t -~ qvo Uo t ~' ein t-Pinch sein. Daraus folgt qvo Uoe(A) , also qVoUo=V ' in G3 mit v'eR__~*, also P(uo 1). Weiter folgt daraus (qtq) -~' Vo Uo t ~' =s Uo=Vo Uo in G3. Aus w e ( J ) folgt also

v,(Yltq) -~" ... v2(s Vo. UoUa t~2u2 ... t~"u,=e in G4

und P(u o 1) und schlieBlich

I)n.. .UlVO'lgOl.ll . . .Un~e in G 4

A / 3 ( U O 1) /k V((b/0 b / l ) - 1) A . . . A V ( ( u 0 b/1 . . . u n _ 1 ) - 1)

oder n--1

Uo u l . . . u . e ( . 4 ) A A P((Uo ul ... ui)- 1). i=0

Andererseits sieht man leicht, dab aus dieser letzten Bedingung auch die Existenz eines Wortes v in obiger Gestalt folgt, so dab v w ' = e in G 4. Damit gilt

n--I We(J)'C=>U 0 U 1 ... blne(A ) A A P((Uo Ul "" ui)- 1).

i=0

Das Pr~idikat rechts vom Doppelpfeil ist sf-entscheidbar, also ist auch w e ( A ) ~-entscheidbar und Lemma 4.9 ist bewiesen.

Wir haben jetzt gezeigt, dab das Wortproblem yon G 5 auf das spezielle Wortproblem yon F reduzierbar ist. Das folgende Lemma yon Boone liefert, dab umgekehrt das spezielle Wortproblem yon F auf das Wortproblem yon G s reduzierbar ist. Den Beweis findet man z.B. in [15].

Lemma 4.10 (Boone). Ffir X, YES*, q~eQ gilt Xq~ Y = q in F genau dann, wenn k ( X q j y ) - i t (Xq j Y) = ()(qj y ) - I t ( f , qj Y) k in G 5 gilt.

Also ist das Wortproblem von G s genau dann 3ff-entscheidbar, wenn das spezielle Wortproblem P von F Y-entscheidbar ist. Damit ist Satz 2.1 vollst~indig bewiesen.

Es bleibt noch Satz 2.4 zu beweisen. Dazu bemerken wir, dab die Gruppe G 4 g-entscheidbar ist, unabh~ingig v o n d e r Wahl der TM-Halbgruppe. H = ( A ) ist eine endlich erzeugte Untergruppe von G,~. Geht man von einer T M - Halbgruppe F aus, deren spezielles Wortproblem Jr-, aber nicht f ' - entscheidbar ist, so ist auch H.:U-, aber nicht Jg'-entscheidbar. Geht man von einer TM-Halbgruppe F aus, deren spezielles Wortproblem vom Unentscheid- barkeitsgrad D ist [2], so ist auch H vom Unentscheidbarkeitsgrad D.

Literatur 1. Aanderaa, S.: A proof of Higman's embedding theorem using Britton extensions of groups. In:

Word problems (W.W. Boone, F.B. Cannonito, R. Lyndon, eds.), pp. 1-17. Amsterdam- London: North Holland 1973

2. Boone, W.W.: Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups. Ann. of Math. 84, 49- 84 (1966)


3. Boone, W.W.: Between logic and group theory. In: Proc. 2. Internat. Conf. Theory of Groups (M. Newman, ed.), Lecture Notes in Mathematics, Vol. 372, pp. 90-102. Berlin-Heidelberg- New York: Springer 1974

4. Britton, J.L.: The word problem. Ann. of Math. (2) 84, 4 9 - 8 4 (1966) 5. Cannonito, F.B.: Hierarchies of computable groups and the word problem. J. Symbolic Logic 31,

376- 392 (1966) 6. Cannonito, F.B., Gatterdam, R.W.: The computability of group constructions, Part I. In: Word

problems (W.W. Boone, F.B. Cannonito, R. Lyndon, eds.), pp. 365-400. Amsterdam-London: North Holland 1973

7. Clapham, C.R.S.: An embedding theorem for finitely generated groups. Proc. London Math. Soc., Ser. 3, 17, 419-430 (1967)

8. Davis, H.: Computability and unsolvability. New York: McGraw Hill 1958 9. Gatterdam, R.W.: The Higman theorem for E,(A) computable groups. In: Conference on group

theory (R.W. Gatterdam, Weston, eds.), Lecture Notes in Mathematics, Vol. 319, pp. 71-74. Berlin-Heidelberg-New York: Springer 1973

10. Gatterdam, R.W.: The computability of group constructions. Part II. Bull. Austral. Math. Soc. 8, 27 - 60 (1973)

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

12. Meyer, A., Ritchie, D.: A classification of the recursive functions. Z. Math. Logik Grundlagen Math. 18, 71 -82 (1972)

13. Miller, C.F.: Decision problems in algebraic classes of groups. In :Word problems (W.W. Boone, F.B. Cannonito, R. Lyndon, eds.), pp. 507-523. Amsterdam-London: North Holland 1973

14. Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Amer. Math. Soc. 95, 341-360 (1960)

15. Rotman, J.J.: The theory of groups, 2nd ed. Boston: Allyn & Bacon 1973 16. Weihrauch, K.: Teilklassen primitiv-rekursiver Wortfunktionen. GMD Bonn, Nr. 91, 1974 17. Arbib, M.A.: Theories of abstract automata. Englewood Cliffs: Prentice Hall 1969 18. Mehlhorn, K.: Polynomial and abstract subrecursive classes, J. Comput. System Sci. 12, 143

- 178 (1976)

Eingegangen am 12. April 1976

Documents

Subrekursive Komplexität bei Gruppen