Theoretical foundations of computer science
By: [by] Dino Mandrioli [and] Carlo Ghezzi.
Contributors: Ghezzi, Carlo.
Publisher: Wiley
Published: 1988
Place of publication: New York
Language: eng
Number of pages: 504
Table of contents: label: Chapter 0
title: Mathematical Background
pagenum: 1; label: 0.1
title: Mathematical Glossary
pagenum: 1; label: 0.1.1
title: Sets, Relations, Functions
pagenum: 1; label: 0.1.2
title: Basic Algebraic Structures
pagenum: 5; label: 0.1.3
title: Permutations and Combinations
pagenum: 7; label: 0.1.4
title: Graphs and Trees
pagenum: 8; label: 0.1.5
title: Alphabets, Strings, and Languages
pagenum: 10; label: 0.2
title: Basic Elements of Mathematical Logic
pagenum: 12; label: 0.2.1
title: Introduction to Formal Theories
pagenum: 12; label: 0.2.2
title: Propositional Calculus (PC)
pagenum: 13; label: 0.2.3
title: First-Order Theories and Predicate Calculi
pagenum: 18; label: 0.2.4
title: A Formal Theory (FT) for Arithmetic and Its Functions
pagenum: 30; label: 0.2.4.1
title: Peano's Axioms
pagenum: 30; label: 0.2.4.2
title: Recursive Functions
pagenum: 34; label: 0.2.4.3*
title: Some Fundamental Properties of the Axiomatization of Arithmetic
pagenum: 37; title: Chapter Summary
pagenum: 41; title: Bibliographic Remarks
pagenum: 41; label: Chapter 1
title: Models for Computer Science: Automata and Grammars
pagenum: 43; label: 1.1
title: The Use of Models in Engineering and Science
pagenum: 43; label: 1.1.1
title: Introductory Examples
pagenum: 45; label: 1.1.2
title: What About Models for the Computer Scientist?
pagenum: 46; label: 1.2
title: Finite-State Automata
pagenum: 50; label: 1.2.1
title: Finite-State Automata as Language Acceptors
pagenum: 52; label: 1.2.2
title: Finite-State Automata as Language Translators
pagenum: 55; label: 1.2.3
title: Properties of Finite-State Automata
pagenum: 59; label: 1.3
title: Extending Finite-State Automata: The Pushdown Automaton
pagenum: 65; label: 1.3.1
title: Pushdown Automata as Language Acceptors
pagenum: 68; label: 1.3.2
title: Pushdown Automata as Language Translators
pagenum: 72; label: 1.3.3
title: Properties of Pushdown Automata and Their Relation to Finite-State Automata
pagenum: 75; label: 1.4
title: Turing Machines
pagenum: 78; label: 1.4.1
title: Turing Machines as Language Acceptors
pagenum: 87; label: 1.4.2
title: Turing Machines as Language Translators
pagenum: 90; label: 1.4.3
title: Turing Machines as Function Evaluators
pagenum: 92; label: 1.4.4
title: Properties of Turing Machines
pagenum: 97; label: 1.5
title: Grammars: A Formalism to Generate Languages
pagenum: 104; label: 1.5.1
title: Properties of Grammars
pagenum: 108; label: 1.6
title: Denotational Language Definitions
pagenum: 111; label: 1.6.1
title: Equations in Language Spaces
pagenum: 112; label: 1.6.2
title: Regular Expressions
pagenum: 117; label: 1.7
title: Nondeterministic Models
pagenum: 119; label: 1.7.1
title: Nondeterministic Finite-State Automata
pagenum: 120; label: 1.7.2
title: Nondeterministic Pushdown Automata and Nondeterministic Turing Machines
pagenum: 124; label: 1.7.3*
title: An Intrinsically Nondeterministic Evolutionary Model: Petri Nets
pagenum: 127; label: 1.7.3.1
title: Petri Nets as Language Recognizers
pagenum: 132; label: 1.7.4
title: Some Remarks on Nondeterministic Versus Stochastic Models
pagenum: 134; label: 1.8
title: On the Power Relations Among Formalisms
pagenum: 135; title: Chapter Summary
pagenum: 138; title: Further Exercises
pagenum: 139; title: Sketchy Solutions to Selected Exercises
pagenum: 140; label: Appendix 1.A
title: The Equivalence Between Turing Machines and Partial Recursive Functions
pagenum: 142; title: Bibliographic Remarks
pagenum: 145; label: Chapter 2
title: Solvable and Unsolvable Problems
pagenum: 147; label: 2.1
title: On the Ability of a Mechanism to Solve a Problem
pagenum: 147; label: 2.2
title: On the Formalization of the Notion of a Problem
pagenum: 148; label: 2.3
title: Turing Machines, Programming Languages, and Church's Thesis (Part 1)
pagenum: 151; label: 2.4
title: Algorithms and Church's Thesis (Part 2)
pagenum: 152; label: 2.5
title: Turing Machine Enumeration and Universal Turing Machines
pagenum: 156; label: 2.5.1
title: Turing Machine Enumeration
pagenum: 157; label: 2.5.2
title: Universal Turing Machines
pagenum: 160; label: 2.6
title: Unsolvable Problems
pagenum: 163; label: 2.7
title: More on Solvable and Unsolvable Problems
pagenum: 166; label: 2.8
title: Fundamental Statements of Computability Theory
pagenum: 169; label: 2.8.1
title: Recursive and Recursively Enumerable Sets
pagenum: 169; label: 2.8.2
title: Kleene's and Rice's Theorems
pagenum: 174; label: 2.9
title: Reasoning on Problem Unsolvability
pagenum: 176; label: 2.10
title: Solvable and Unsolvable Language Problems
pagenum: 179; label: 2.11*
title: Problem Reducibility and Degrees of Unsolvability
pagenum: 182; title: Chapter Summary
pagenum: 187; title: Further Exercises
pagenum: 188; title: Sketchy Solutions to Selected Exercises
pagenum: 189; title: Bibliographic Remarks
pagenum: 190; label: Chapter 3
title: The Complexity of Computing
pagenum: 193; label: 3.1
title: Problem Solving in Practice: Some Difficulties
pagenum: 193; label: 3.1.1
title: How to Define Complexity Precisely
pagenum: 197; label: 3.1.2
title: Asymptotic Behavior
pagenum: 198; label: 3.1.3
title: Other Sources of Complexity
pagenum: 200; label: 3.2
title: Complexity Analysis by Means of Automata
pagenum: 201; label: 3.2.1
title: The Complexity of Problem Solving by Turing Machines
pagenum: 201; label: 3.2.2
title: The Complexity of Problem Solving by Other Automata
pagenum: 209; label: 3.2.2.1
title: Complexity of Finite-State Automata Computations
pagenum: 209; label: 3.2.2.2
title: Complexity of Push-Down Automata Computations
pagenum: 210; label: 3.2.2.3
title: Complexity of Single-Tape Turing Machines
pagenum: 212; label: 3.3
title: Some General Properties of Multitape Turing Machines Complexity
pagenum: 218; label: 3.4
title: Complexity Analysis of Real Computer Programs
pagenum: 225; label: 3.4.1
title: The RAM Machine
pagenum: 226; label: 3.4.2
title: Higher-Level Programming Languages
pagenum: 237; label: 3.5
title: Putting Things Together
pagenum: 244; label: 3.6*
title: Advanced Complexity Concepts: Hierarchies, Reducibility, and Completeness
pagenum: 253; label: 3.7*
title: Some Classical NP-Complete Problems
pagenum: 259; label: 3.8
title: Complexity Lower Bounds
pagenum: 268; label: 3.9
title: Complexity Evaluation in Action
pagenum: 272; label: 3.9.1
title: A Sorting Example
pagenum: 272; label: 3.9.2
title: An Algorithm on Graphs
pagenum: 275; label: 3.10
title: Some Advice and Conclusions
pagenum: 279; title: Chapter Summary
pagenum: 281; title: Further Exercises
pagenum: 281; title: Sketchy Solutions to Selected Exercises
pagenum: 282; title: Bibliographic Remarks
pagenum: 283; label: Chapter 4
title: Formal Semantics
pagenum: 285; label: 4.1
title: Notation and Meaning
pagenum: 285; label: 4.2
title: The Need for a Formal Definition of Semantics
pagenum: 290; label: 4.3
title: The Use of Formal Semantics
pagenum: 292; label: 4.4
title: Main Approaches to Giving Formal Semantics of Programming Languages
pagenum: 294; label: 4.4.1
title: The Operational Approach to Semantics
pagenum: 295; label: 4.4.2
title: The Denotational Approach to Semantics
pagenum: 296; label: 4.5
title: Operational Semantics
pagenum: 298; label: 4.5.1
title: SMALG+: Syntax and Informal Semantics
pagenum: 298; label: 4.5.2
title: Description of SMALM+
pagenum: 302; label: 4.5.3
title: Semantics of SMALG+ Defined via SMALM+
pagenum: 306; label: 4.6
title: Denotational Semantics
pagenum: 315; label: 4.6.1
title: McCarthy's Formalism and Its Semantics
pagenum: 316; label: 4.6.1.1
title: Mathematical Background
pagenum: 329; label: 4.6.1.2
title: Denotational Semantics of McCarthy's Formalism
pagenum: 339; label: 4.6.2
title: McCarthy's Formalism as a Programming Language
pagenum: 344; label: 4.6.3
title: Denotational Semantics for Algol-like Languages
pagenum: 347; label: 4.7
title: Concluding Remarks
pagenum: 354; title: Chapter Summary
pagenum: 356; title: Further Exercises
pagenum: 356; title: Sketchy Solutions to Selected Exercises
pagenum: 357; label: Appendix 4.A
title: Equivalence Between McCarthy's Formalism, Partial Recursive Functions, and Turing Machines
pagenum: 358; title: Bibliographic Remarks
pagenum: 359; label: Chapter 5
title: Proving Program Properties
pagenum: 361; label: 5.1
title: The Impact of Formal Techniques on Program Reliability
pagenum: 361; label: 5.2
title: A Proof-Oriented Formal Semantics: The Axiomatic Approach
pagenum: 364; label: 5.2.1
title: Handling Quantified Assertions
pagenum: 372; label: 5.2.2
title: Handling Indexed Variables
pagenum: 375; label: 5.3
title: The Termination Issue
pagenum: 386; label: 5.3.1*
title: Further Insights into Termination Proofs
pagenum: 388; label: 5.4*
title: The Soundness and Completeness Issues
pagenum: 392; label: 5.5*
title: The Synthesis of Correct Programs
pagenum: 394; label: 5.6
title: Towards a Proof-System for a Real-Life Programming Language
pagenum: 402; label: 5.7*
title: Proving Further Program Properties: The Case of Complexity
pagenum: 405; label: 5.7.1*
title: Termination as Corollary of Complexity
pagenum: 408; label: 5.8
title: Proving Program Properties Through Denotational Semantics
pagenum: 409; label: 5.9
title: Concluding Remarks
pagenum: 415; title: Chapter Summary
pagenum: 416; title: Further Exercises
pagenum: 416; title: Sketchy Solutions to Selected Exercises
pagenum: 417; title: Bibliographic Remarks
pagenum: 419; label: Chapter 6
title: Nondeterminism and Parallel Computation
pagenum: 421; label: 6.1
title: Introduction
pagenum: 421; label: 6.2
title: The Use of Nondeterminism and Parallelism in Classical Programming
pagenum: 422; label: 6.2.1
title: Nondeterministic Algorithms for Search Problems
pagenum: 422; label: 6.2.2
title: Parallel Computation: An Example
pagenum: 426; label: 6.2.3
title: Nondeterministic Programming Languages and Correctness Proofs: A Brief Introduction
pagenum: 428; label: 6.3
title: Concurrent Computations and the Use of Nondeterministic Models
pagenum: 432; label: 6.3.1
title: Petri Nets and the Description of Operating Systems
pagenum: 440; label: 6.3.2
title: Describing Shared Databases by Means of Petri Nets
pagenum: 446; label: 6.3.3
title: Real-Time Systems and Petri Nets
pagenum: 446; label: 6.3.4
title: Describing Semantics of Concurrent Programming Languages: Examples from Ada
pagenum: 449; label: 6.3.5
title: Describing Distributed Systems by Means of Petri Nets
pagenum: 452; title: Chapter Summary
pagenum: 455; title: Further Exercises
pagenum: 455; title: Sketchy Solutions to Selected Exercises
pagenum: 456; title: Bibliographic Remarks
pagenum: 457; title: Bibliography
pagenum: 459; title: Index
pagenum: 471