文档介绍：Second Edition
Computability,
Complexity, and
Languages
Fundamentals of
puter Science
Martin D. Davis
Department puter Science
Courant Institute of Mathematical Sciences
New York University
New York, New York
Ron Sigal
Departments of Mathematics puter Science
Yale University
New Haven, Connecticut
Elaine J. Weyuker
Department puter Science
Courant Institute of Mathematical Sciences
New York University
New York, New York
ACADEMIC PRESS
Harcourt, Brace & Company
Boston San Diego New York
London Sydney Tokyo Toronto
This book is printed on acid-free paper @)
Copyright© 1994, 1983 by Academic Press, Inc.
All rights reserved
No part of this publication may be reproduced or
transmitted in any form or by any means, electronic
or mechanical, including photocopy, recording, or
any information storage and retrieval system, without
permission in writing from the publisher.
ACADEMIC PRESS, INC.
525 B Street, Suite 1900, San Diego, CA 92101-4495
United Kingdom Edition published by
ACADEMIC PRESS LIMITED
24-28 Oval Road, London NW1 7DX
Library of Congress Cataloging-in-Publication Data
Davis, Martin 1928-
Computability, complexity, and languages: fundamentals of
puter science/Martin D. Davis, Ron Sigal,
Elaine J. Weyuker. --2nd ed.
p. em. --(Computer science and applied mathematics)
Includes bibliographical references and index.
ISBN 0-12-206382-1
1. Machine theory. 2. plexity. 3. Formal
languages. I. Sigal, Ron. II. Weyuker, Elaine J. III. Title.
IV. Series.
1994
-dc20 93-26807
CIP
Printed in the United States of America
94 95 96 97 98 BC 9 8 7 6 5 4 3 2 1
To the memory ofHelen and Harry Davis
and to
Hannah and Herman Sigal
Sylvia and Marx Weyuker
Vir;ginia Davis, Dana Latch, Thomas Ostrand
and to
Rachel Weyuker Ostrand
Contents
Preface xiii
Acknowledgments xvii
Dependency Graph xix
1 Preliminaries 1
1. Sets and n-tupl