Logic and Language Models for Computer Science

<!– –>

This text presents the formal concepts underlying Computer Science.

It starts with a wide introduction to Logic with an emphasis on reasoning and proof, with chapters on Program Verification and Prolog.

The treatment of computability with Automata and Formal Languages stands out in several ways:

<!––>
it emphasizes the algorithmic nature of the proofs and the reliance on simulations;
it stresses the centrality of nondeterminism in generative models and the relationship to deterministic recognition models
<!––>
The style is appropriate for both undergraduate and graduate classes.

<!– –>Contents:
Mathematical Preliminaries
Logic for Computer Science:
Propositional Logic
Proofs by Deduction
Predicate Logic
Proving with Predicates
Program Verification
Language Models for Computer Science:
Language and Models
Generative Models of Regular Languages
Finite Automata and Regular Languages
Context-Free Grammars
Pushdown Automata and Parsing
Turing Machines

Appendices:
Logic Programming
The awk Language
Answers to Selected Problems
<!– –>
<!– –>Readership: Students and professionals interested in theoretical computation and language models for computer science.<!– –>

Key Features:
The emphasis is on Logic. Logic is described in the context of reasoning (not circuits) with a concentration on proof techniques. The discussion entails a chapter on Program Verification and a chapter on Prolog programming
There is a forthright treatment of non-determinism. Non-determinism is fundamental to generative techniques, like grammatical models and recursively defined constructs such as regular expressions, and are integral to machine models of context-free languages
The treatment of constructive proofs (in particular, simulation-based proofs of computability) are cast in explicit algorithmic notation, which is familiar to the Computer Science student