资源描述：
《turing machines with sublogarithmic space外语英文电子书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、AndrzejSzepietowskiTuringMachineswithSublogarithmicSpaceSpringer-VerlagBerlinHeidelbergNewYorkLondonParisTokyoHongKongBarcelonaBudapestLectureNotesinComputerScience843EditedbyG.GoosandJ.HartmanisAdvisoryBoard:W.BrauerD.GilesJ.StoerSeriesEditorsGerhardGoosJurisHartma
2、nisUniversitatKarlsruheCornellUniversityPostfach6980DepartmentofComputerScienceVincenz-Priessnitz-Strage14130UpsonHallD-76131Karlsruhe,GermanyIthaca,NY14853,USAAu~orAndrzejSzepietowskiMathematicalInstitute,GdanskUniversityU1.WitaStwosza57,80-952Gdansk,PolandUntilMar
3、ch1995:FB17-Informatik,Universit~itGHPaderbornWarburgerstrafie100,D-33095Paderborn,GermanyCRSubjectClassification(1991):Ei.1,E4.1ISBN3-540-58355-6Springer-VerlagBerlinHeidelbergNewYorkISBN0-387-58355-6Springer-VerlagNewYorkBerlinHeidelbergCIPdataappliedforThisworkis
4、subjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialisconcerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting,reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublicati
5、onorpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.ViolationsareliableforprosecutionundertheGermanCopyrightLaw.9Springer-VerlagBerlinHeidelberg1994
6、PrintedinGermanyTypesetting:Camera-readybyauthorSPIN:1047543545/3140-543210-Printedonacid-freepaperPrefaceThemainobjectsofinvestigationofspacecomplexitytheoryareTuringmachineswithboundedspace(thenumberofcellsonthetapeusedduringcomputation)andlanguagesacceptedbysuchm
7、achines.Althoughsomeimportantproblemsstillremainopen,muchworkhasbeendone,andmanyexcitingresultshavebeenobtained.Manyoftheseresults,however,havebeenprovedundertheassumptionthattheamountofavailablespaceisatleastlogarithmicwithrespecttothelengthoftheinput.InthisbookIha
8、vepresentedthekeyresultonspacecomplexity,butconcentratedonproblems:Whathappenswhenwedroptheassumptionofatleastlogarithmicspaceandwhatdolan
