It may sound surprising that in computing, a field which develops so fast that the future often becomes the past without having been the present, there is nothing more stable and worthwhile learning than its foundations.

It may sound less surprising that in a field with such a revolutionary methodological impact on all sciences and technologies, and on almost all our intellectual endeavours, the importance of the foundations of computing goes far beyond the subject itself. It should be of interest both to those seeking to understand the laws and essence of the information processing world and to those wishing to have a firm grounding for their lifelong reeducation process - something which everybody in computing has to expect.

This book presents the automata-algorithm-complexity part of foundations of computing in a new way, and from several points of view, in order to meet the current requirements of learning and teaching.

First, the book takes a broader and more coherent view of theory and its foundations in the various subject areas. It presents not only the basics of automata, grammars, formal languages, universal computers, computability and computational complexity, but also of parallelism, randomization, communications, cryptography, interactive protocols, communication complexity and theoretical computer/communication architecture.

Second, the book presents foundations of computing as rich in deep, important and exciting results that help to clarify the problems, laws, and potentials in computing and to cope with its complexity.
Third, the book tries to find a new balance between the formal rigorousness needed to present basic concepts and results, and the informal motivations, illustrations and interpretations needed to grasp their merit.

Fourth, the book aims to offer a systematic, complex and up-to-date presentation of the main basic concepts, models, methods and results, as well as to indicate new trends and results whose detailed demonstration would require special lectures. To this end, basic concepts, models, methods and results are presented and illustrated in detail, whilst other deep/new results with difficult or rather obsure proofs are just stated, explained, interpreted and commented upon.

The topics covered are very broad and each chapter could be expanded into a separate book.