欢迎来到天天文库
浏览记录
ID:33680412
大小:6.35 MB
页数:600页
时间:2019-02-28
《TP301.6 An Introduction to the Theory of Computation》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、theory-bk.htmlAnIntroductiontotheTheoryofComputationEitanGurari,OhioStateUniversityComputerSciencePress,1989,ISBN0-7167-8182-4Copyright©EitanM.GurariToShaula,Inbal,Itai,Erez,Netta,andDannaPreface1GENERALCONCEPTS1.1Alphabets,Strings,andRepresentations1.2FormalLangua
2、gesandGrammars1.3Programs1.4Problems1.5ReducibilityamongProblemsExercisesBibliographicNotes2FINITE-MEMORYPROGRAMS2.1Motivation2.2Finite-StateTransducers2.3Finite-StateAutomataandRegularLanguages2.4LimitationsofFinite-MemoryPrograms2.5ClosurePropertiesforFinite-Memo
3、ryPrograms2.6DecidablePropertiesforFinite-MemoryProgramsExercisesBibliographicNotes3RECURSIVEFINITE-DOMAINPROGRAMS3.1Recursion3.2PushdownTransducers3.3Context-FreeLanguages3.4LimitationsofRecursiveFinite-DomainPrograms3.5ClosurePropertiesforRecursiveFinite-DomainPr
4、ograms3.6DecidablePropertiesforRecursiveFinite-DomainProgramsExerciseshttp://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html(1of3)[2/24/20031:46:54PM]theory-bk.htmlBibliographicNotes4GENERALPROGRAMS4.1TuringTransducers4.2ProgramsandTuringTransducers4.3Nonde
5、terminismversusDeterminism4.4UniversalTuringTransducers4.5Undecidability4.6TuringMachinesandType0Languages4.7Post'sCorrespondenceProblemExercisesBibliographicNotes5RESOURCE-BOUNDEDCOMPUTATION5.1TimeandSpace5.2ATimeHierarchy5.3NondeterministicPolynomialTime5.4MoreNP
6、-CompleteProblems5.5PolynomialSpace5.6P-CompleteProblemsExercisesBibliographicNotes6PROBABILISTICCOMPUTATION6.1Error-FreeProbabilisticPrograms6.2ProbabilisticProgramsThatMightErr6.3ProbabilisticTuringTransducers6.4ProbabilisticPolynomialTimeExercisesBibliographicNo
7、tes7PARALLELCOMPUTATION7.1ParallelPrograms7.2ParallelRandomAccessMachines7.3Circuits7.4UniformFamiliesofCircuits7.5UniformFamiliesofCircuitsandSequentialComputations7.6UniformFamiliesofCircuitsandPRAM'sExercisesBibliographicNotesAMATHEMATICALNOTIONSA.1Sets,Relation
8、s,andFunctionshttp://www.cis.ohio-state.edu/~gurari/theory-bk/theory-bk.html(2of3)[2/24/20031:46:54PM]theory-bk.htmlA.2GraphsandTreesBBIBLIOGRAPH
此文档下载收益归作者所有