Computability, Complexity, and Languages, Second Edition：Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing)

PrefaceAcknowledgmentsDependencyGraph1Preliminaries1.Setsandn-tuples2.Functions3.AlphabetsandStrings4.Predicates5.Quantifiers6.ProofbyContradiction7.MathematicalInductionPart1Cmnputability2ProgramsandComputableFunctions1.AProgrammingLanguage2.SomeExamplesofPrograms3.Syntax-4.ComputableFunctions5.MoreaboutMacros3PrimitiveRecursiveFunctions1.Composition2.Recursion3.PRCClasses4.SomePrimitiveRecursiveFunctions5.PrimitiveRecursivePredicates6.IteratedOperationsandBoundedQuantifiers7.Minimalization8.PairingFunctionsandGijdelNumbers4AUniversalProgram1.CodingProgramsbyNumbers---2.TheHaltingProblem3.Universality4.RecursivelyEnumerableSets5.TheParameterTheorem6.DiagonalizationandReducibility-_’7.Rice’sTheorem*8.TheRecursionTheorem*9.AComputableFunctionThatIsNotPrimitiveRecursive5CalculationsonStrings1.NumericalRepresentationofStrings2.AProgrammingLanguageforStringComputations3.TheLanguagesYandYn4.Post-TuringPrograms5.Simulationof-F”,in96.SimulationofYinY6TuringMachines1.InternalStates2.AUniversalTuringMachine3.TheLanguagesAcceptedbyTuringMachines4.TheHaltingProblemforTuringMachines5.NondeterministicTuringMachines6.VariationsontheTuringMachineTheme7ProcessesandGrammars1.Semi-ThueProcesses2.SimulationofNondeterministicTuringMachinesbySemi-ThueProcesses3.4.5.6.*7.UnsolvableWordProblemsPost’sCorrespondenceProblemGrammarsSomeUnsolvableProblemsConcerningGrammarsNormalProcesses8ClassifyingUnsolvableProblems1.UsingOracles2.RelativizationofUniversality3.Reducibility4.Setsr.e.RelativetoanOracle5.TheArithmeticHierarchy6.Post’sTheorem7.ClassifyingSomeUnsolvableProblems8.Rice’sTheoremRevisited9.RecursivePermutationsPart2GrammarsandAutomata9RegularLanguages1.FiniteAutomata2.NondeterministicFiniteAutomata3.AdditionalExamples4.ClosureProperties5.Kleene’sTheorem6.ThePumpingLemmaandItsApplications7.TheMyhill-NerodeTheorem10Context-FreeLanguages1.Context-FreeGrammarsandTheirDerivationTrees2.RegularGrammars3.ChomskyNormalForm4.Bar-Hillel’sPumpingLemma5.ClosureProperties*6.SolvableandUnsolvableProblems7.BracketLanguages8.PushdownAutomata9.CompilersandFormalLanguages11Context-SensitiveLanguages1.TheChomskyHierarchy2.LinearBoundedAutomata3.ClosurePropertiesPart3Logic12PropositionalCalculus1.FormulasandAssignments2.TautologicalInference3.NormalForms4.TheDavis-PutnamRules5.MinimalUnsatisfiabilityandSubsumption6.Resolution7.TheCompactnessTheorem13QuantificationTheory1.TheLanguageofPredicateLogic2.Semantics3.LogicalConsequence4.Herbrand’sTheorem5.Unification6.CompactnessandCountability*7.Godel’sIncompletenessTheorem*8.UnsolvabilityoftheSatisfiabilityProbleminPredicateLogicPart4Complexity14AbstractComplexity1.TheBlumAxioms2.TheGapTheorem3.PreliminaryFormoftheSpeedupTheorem4.TheSpeedupTheoremConcluded15Polynomial-TimeComputability1.RatesofGrowth2.PversusNP3.Cook’sTheorem4.OtherNP-CompleteProblemsPart5Semantics16ApproximationOrderings1.ProgrammingLanguageSemantics2.PartialOrders3.CompletePartialOrders4.ContinuousFunctions5.FixedPoints17DenotationalSemanticsofRecursionEquations1.Syntax2.SemanticsofTerms3.SolutionstoW-Programs4.DenotationalSemanticsofW-Programs5.SimpleDataStructureSystems6.InfinitaryDataStructureSystems18OperationalSemanticsofRecursionEquations1.OperationalSemanticsforSimpleDataStructureSystems2.ComputableFunctions3.OperationalSemanticsforInfinitaryDataStructureSystems