Books in the Texts in Computer Science series

Algorithms are central to all areas of computer science, from compiler construction to numerical analysis to artificial intelligence. Throughout your academic and professional careers, you may be required to construct new algorithms, analyze existing algorithms, or modify algorithms to suit new purposes. How do we know that such algorithms are correct? One method involves making claims about how we expect our programs to operate, and then constructing code that carries out these tasks. The key component of such reasoning is the invariant, and is the topic of this book. In these pages, you will study how invariants are developed, how they are used to construct correct algorithms, and how they are helpful in analyzing existing programs. Along the way, you'll be introduced to some classic sorting, searching and mathematical algorithms, and even some solutions to games and logic puzzles. These examples, though, are only conduits for the loftier goal: understanding why algorithms work.

Logic for Artificial Intelligence and Information Technology is based on student notes used to teach logic to second year undergraduates and Artificial Intelligence to graduate students at the University of London since1984, first at Imperial College and later at King's College.Logic has been applied to a wide variety of subjects such as theoretical computer science, software engineering, hardware design, logic programming, computational linguistics and artificial intelligence. In this way it has served to stimulate the research for clear conceptual foundations.Over the past 20 years many extensions of classical logic such as temporal, modal, relevance, fuzzy, probabilistic and non-monotoinic logics have been widely used in computer science and artificial intelligence, therefore requiring new formulations of classical logic, which can be modified to yield the effect of the new applied logics.The text introduces classical logic in a goal directed way which can easily deviate into discussing other applied logics. It defines the many types of logics and differences between them.Dov Gabbay, FRSC, FAvH, FRSA, FBCS, is Augustus De Morgan Professor of Logic at the University of London. He has written over 300 papers in logic and over 20 books. He is Editor-in-Chief of several leading journals and has published over 50 handbooks of logic volumes. He is a world authority on applied logics and is one of the directors and founder of the UK charity the International Federation of Computational Logic

Automata and Dictionaries is aimed at students and specialists in natural language processing and related disciplines where efficient text analysis plays a role. Large linguistic resources, in particular lexica, are now recognized as a fundamental pre-requisite for all natural language processing tasks. Specialists in this domain cannot afford to be ignorant of the state-of-the-art lexicon-management algorithms. This monograph, which is also intended be used as an advanced text book in computational linguistics, fills a gap in natural language processing monographs and is complementary to other publications in this area.This book is also a source of examples, exercises and problems for software engineering in general. The algorithms that are presented are excellent examples of non-trivial problems of graph construction, graph handling and graph traversal. Even though published in scientific journals, they have not been presented in an easily accessible form so far to teachers and students. These algorithms will also be of interest for the training of software engineers.Chapter 1 of Automata and Dictionaries provides the application-oriented motivation for solving the problems studied in the rest of the book. It introduces and exemplifies several key notions of lexicon-based natural language processing in a way accessible to any computer science student. Chapter 2 surveys the main solutions of the problem, using as an example a very small toy lexicon. Chapter 3 defines the underlying mathematical notions, immediately illustrating theory with practical examples, which makes this part quite readable.Chapters 4 and 5 are dedicated to the two central notions of lexicon construction: the algorithms of determinization and minimization. The standard form of both algorithms is presented, but also their variants and some special cases that occur frequently in practice. The operation of the algorithms is described step by step in examples, introducing the beginner into the world of epsilon-transitions, state heights and reverse automata.Chapter 6 goes a step further into complexity. It is based on algorithms published by scholars from 1998 to now. They are presented here with the same clarity as the preceding, more classical, algorithms. This remarkable achievement owes much to the rigorous structuration of this chapter. These algorithms have variants for transducers, which are presented in Chapter 7 with the same pedagogical skill.The last chapter studies time and space complexity of the algorithms and explains several tricks useful to speed up their operation.