TP301.6 An Introduction to the Theory of Computation

《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