Handbook Of Constraint Programming – Francesca Rossi

Marriott, P. J. Stuckey, M. Wallace Theorem 12.8. (Logical Soundness of Success) Let TC be the constraint theory for con- straint domain C and P be a CLP(C) program. If goal G has answer c, then P, TC |= ¯∃vars(G)c →G. Theorem 12.9. (Logical Completeness of Success) Let TC be the constraint theory for constraint domain C and P be a CLP(C) program. Let G be a goal and c a constraint. If P, TC |= c →G then G has answers c1, .

. . , cn such that TC |= c →(¯∃vars(G)c1 ∨. . . ∨¯∃vars(G)cn). Algebraic semantics We now turn our attention to the algebraic semantics. Such a semantics requires us to find a model for the program which is the “intended” interpretation of the program. Clearly, the intended interpretation of a CLP program should not change the interpretation of the primitive constraints or function symbols: All it should do is to extend this intended inter- pretation by providing an interpretation for each user-defined predicate symbol in P. Definition 12.10.

A C-interpretation for a CLP(C) program P is an interpretation which agrees with the constraint interpretation DC on the interpretation of the symbols in C. Definition 12.11. A C-model of a CLP(C) program P is a C-interpretation which is a model of P. Since the meaning of the primitive constraints is fixed by C we can identify each C- interpretation with the subset of the C-base of P, written C-baseP , which it makes true where C-baseP is the set {p(d1, .

. . , dn) | p is an n-ary user-defined predicate in P and each di is a domain element of DC }. Every program has a least C-model, denoted lm(P, C) which is usually regarded as the intended interpretation of the program since it is the most conservative C-model.

Copyright © 2006 Elsevier B.V. All rights reserved No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means electronic, mechanical, photocopying, recording or otherwise without the prior written permission of the publisher Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone (+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email: [email protected].

Alternatively you can submit your request online by visiting the Elsevier web site at http://elsevier.com/locate/permissions, and selecting Obtaining permission to use Elsevier material Notice No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or ideas contained in the material herein. Because of rapid advances in the medical sciences, in particular, independent verification of diagnoses and drug dosages should be made Library of Congress Cataloging-in-Publication Data A catalog record for this book is available from the Library of Congress British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library ISBN-13: 978-0-444-52726-4 ISBN-10: 0-444-52726-5 ISSN: 1574-6525 For information on all Elsevier publications visit our website at books.elsevier.com Printed and bound in The Netherlands 06 07 08 09 10 10 9 8 7 6 5 4 3 2 1 Foreword Constraints are an ubiquitous concept, which in its broader sense pertains to every day experience: they represent the conditions which restrict our freedom of decision.

In fact, how much our choices are constrained by the external world is a basic philosophical ques- tion. In the formalized reasoning of scientific disciplines, constraints have been employed extensively, from logic to numerical analysis, from mathematical programming to opera- tions research. In computer science, constraints have been with us from the early days, for modeling, representing and reasoning (see the interesting historical remarks in Chapter 2 of this handbook, Constraint Satisfaction: An Emerging Paradigm). I see several good reasons for this ubiquity: one is the conceptually clear separation between the perfectly declarative problem statements and the often cumbersome enumera- tive efforts for finding solutions.

Another reason is the complexity challenge: the classical constraint satisfaction problem is NP-complete and in fact tautology checking in propo- sitional calculus (a constraint problem on Boolean variables) has been the touchstone for this complexity class. A further reason is that large, complex constraint problems often occur in practice, they must be solved in one way or another, and fast, efficient, systematic solutions have an enormous economic value.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 2a86d078fabaeb67
• File Extension: .pdf
• File Size: 7,092,176 bytes (6.764 MB)
• Title: –
• Author: Unknown
• ISBN: 9780444527264, 1865843830, 0444527265, 0865760578, 0897915704
• Pages: 978
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 2312.11 minutes
• Total Words: 462,421
• Total Characters: 2,812,880
• Average Words per Page: 472.82
• Average Characters per Page: 2876.16

Most Frequent Words

constraint (4585), constraints (3168), search (1950), problem (1834), set (1737), variables (1645), programming (1498), problems (1253), variable (1224), one (1108), algorithm (1051), consistency (1037), value (979), domain (932), solution (924), pages (882), time (864), algorithms (827), example (823), used (766), also (698), propagation (697), two (687), values (677), using (640), model (632), number (631), given (616), local (613), graph (587), network (585), csp (546), arc (545), first (507), domains (505), proceedings (502), artificial (500), logic (496), intelligence (495), between (492), solving (492), new (484), satisfaction (474), language (467), symmetry (460), use (457), different (438), see (436), section (436), possible (433), bound (429), case (429), conference (429), solutions (414), let (413), many (412), tree (411), cost (410), based (408), techniques (407), node (405), scheduling (402), interval (401), function (401), methods (397), global (393), however (388), con (385), order (382), backtracking (379), international (378), systems (377), definition (372), assignment (369), research (368), since (364), figure (364), languages (359), system (358), structure (358), solver (356), computer (350), defined (350), finite (348), optimization (345), complexity (344), form (339), approach (339), ordering (337), consistent (330), van (325), linear (325), path (323), chapter (320), temporal (319), sets (318), called (314), every (306), consider (306), general (299).

PDF Download