Concise Guide to Computation Theory
Computation lies at the heart of modern digital technology and our increasingly advanced information society. The theory of computation describes what tasks can and cannot be computed, and how efficiently the computable tasks can be computed.This focused
- PDF / 7,108,649 Bytes
- 284 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 254 Views
Akira Maruoka
Concise Guide to Computation Theory
Akira Maruoka Faculty of Science and Engineering Ishinomaki Senshu University Shinmito Minamisakai 1 Ishinomaki, Japan [email protected]
ISBN 978-0-85729-534-7 e-ISBN 978-0-85729-535-4 DOI 10.1007/978-0-85729-535-4 Springer London Dordrecht Heidelberg New York British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2011927846 © Springer-Verlag London Limited 2011 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licenses issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Cover design: VTeX UAB, Lithuania Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Endorsements
Reischuk Rüdiger This fascinating text includes a wealth of ideas presented to novice readers such that they can understand substantial subjects of computation theory in just the way that experienced researchers in the field grasp them. Readers will find learning with this book to be both pleasurable and rewarding.
November, 2010
John E. Savage An unusual book that provides an excellent introduction to theoretical computer science while striking a good balance between mathematical rigor and intuitive understanding.
November, 2010
v
Foreword
This book is unusual: ambitious in scope, yet compact. Drawing on his broad research interests and extensive teaching experience, Professor Maruoka distills some of the major topics in the theory of computation into a relatively slim textbook accessible to undergraduates. His aim is to combine intuitive descriptions and illustrations with rigorous arguments and detailed proofs for key topics. The book is selfcontained in that it briefly introduces any mathematical prerequisites (in Part I), and it would be ideal for a one- or two-semester undergraduate course in the theory of computation. The principal material is in three sections: Automata and Languages, Computability, and Complexity of Computation. These represent the foundations of the theory of computation as understood today, underpinning the rich developments of the subject which have
Data Loading...
