The Kolmogorov complexity of infinite words Abstract Electronic Colloquium on Computationa

TheKolmogorovcomplexityofinfinitewords󰀯

LudwigStaiger

Martin-Luther-Universit¨atHalle-Wittenberg

Institutf¨urInformatik

von-Seckendorff-Platz1,D–06099Halle(Saale),Germany

TheaimofthispaperistobrieflysurveyseveralresultsontheKolmogorovcomplexityofinfinitestrings.Wefocusonthoseresultswhichcanbede-rivedbyelementarymethodsfromtheKolmogorovcomplexityoffinitestrings(words)andcountingargumentsforsetsoffinitestrings(languages)ase.g.structurefunctionsandtheconceptofentropyoflanguages.

TheconceptofKolmogorovorprogramsizecomplexitywasintroducedinthepapersbySolomonoff[27],Kolmogorov[14]andChaitin[6]inthesixties(forthecompletehistoryseethetextbooksbyCalude[4]orLiandVit´anyi[15]).Itmeasurestheinformationcontentofa(finite)stringasthesizeofthesmallestprogramthatcomputesthestring,thatis,thecomplexityofastringistheamountofinformationnecessarytoprintthestring.

TheoriginalintentionofKolmogorovwastogiveanalternativeapproachtoinformationtheorynotdependingonprobabilitytheory.AfirstfactprovingevidenceofthisintentionwasP.Martin-L¨of’s[19]characterisationofinfiniterandomstrings.Roughlyspeaking,ifaninfinitestringisrandomthenmostofitsinitialwordshavemaximumKolmogorovcomplexity,thatis,havea

ISSN 1433-8092󰀀

complexitywhichisclosetotheirlength.Toputitintothecontextofinfor-mation,theamountofinformationwhichmustprovidedinordertospecifyaparticularsymbolofarandomsequenceisoneunitofinformation(e.g.onebitifweconsiderbinarysequences).

AlthoughKolmogorovwasinterestedmainlyinthecomplexityoffinitestrings,Kolmogorovcomplexitywasalsoappliedtoinfinitestrings.Hereitwascom-paredtoinformation-theoreticsizemeasures(ordimensions).Thesedimen-sionsarealsoknownfromfractalgeometry(see[10]).ItturnedoutthatsomeofthemarecloselyrelatedtoKolmogorovcomplexity.Whereasthepapers[8,9]giveanaccountontheKolmogorovcomplexityofsingleinfinitestrings,thepapers[2,3,23–25,28,31]setKolmogorovcomplexityofindividualinfinitestringsinrelationtothedimension(topologicalentropy,Hausdorffdimension)ofsetscontainingthesestrings.

ThefirstoneofthosedimensionsiscalledMinkowskiorbox-countingdimen-sion.Itisalsoknownunderseveralothernames(cf.[10]).TheothermeasuresaretheHausdorffdimensionandthepackingormodifiedbox-countingdimen-sion.

AnotherwaytoapproachKolmogorovcomplexityofinfinitestringsistofurtherpursuetheinvestigationofrandomness(see[4,15,26,38])andpar-tialrandomness[5,31,36].HerewehaveseveralcharacterisationsofrandomstringscombiningcomplexityormartingalesandorderfunctionsasinitiatedbySchnorr[26].Recentlytheconstructivisationofdimensionasin[1,16–18]gavenewinsightintotheseproblems.Thesepapersusetheconceptofso-calleds-gales,acombinationofmartingalesandexponentialorderfunctions.TheirrelationtoKolmogorovcomplexityisbasedonLevin’s[40]constructionofauniversalsemi-measure.ThecoincidenceofLutz’s[1,16–18]constructivedimensionandKolmogorovcomplexityofinfinitewordsisimmediatefromTheorem3.4of[40]andTheorem3.6[18].Foradetailedexplanationseealso[35].

InthispaperwefocusonresultslinkingKolmogorovcomplexityofsetsofin-finitestringstotheirdimensions.AmajorpointisthatweshowhowtoderivetheseresultsutilisingsimpleboundsontheKolmogorovcomplexityoffinitestringsandtransferthemfromlanguages(setsoffinitestrings)tosetsofinfi-nitestringsbymeansoflimitconcepts.Thisisdoneinanelementarymannerusingstructural(combinatorial)propertiesastheentropyoflanguages.Sim-ilarapproacheswerealreadypursuedinpartinthepapers[13]and[31,34].IncontrasttoHitchcock’spaper[13]whichusestheconceptofs-galesthepresentpaperisbasedonelementarypropertiesofKolmogorovcomplexityoffinitestrings.

WestartwithabriefaccountofKolmogorovcomplexityoffinitestringsand

2

theentropyoflanguagesinSection2.Then,inSection3,weproceedtothederivationofresultslinkingtheentropyoflanguagestodimensionsofsetsofinfinitestrings.Section4givesgeneralboundsonKolmogorovcomplexityofsetsofinfinitestringsbytheirdimensions.

Morepreciseboundsoncomplexityviadimensionforcertainclassesofsetsofinfinitestringsareobtainedutilisingstructuralproperties.InSection5wepresentresultsforsetshavingself-similaritypropertiesordefinedbycom-putabilityconstraints.

InthefinalSection6weintroduceanotherversionofcomplexityofinfinitestringsandpresentitsrelationtodimensionandKolmogorovcomplexity.

1Notation

Inthissectionweintroducethenotationusedthroughoutthepaper.ByIN={0,1,2,...}wedenotethesetofnaturalnumbers.LetXbeanalphabetofcardinality|X|=r≥2.ByX∗wedenotethesetoffinitewordsonX,includingtheemptyworde,andXωisthesetofinfinitestrings(ω-words)overX.SubsetsofX∗willbereferredtoaslanguagesandsubsetsofXωasω-languages.

Forw∈X∗andη∈X∗∪Xωletw·ηbetheirconcatenation.Thisconcatena-tionproductextendsinanobviouswaytosubsetsW⊆X∗andB⊆X∗∪Xω.

󰀆

ForalanguageWletW∗:=i∈INWi,andbyWω:={w1···wi···:wi∈W\\{e}}wedenotethesetofinfinitestringsformedbyconcatenatingwordsinW.Furthermore|w|isthelengthofthewordw∈X∗andpref(B)isthesetofallfiniteprefixesofstringsinB⊆X∗∪Xω.Weshallabbreviatew∈pref(η)(η∈X∗∪Xω)byw󰀛η,andη[0..n]isthen-lengthprefixofηprovided|η|≥n.AlanguageW⊆X∗isreferredtoasprefix-freeprovidedw󰀛vandw,v∈Wimplyw=v.

WedenotebyB/w:={η:w·η∈B}theleftderivativeofthesetB⊆X∗∪Xω.AsusualalanguageW⊆X∗isregularprovideditssetofleftderivatives{W/w:w∈X∗}isfinite.Inthesequelweassumethereadertobefamiliarwithbasicfactsoflanguagetheory.Asusual,theclassofrecursivelyenumerablelanguagesisdenotedbyΣ1,theclasscontainingtheircomplementsbyΠ1.Thus,Σ1∩Π1istheclassofrecursivelanguages.

WeconsiderthesetXωasametricspace(Cantorspace)(Xω,󰀮)ofallω-wordsoverthealphabetXwherethemetric󰀮isdefinedasfollows.

󰀮(ξ,η):=inf{r−|w|:w󰀁ξ∧w󰀁η}.

3

Thisspaceisacompact,andC(F):={ξ:pref(ξ)⊆pref(F)}turnsouttobetheclosureofthesetF(smallestclosedsubsetcontainingF)in(Xω,󰀮).Besidestheω-powerWωwedefinestilltwomoremappingstransforminglan-−→

guagestoω-languages,theδ-ori.o.-limitW:={ξ:|pref(ξ)∩W|=∞}andthea.e.-limitW↑:={ξ:|pref(ξ)\\W|<∞}.Itisimmediatethat

−−−−−−→−−−−−→−→

W↑⊆W⊆pref(W)=pref(W)↑andC(F)=pref(F)↑=pref(F).Moreover,wehave

−−−−−−−−−→−−→→

pref(V)∩V=Vand(pref(W↑)∩W)↑=W↑.

(1)

2

Kolmogorovcomplexityoffinitewordsandtheentropyoflan-guages

InthissectionwebrieflyrecalltheconceptofKolmogorovcomplexityoffinitewords.Foramorecomprehensiveintroductionseethetextbooks[4]and[15].Tothisendletϕ:X∗→X∗beapartial-recursivefunction.Thecomplexityofawordw∈X∗withrespecttoϕisdefinedas

Kϕ(w):=inf{|π|:π∈X∗∧ϕ(π)=w}.

(2)

Itiswellknownthatthereisanoptimalpartial-recursivefunctionU:X∗→X∗,thatis,afunctionsatisfyingthatforeverypartial-recursivefunctionϕ

∃cϕ∀w(w∈X∗→KU(w)≤Kϕ(w)+cϕ)

(3)

Ifoneconsidersonlypartial-recursivefunctionsϕwithprefix-freedomaindom(ϕ)⊆X∗weobtaininthesamewayanoptimalpartial-recursivefunctionC.

Proposition1ThereisapartialrecursivefunctionC:X∗→X∗withprefix-freedomaindom(C)suchthatforeverypartial-recursivefunctionsϕwithprefix-freedomaindom(ϕ)thereisaconstantcϕsuchthat

∀w(w∈X∗→KC(w)≤Kϕ(w)+cϕ).

Following[15]thecomplexityKCwillbecalledprefixcomplexity.

Athirdversionusefulforourconsiderationsistheconditionalcomplexity.LetA∈{IN,X∗},considerapartial-recursivefunctionψ:X∗×A→X∗andset

Kψ(w|a):=inf{|π|:π∈X∗∧ψ(π,a)=w}.

4

(4)

Againwehaveanoptimalpartial-recursivefunctionA:X∗×A→X∗satis-fyingthatforeverypartial-recursivefunctionψ

∃cψ∀w∀a(w∈X∗∧a∈A→KA(w|a)≤Kψ(w|a)+cψ).

Forthisconditionalcomplexitywehavethefollowingtwoproperties.ThefirstoneisTheorem1.2in[40](seealsoTheorem2.1.3in[15]).

Theorem2(Kolmogorov)LetM⊆X∗×AbearecursivelyenumerablesetsuchthateachsectionMa:={w:(w,a)∈M}isfinite.Thenthereisac∈INsuchthatK(w|a)≤logr|Ma|+cforalla∈Aandw∈Ma.ThenexttheoremisaslightextensionofTheorem2.9of[31].

Theorem3LetM,M󰀉⊆X∗×Aberecursivelyenumerablesetssuchthat

󰀉

eachsectionMa:={w:(w,a)∈M}isfinite,andlets:A→INbea

󰀉

recursivefunctionsatisfying|Ma|≤s(a).Thenthereisac∈INsuchthatK(w|a)≤logr(max{s(a)−|Ma|,1})+cfor

󰀉

alla∈Aandw∈Ma\\Ma.

PROOF.Weconstructafunctionψ:X∗×A→X∗suchthatKψ(w|a)≤

󰀉

logr(max{s(a)−|Ma|,1})foralla∈Aandw∈Ma\\Ma.

(t)󰀉LetMa⊆M∩M󰀉,t≤|Ma∩Ma|bethesetofthefirsttelementsoftheform(v,a)intheenumerationofM∩M󰀉.

Forinput(π,a)weenumerateMuntilwegett0:=max{s(a)−r|π|,1}elementsoftheform(w,a).LetπbetheqthelementofX|π|inlexicographicalorder.

󰀉(t0)

NowenumerateM󰀉untilqelementsinMa\\Maappearandputψ(π,a):=vwhen(v,a)isthisqthelement.

Aspecialcaseoftheconditionalcomplexityisthelength-conditionalcomplex-ity.Herewehaveapartial-recursivefunctionψ:X∗×IN→X∗andset

Kψ(w|n):=inf{|π|:ψ(π,n)=w∧|w|=n}.

(5)

Againwehaveanoptimalpartial-recursivefunctionL:X∗×IN→X∗satis-fyingthatforeverypartial-recursivefunctionψ

∃cψ∀w∀n(w∈X∗∧n∈IN→KL(w|n)≤Kψ(w|n)+cψ).

5

Thefollowingrelationbetweentheoptimalfunctionsisobvious.

KL(w||w|)≤KU(w)+c1≤KC(w)+c2

(6)

holdsforallw∈X∗andconstantsc1,c2dependingonlyonL,UandC.InthesequelweshallfixtheseoptimalfunctionsanddenotethecorrespondingcomplexitiesbyK(·|n),KandH,respectively.1

TheinequalitiesinEq.(6)canbe,tosomeextent,reversed(see[4,15]).

K(w||w|)+2·logr|w|+c1≥K(w)and

K(w)+2·logr|w|+c2≥H(w)

forallw∈X∗andsuitableconstantsc1,c2∈IR.

ForalanguageW⊆X∗defineitslength-structurefunction2sW:IN→INbysW(n):=|W∩Xn|anditsentropyas(cf.[7,12,31]),

HW=limsup

n→∞

(7)

logr(1+sW(n))

1

Thisfollowsthenotationof[4]whereas[15]usesCfortheusualcomplexityandKfortheprefixcomplexity.

2ThisfunctionisnottobeconfusedwiththeKolmogorovstructurefunctiondefinede.g.in[15,Section2.2.2].

6

Corollary6IfW∈Σ1∩Π1thenthereisac>0suchthat

∀w(w∈W→K(w)≤logr

󰀈|w|

s(i)i=0W

+c).

WeconcludethisintroductorysectionwiththeconsiderationofthesetsWα:=

{w:K(w)<α·|w|}.Asimplecountingargumentshowsthat

HWα≤αfor0≤α≤1.

(8)

Forcertainα∈[0,1]thesetsWαcanbeeffectivelydescribed.Tothisendwementionthatarealnumberα∈[0,1]iscalledleft-computable3provided{(p,q):p,q∈IN∧p

infBF=limn→∞dimBF=limsup

n→∞

logr(spref(F)(n)+1)logr(spref(F)(n)+1)

B

F=dimdimBF=

3

Thesenumbersarealsocalledsemi-computablefrombelow.

7

NextwerecallthedefinitionoftheHausdorffmeasureandHausdorffdimen-sionofasubsetof(Xω,󰀮)(seee.g.[10]).Inthesettingoflanguagesthiscanbereadasfollows(see[31,34]).ForF⊆Xωand0≤α≤1theequation

ILα(F):=liminf

l→∞

󰀃󰀈

r

−α·|w|

:F⊆W·X∧∀w(w∈W→|w|≥l)(9)

ω

w∈W

󰀄

definestheα-dimensionalmetricoutermeasureonXω.ILαsatisfiesthefol-lowing(ForatypicalplotofILα(F)asafunctionofαseeFigure1below.).Corollary9IfILα(F)<∞thenILα+ε(F)=0forallε>0.

ILα(F)∞

0

qILα0(F)

0

α0=dimHF

1

αE

Fig.1.AtypicalplotofILα(F)asafunctionofαwhen|F|=∞

ThentheHausdorffdimensionofFisdefinedas

dimHF:=sup{α:α=0∨ILα(F)=∞}=inf{α:ILα(F)=0}.ForthedefinitionofthepackingdimensiondimPweuseitscharacterisation

asmodifiedupperboxcountingdimension

dimMBF=inf{supi∈IN

B

F≤dimBF.

Everydimensionismonotone,thatis,E⊆FimpliesdimE≤dimFandshiftinvariant,thatis,dimw·F=dimF.Moreover

dimB(E∪F)=max{dimBF}and

󰀆

dim(i∈INFi)=supi∈INdimFifordim∈{dimP,dimH}

Thatis,theupperboxcountingdimensionisstable,andHausdorffandpack-ingdimensionarecountablystable.

8

Finally,wegiveaconnectiontotheentropyoflanguages(see[31]).Westartwithsomesimpleinequalities.

−→

dimHV≤HVdimW↑≤H

P

(10)(11)

W

−→

PROOF.InordertoproveEq.(10)weshowthatα>HVimpliesILα(V)=0.

Ifα>HVthenv∈Vr−α·|v|<∞.DefineV(i):={v:v∈V∧|pref(v)∩V|=i+1},thatis,V(i)isthesetofwordsinVhavingexactlyiproperprefixes

󰀆−→

inV.ByconstructionV(i)·Xω⊇V,andV=i∈INV(i)isadisjointunion.

󰀅−→

Now,Eq.(9)showsthatILα(V)≤v∈V(i)r−α·|v|.Thelattertendstozeroasiapproachesinfinity.

ToshowEq.(11)weobservethatW↑=w∈X∗EwwhereEw:={ξ:pref(ξ)⊆pref(w)∪(W∩w·X∗)}.Itisreadilyseenthat

󰀆

󰀅

α

.Thiscompletestheproofofthefirstidentity.

FortheproofofthesecondassertionitsufficestoshowthatdimPF≥inf{HW:

󰀆

F⊆W↑}.Westartwithacoveringi∈INFi⊇Fsatisfyingsupi∈IN

󰀆

dimBni=0Fi=max0≤i≤n

dimBFi=limi→∞

(1)nilogs(n)(2)rpref(Fi)dimBFi+2−iforalln≥ni.Thisispossible,because

n

.

NowdefineWinthefollowingway:W∩Xn:=pref(Fi)∩Xnforni≤nlogrsW(n)

n

≤

dimBFi≤dimPF+ε.

Lemma10provescloseconnectionsbetweentheHausdorffdimensionofan

−→

ω-languageandthelimitV,ontheonehand,andthepackingdimensionandthelimitW↑,ontheotherhand.InthenextsectionweshallprovesimilarconnectionsbetweentwoversionofKolmogorovcomplexityandthe

−→

limit-operationsVandW↑.

4GeneralboundsonKolmogorovcomplexitybydimensions

TheKolmogorovcomplexityofaninfinitewordξ∈Xωisafunctionk:IN→INmappingthen-lengthprefixξ[0..n]ofξtoitscorrespondingcomplexityK(ξ[0..n])(orH(ξ[0..n])orK(ξ[0..n]|n),respectively)(see[8]).Alargepartofinvestigationsdealswiththefollowingfirstorderapproximationsofthecomplexityofindividualω-wordsandsetsofω-words:

κ(ξ):=limsup

n→∞

K(ξ[0..n])K(ξ[0..n])

(F):=supκ

ξ∈F

(ξ):=liminf

n→∞

areindependentofthechosenword

complexityK,HorK(·|n).

WeobtainthefollowingconnectiontothelanguagesWα.

{ξ:κ

−→↑,(ξ)≤α}⊆Wγand{ξ:κ(ξ)≤α}⊆Wγ

forα<γ,areimmediatefromthedefinitions.

10

󰀇−→

Toshowthereverseinclusionsletξ∈γ>αWγ.Thenforeveryε>0thereareinfinitelymanyn∈INsuchthatK(ξ[0..n])<(α+ε)·n.Consequently,liminfw→ξK(ξ[0..n])

(F)andκ(F)similartotherelationbetween

entropyanddimensioninLemma10.ForthecaseW∈Σ1thislemmawasprovedin[13,Lemma5.5](seealso[1])inadifferentmanner.Lemma11κ

observethatEqs.(12)and(8)imply

κ

(F)∧γisleft-computable}

≥inf{HWγ:γ>κ

−→

(F)≥inf{HV:F⊆V∧V∈Σ1}follows.

Thecaseofκ(F)isprovedinthesameway.

HereLemma11provesasimilarconnectionbetweenlowerandupperKol-−→

mogorovcomplexityandthelimit-operationsVorW↑asLemma10didforHausdorffandpackingdimensions.Inthesequel,theseresultswillbeusedtoobtainboundsontheKolmogorovcomplexityofinfinitestringsviaHausdorfforpackingdimension.

4.1Lowerbounds

ItseemstobeanobviousmatterthatsimilartoCorollary4largesetscontaincomplexelements.Thisisestablishedbythefollowinglowerboundsonκ

Theorem12([24,1])dimHF≤κ

spref(F)(|w|)

=g(|w|)·

󰀅

|v|=|w|spref(F/v)(|w|)

B

F.

Theorem15IfF⊆Xωisbalancedandclosedthenthereisaξ∈Fsuchthat

K(ξ[0..n]|n)≥aedimHF·n−o(n).

12

4.2Upperbounds

AfterthederivationoflowerboundsontheKolmogorovcomplexityofinfinitewordsweturntoupperbounds.HereweneedsomecomputationalconstraintsonthesetF.Tothisendweintroducethelowclassesofthearithmeticalhierarchyofω-languages(seee.g.[22,32]).

Definition16(Π1-definableω-languages)F⊆XωisΠ1-definableifandonlyifthereisarecursivelanguageWF⊆X∗(WF∈Σ1∩Π1)suchthat

ξ∈F

←→

∀w(w󰀁ξ→w∈WF).

Definition17(Σ2-definableω-languages)F⊆XωisΣ2-definableifandonlyifthereisarecursivesetMF⊆IN×X∗suchthat

ξ∈F

←→

∃i(i∈IN∧∀w(w󰀁ξ:(i,w)∈MF)).

Theotherclassesaredefinedinasimilarway.Observethatwecanchar-acteriseseveralclassesbyrecursiveorrecursivelyenumerablelanguages(see[26,29,32]).

Lemma18FortheclassesΣ1,Π1,Σ2andΠ2ofthearithmeticalhierarchyofω-languagesinXωthefollowingidentitiesholdtrue.

Σ1={W·Xω:W⊆X∗∧W∈Σ1∩Π1}

Π1={F:Fisclosedin(Xω,󰀮)∧pref(F)∈Π1}Σ2={F:∃W(W⊆X∗∧W∈Σ1∩Π1∧F=W↑)}

−→

Π2={F:∃W(W⊆X∗∧W∈Σ1∩Π1∧F=W)}

OtherclassesofinterestarethefollowingoneswhicharedefinedsimilartothecharacterisationofΠ1inLemma18.

P={F:Fisclosedin(Xω,󰀮)∧pref(F)∈Π2}S={F:Fisclosedin(Xω,󰀮)∧pref(F)∈Σ1}

Figure2presentstheinclusionrelationbetweentheseclasses.Allinclusionsareproper,Σ2andSareincomparable,andΣ1isnotincludedinP.Forinstance,inExample1.15of[31]ω-languagesE∈S\\Σ2andF∈Π1\\Saregiven,andΣ1⊆PfollowsfromthefactthatPcontainsonlyclosedsets.Firstweobtainanexactestimateforκ

B(Σ2)

 d

d 

d 

Σ2

B(Σ1)

¨¨¨¨¨¨

Π2

P

Σ1

 d d  dd d d

Π1S

Fig.2.Inclusionrelationsbetweenvariousclassesofω-languages(B(K)denotesthe

closureofKunderBooleanoperations)

Theorem19IfF⊆XωisΣ2-definablethen

dimHF=sup{κ

(ξ)=1forallξ∈F,andκ(ξ)=0forall

ξ∈E\\F.

Thus,fortheω-languageEinLemma20wehaveκ(E)=1whereasdimHE=dimPE=0asEiscountable.ThisshowsalsothatthesetEgiveninLemma20isanotherwitnessforS\\Σ2=∅.ForsetsinSweobtainanupperboundviaCorollary5.Lemma21IfE∈SthenκSimilarlyoneobtainsthefollowing.Lemma22IfE∈S∪Π1thenκ(E)≤

(E∩F)=1.Consequently,

theboundsofLemmas21and22donotextendtoω-languagesoftheformE∩FwhereE∈SandF∈Π1.

14

B

E.

5

Kolmogorovcomplexityforω-powerlanguagesandregularω-languages

AsLemma20showedtheresultofTheorem19cannotbeextendedtohigherclassesofthearithmeticalhierarchy.IntheprecedingTheorem15wesawthatstructuralpropertiesmightleadtotighterlowerbounds.Inthissectionclassesofω-languageswhichallowformorepreciseboundsarepresented.

5.1ω-powerlanguages

Thefirstclassisconnectedtoω-languagesexhibitingacertainkindofself-similarity,namely,ω-languagesF⊆Xωcontaining,foracertainsetofwords

󰀆

W⊆X∗alloftheshiftsw·Fwherew∈WinsuchawaythatF=w∈Ww·F.Amongtheseω-languagesthemaximaloneshavetheformWω(see[33]).Theysatisfythefollowingproperties.

−−→

Proposition23LetW⊆X∗.ThenWω⊆W∗⊆C(Wω).

ItisalsoobviousthatWωisclosedifWisfinite,andWωisintheBorelclassΠ2ifWisprefix-free.Onecannot,however,boundthetopologicalcomplexityofsetsoftheformWωasFinkel[11]showedthatforeveryi∈INthedifferenceoftheBorelclassesΠi+1\\Πicontainsanω-powerlanguagesWωwhereWisacontext-freelanguage.

Eq.(6.2)of[31]andCorollary3.9of[10]givethefollowingformulaeforHausdorffandpackingdimension.Proposition24dimHWω

−−→

=dimHW∗=HW∗

dimPC(Wω)=

ThenextcorollaryfollowsalsofromTheorem12andProposition24.Corollary27κ(Wω)≥

dimBWωifW∈Σ1

Proposition24andLemma11yieldasimilarestimateforκ

(Wω).

(13)

5.2Regularω-languages

Theclassofregularω-languagesistheonewhichismostextensivelyinvesti-gated,becauseitistheclassofω-languagesdefinablebyfiniteautomata(cf.[32,37]).Asweshallseebelow,thisclassbehavesmostregularlyalsoincaseofcorrespondencesbetweencomplexityanddimension.

Werefertoanω-languageF⊆Xωasregularprovidedthereareann∈INandregularlanguagesWi,Vi,i=1,...,nsuchthat

F=

󰀁n

ω

W·V.iii=1

Itisknownthatallregularω-languagesareinB(Σ2).

Firstwementionpropertiesofregularω-languageswithrespecttodimensions

whichcanbefoundin[31,Corollary4.4].

Proposition29IfF⊆Xωisaregularω-languageclosedin(Xω,󰀮)thendimHF=

dimBWω.

Thisyieldsthefollowingasacorollary.

Corollary31IfF⊆Xωisaregularω-languagethendimHF=dimPF.

16

ωω

PROOF.Observethatdimni=1Wi·Vi=max{dimVi:1≤i≤n}holdsfordim∈{dimH,dimP}.NowtheassertionfollowswithCorollary30.

󰀆

Regularω-languageshavenon-nulldimH-dimensionalmeasure.

Theorem32([31,Theorem4.7])LetF⊆Xωbeanonemptyregularω-language.ThenILdimHF(F)>0.

ThisenablesustoapplyTheorem13toobtainlowerboundsonthecomplexityfunctionforω-wordsinregularω-languages.Moreover,wecanalsotransferP.Martin-L¨of’sresult[20]oncomplexityoscillationsinXωtoallnonemptyregularω-languages(see[31,Theorem4.12]).Theorem33LetF⊆Xωbenonemptyandregular.

(1)Iff:IN→INsatisfiesn∈INr−f(i)<∞thenthereisaξ∈Fsuchthat

K(ξ[0..n]|n)≥aedimHF·n−f(n).

󰀅

(2)Iff:IN→INisarecursivefunctionandsatisfiesn∈INr−f(i)=∞then

K(ξ[0..n]|n)≤iodimHF·n−f(n)holdsforallξ∈F.Agenerallinearupperboundonthecomplexityfunctionforω-wordsinregularω-languagesisthefollowingone(cf.also[28,31]).

Theorem34(1)LetW⊆X∗bearegularlanguage.IfdimHWω>0

thenthereisaconstantcW∈IRsuchthatforallξ∈WωtheboundK(ξ[0..n])≤aedimHWω·n+cWholds.

(2)LetFbearegularω-languagesuchthatdimHF>0.Thenforevery

ξ∈Fthereisaconstantcξ∈IRsuchthatK(ξ[0..n])≤aedimHF·n+cξ.

󰀅

PROOF.SinceWisregular,pref(Wω)isalsoregular,thuspref(Wω)∈Σ1∩Π1.AccordingtoProposition2.15of[31]thereisaconstantc∈IRsuchthatspref(Wω)(n)≤c·rα·nforα=Hpref(Wω)andalln∈IN.Consequently,󰀅n󰀉α·(n+1)

forasuitableconstantc󰀉∈IR.Now,ourfirsti=0spref(Wω)(i)≤c·r

assertionisaconsequenceofCorollaries6and30.Thesecondonefollows,becauseξ∈F=forsuitablei∈{1,...,n}andwξ,i∈Wi.

󰀆n

i=1

Wi·Viωimpliesthatξ∈wξ,i·Viω

ThetheoremdoesnotholdfordimHF=0.Inthiscasewehave,inviewofProposition4.12of[31]thataregularω-languageofHausdorffdimension0iscountableandconsistsentirelyofrecursiveω-words.

17

6Subwordcomplexity

ItwouldbedesirabletohaveananaloguetoLemma11forregularlanguages.ForregularlanguagesV⊆X∗,however,theidentityHV=Hpref(V)istrue.

−→

InconnectionwiththefactthatF⊆Vimpliespref(F)⊆pref(V)we

−→

obtaintheidentityinf{HV:F⊆V∧Visregular}=inf{HV:pref(F)⊆pref(V)∧Visregular}.

Consequently,sinceeverydensesubsetFofXωhaspref(F)=X∗,theinfi-mumis1forarbitrarydensesubsetsofXω.

Butifwerestrictourselvestosingleω-wordsweobtainavariantofcomplexity,thesocalledsubwordcomplexity.Itturnsoutthatthissubwordcomplexityτ(ξ)ofastringξ∈XωisalsocloselyrelatedtotheHausdorffdimensionoftheregularω-languagescontainingξ.Westartwithsomedefinitions.Let

infix(ξ):={w:w∈X∗∧∃v∃ξ󰀉(v·w·ξ󰀉=ξ)}andinfix∞(ξ):={w:w∈X∗∧∀n∃v∃ξ󰀉(|v|≥n∧v·w·ξ󰀉=ξ)}

(14)(15)

bethesetofsubwordsofξandthesetofsubwordsoccurringinfinitelyofteninξ,respectively.Wecallτ(ξ):=Hinfix(ξ)thesubwordcomplexityofthestringξ∈Xω.

Thenthefollowingidentityholds(cf.[31,Section5])Lemma35

τ(ξ)=Hinfix(ξ)=Hinfix∞(ξ)=inf{dimHF:Fisregular∧ξ∈F}

=inf{

andκtothisnewcomplexitymea-sureforinfinitestrings.

κ

,κ,τ}

(η)(η)Eα:={ξ:η(ξ)≤α}andFα:={ξ:η(ξ)<α}.

(17)

18

ThesetsE(κ

,κ,τ}

(τ)(κ)Eα⊆Eα⊆E(κ

α)

(18)(19)

(η)(η)ItshouldbementionedthatLemma3.4of[3]showsFα⊂Eαforη∈{κ

,κandτcanbeobtainedfromtheresultsof

[23]or[3]andLemma35.

(η)(η)Theorem36EachofthesetsEα,Fα,bbwhereη∈{κ

α

)

.

Theorem12showsdimHE(κ(ξ)≤α}≤α.

(τ)Inordertoshowα≤dimHFα=dimH{ξ:ξ∈Xω∧τ(ξ)<α}itsufficestoconstructacountableunionofregularω-languagesFi⊆{ξ:ξ∈Xω∧τ(ξ)<α}suchthatsup{dimHFi:i∈IN}=α.

LetMα:={(p,q):p,q∈IN∧q=0∧

p

.TheninviewofLemma35wehaveq

Xω∧τ(ξ)<α},andourassertionfollows.

󰀆

(p,q)∈Mα

F(p,q)⊆{ξ:ξ∈

(η)

SinceEα󰀃⊂Fα,forα󰀉<αweobtainasacorollarytoTheorem36and

(η)(η)

Lemma3.4of[3]thatthefamilies(Eα)α∈[0,1]and(Fα)α∈[0,1]formstrictlyincreasingchainsofω-languages.

(κ)

Whatconcernsthepackingdimension,Theorem12showslikewisedimPEα=

(τ)(τ)

dimP{ξ:ξ∈Xω∧κ(ξ)≤α}≤α.Thus,inviewofα=dimHFα≤dimPFαandEq(19),weobtainalsothefollowing.

(η)(η)

Lemma37EachofthesetsEα,Fα,whereη∈{κ,τ},haspackingdi-mensionα.

(η)

Lemma37,however,doesnotholdforκ

(ξ)=0}=1.

19

References

[1]K.B.Athreya,J.M.Hitchcock,J.H.Lutz,andE.Mayordomo,Effectivestrong

dimension,algorithmicinformation,andcomputationalcomplexity.InProc.21stSymposiumonTheoreticalAspectsofComputerScience,Springer-Verlag,Berlin,2004,632–643.[2]A.A.Brudno,Topologicalentropy,andcomplexityinthesenseofA.N.

Kolmogorov.(Russian)UspehiMat.Nauk29(1974)6(180),157–158.[3]J.Cai,andJ.Hartmanis,OnHausdorffandtopologicaldimensionsofthe

Kolmogorovcomplexityoftherealline.JournalofComputerandSystemsSciences,49(1994),605–619.[4]C.S.Calude.InformationandRandomness.AnAlgorithmicPerspective,2nd

Edition,RevisedandExtended,SpringerVerlag,Berlin,2002[5]C.S.Calude,L.StaigerandS.A.Terwijn,Onpartialrandomness.Ann.Pure

andAppl.Logic,138(2006),20-30.[6]G.J.Chaitin,Onthelengthofprogramsforcomputingfinitebinarysequences,

J.Assoc.Comput.Mach.13(1966),547-569.[7]N.ChomskyandG.A.Miller,Finite-statelanguages,Inform.andControl1

(1958),91-112.[8]R.P.Daley,Theextentanddensityofsequenceswithintheminimal-program

complexityhierarchies,J.Comput.SystemSci.9(1974),151-163.[9]R.P.Daley,Minimal-programcomplexityofpseudo-recursiveandpseudo-randomsequences.Math.SystemsTheory9(1975)1,83–94.[10]K.Falconer,FractalGeometry.Wiley,NewYork,1990.

[11]O.Finkel,Topologicalpropertiesofomegacontext-freelanguages,Theoret.

Comput.Sci.262(2001),669–697.[12]G.Hansel,D.Perrin,andI.Simon.Entropyandcompression,in:STACS’92,

A.FinkelandM.Jantzen(Eds.),Lect.NotesComput.Sci.,Vol.577,Springer-Verlag,Berlin1992,515–530.[13]J.M.Hitchcock,Correspondenceprinciplesforeffectivedimension.Theory

Comput.Systems38(2005),559–571.[14]A.N.Kolmogorov(1965),Threeapproachestothequantitativedefinitionof

information,ProblemyPeredachiInformatsii1(1),3-11.[Russian][15]M.Li,andP.M.B.Vit´anyi,AnIntroductiontoKolmogorovComplexityandits

Applications,2ndedition,Springer-Verlag,Berlin,1997.[16]J.H.Lutz,Galesandtheconstructivedimensionofindividualsequences,

InProc.27thInternationalColloquiumonAutomata,Languages,andProgramming,Springer-Verlag,Heidelberg,2000,902–913.

20

[17]J.H.Lutz,Dimensionincomplexityclasses,SIAMJournalonComputing,32

(2003),1236–1250.[18]J.H.Lutz,Thedimensionsofindividualstringsandsequences,Inform.and

Comput.187(2003),49–79.[19]P.Martin-L¨of.Thedefinitionofrandomsequences,Inform.andControl9

(1966),602–619.[20]P.Martin-L¨of.Complexityoscillationsininfinitebinarysequences,Z.

Wahrscheinlichkeitstheorieundverw.Gebiete19(1971),225-230.[21]C.A.Rogers,HausdorffMeasures.CambridgeUniversityPress,1970.[22]H.Rogers,TheoryofRecursiveFunctionsandEffectiveComputability,McGraw

Hill,NewYork1967.[23]B.Ya.Ryabko,CodingofcombinatorialsourcesandHausdorffdimension,

SovietMath.Dokl.30(1984)(1),219-222.[24]B.Ya.Ryabko,Noiselesscodingofcombinatorialsources,Hausdorffdimension

andKolmogorovcomplexity,ProblemyPeredachiInformatsii22(1986)(3),16-26.[25]B.Ya.Ryabko,Thecomplexityandeffectivenessofpredictionalgorithms,J.

Complexity10(1994),281-295.[26]C.P.Schnorr,Zuf¨alligkeitundWahrscheinlichkeit,LectureNotesinMath.No.

218,Springer-Verlag,Berlin1971.[27]R.J.Solomonoff,Aformaltheoryofinductiveinference,Part1andPart2,

Inform.andControl7(1964),1-22,and224-254.[28]L.Staiger,Complexityandentropy,InMathematicalFoundationsofComputer

Science,Proc.10thIntern.Symposium,(J.GruskaandM.Chytil,eds.),LectureNotesinComput.Sci.No.118,Springer-Verlag,Berlin1981,508–514.[29]L.Staiger,Hierarchiesofrecursiveω-languages.J.Inform.Process.Cybernetics

EIK22(1986)5/6,219–241.[30]L.Staiger,CombinatorialpropertiesoftheHausdorffdimension.J.Statist.

Plann.Inference23(1989),95-100.[31]L.Staiger,KolmogorovcomplexityandHausdorffdimension,Inform.and

Comput.103(1993),159–194.[32]L.Staiger.ω-languages,InHandbookofFormalLanguages(G.Rozenbergand

A.Salomaaeds.)Vol.3,Springer,Berlin1997,pp.339–387.[33]L.Staiger.Onω-powerlanguages,in:NewTrendsinFormalLanguages,

Control,Cooperation,andCombinatorics,vol.1218ofLectureNotesinComput.Sci.,pp.377–393,Springer,1997.[34]L.Staiger,AtightupperboundonKolmogorovcomplexityanduniformly

optimalprediction,TheoryComput.Systems31(1998),215–229.

21

[35]L.Staiger,ConstructivedimensionequalsKolmogorovcomplexity.Inform.

Process.Lett.93(2005),149–153[36]K.Tadaki.AgeneralizationofChaitin’shaltingprobabilityΩandhaltingself-similarsets,HokkaidoMath.J.31(2002),219–253.[37]W.Thomas,AutomataonInfiniteObjects,in:HandbookofTheoretical

ComputerScience,(J.VanLeeuwenEd.),Vol.B,133–191,Elsevier,Amsterdam,1990.[38]M.vanLambalgen,Randomsequences,Ph.D.Thesis,Univ.ofAmsterdam,

1987.[39]KlausWeihrauch,Computableanalysis:anintroduction.Springer-Verlag,

Berlin2000.[40]A.K.ZvonkinandL.A.Levin,Complexityoffiniteobjectsandthedevelopment

oftheconceptsofinformationandrandomnessbymeansofthetheoryofalgorithms,RussianMath.Surveys25(1970),83–124.

22

ECCC󰀀

http://eccc.hpi-web.de/

ISSN 1433-8092󰀀