Logic is one of the most popular approaches to artificial intelligence. A potential obstacle to the use of logic is its high computational complexity, as logical inference is an extraordinarily powerful computational device.
This book is concerned with computational aspects of the logical approach to AI. The focus is on two strategies for achieving computational tractability in knowledge representation and reasoning by language restriction and approximation. Several formalisms for knowledge representation are taken into account; among the computational problems studied are checking satisfiability and entailment of formulae, finding a model, and approximating and compiling a logical for

Logic is now widely recognized to be one of the foundational disciplines of computing and has found applications in virtually all aspects of the subject, from software engineering and hardware to programming languages and artificial intelligence. There is a growing need for an in-depth survey of the applications in logic in A1 and computer science. The Handbook of Logic in Ariticial Intelligence and Logic Programming and its companion, the Handbook of Logic in Computer Science, have been created in response to this need. We see the creation of the Handbook as a combination of authoritative exposition, comprehensive survey, and fundamental research exploring the underlying themes in the various areas. The intended audience is graduate students and researchers in the areas of A1 and logic, as well as other people interested in the subject. We assume as background some mathematical sophistication. Much of the material will be of interest to logicians and mathematicians. The tables of contents of the volumes were finalized after extensive discussions between handbook authors and second readers. This book is intended for theoretical computer scientists. Logicians. Volume Co-ordinator::

This volume constitutes the proceedings of the 4th International Workshop on Theorem Proving with Analytic Tableaux and Related Methods, TABLEAU '95, held at Schloss Rheinfels, St. Goar, Germany in May 1995.
Originally tableau calculi and their relatives were favored primarily as a pedagogical device because of their advantages at the presentation level. The 23 full revised papers in this book bear witness that these methods have now gained fundamental importance in theorem proving, particularly as competitors for resolution methods. The book is organized in sections on extensions, modal logic, intuitionistic logic, the connection method and model elimination, non-clausal proof procedures, linear logic, higher-order logic, and applications"

This volume presents the proceedings of the Second International Conference on Typed Lambda Calculi and Applications, held in Edinburgh, UK in April 1995.
The book contains 29 full revised papers selected from 58 submissions and comprehensively reports the state of the art in the field. The following topics are addressed: proof theory of type systems, logic and type systems, typed lambda calculi as models of (higher-order) computation, semantics of type systems, proof verification via type systems, type systems of programming languages, and typed term rewriting systems.

This volume presents the thoroughly revised proceedings of the IJCAI '93 Workshop on Executable Modal and Temporal Logics held in Chambery, France in August 1993.
The direct execution of logical statements, through languages such as PROLOG, has proved remarkably successful within CS and AI. In recent years a variety of nonclassical logics have been introduced and several executable forms of these logics have been applied to programming.
This volume addresses a range of approaches to executable modal and temporal logics, not only from a logical point of view, but also from programming language and application standpoints; in addition, an introductory survey and an annotated bibliography are presented.

The book is a fairly complete and up-to-date survey of projectivity and its generalizations in the class of Boolean algebras. Although algebra adds its own methods and questions, many of the results presented were first proved by topologists in the more general setting of (not necessarily zero-dimensional) compact spaces.
An appendix demonstrates the application of advanced set-theoretic methods to the field.
The intended readers are Boolean and universal algebraists. The book will also be useful for general topologists wanting to learn about kappa-metrizable spaces and related classes. The text is practically self-contained but assumes experience with the basic concepts and techniques of Boolean algebras.

The subject of the book is an approach to the modeling of and the reasoning under uncertainty. It develops the Dempster-Shafer Theory as a theory of the reliability of reasoning with uncertain arguments. A particular interest of this approach is that it yields a new synthesis and integration of logic and probability theory. The reader will benefit from a new view at uncertainty modeling which extends classical probability theory.

This volume presents the proceedings of the 7th International Workshop on Higher Order Logic Theorem Proving and Its Applications held in Valetta, Malta in September 1994.
Besides 3 invited papers, the proceedings contains 27 refereed papers selected from 42 submissions. In total the book presents many new results by leading researchers working on the design and applications of theorem provers for higher order logic. In particular, this book gives a thorough state-of-the-art report on applications of the HOL system, one of the most widely used theorem provers for higher order logic.

This volume contains revised refereed versions of the best papers presented during the CSL '94 conference, held in Kazimierz, Poland in September 1994; CSL '94 is the eighth event in the series of workshops held for the third time as the Annual Conference of the European Association for Computer Science Logic.
The 38 papers presented were selected from a total of 151 submissions. All important aspects of the methods of mathematical logic in computer science are addressed: lambda calculus, proof theory, finite model theory, logic programming, semantics, category theory, and other logical systems. Together, these papers give a representative snapshot of the area of logical foundations of computer science.

This volume constitutes the proceedings of the First International Conference on Constraints in Computational Logics, CCL '94, held in Munich, Germany in September 1994. Besides abstracts or full papers of the 5 invited talks by senior researchers, the book contains revised versions of the 21 accepted research papers selected from a total of 52 submissions. The volume assembles high quality original papers covering major theoretical and practical issues of combining and extending programming paradigms, preferably by using constraints. The topics covered include symbolic constraints, set constraints, numerical constraints, multi-paradigm programming, combined calculi, constraints in rewriting, deduction, symbolic computations, and working systems.

This volume contains the thoroughly refereed and revised papers accepted for presentation at the IJCAI '91 Workshops on Fuzzy Logic and Fuzzy Control, held during the International Joint Conference on AI at Sydney, Australia in August 1991. The 14 technical contributions are devoted to several theoretical and applicational aspects of fuzzy logic and fuzzy control; they are presented in sections on theoretical aspects of fuzzy reasoning and fuzzy control, fuzzy neural networks, fuzzy control applications, fuzzy logic planning, and fuzzy circuits. In addition, there is a substantial introduction by the volume editors on the latest developments in the field that brings the papers presented into line.

Logic is now widely recognized to be one of the foundational disciplines of computing and has found applications in virtually all aspects of the subject, from software engineering and hardware to programming languages and artificial intelligence. There is a growing need for an in-depth survey of the applications of logic in Al and computer science. The Handbook of Logic in Articial Intelligence and Logic Programming and its companion, the Handbook of Logic in Computer Science, have been created in response to this need. We see the creation of the Handbook as a combination of authoritative exposition, comprehensive survey, and fundamental research exploring the underlying themes in the various areas. The intended audience is graduate students and researchers in the areas of A1 and logic, as well as other people interested in the subject. We assume as background some mathematical sophistication. Much of the material will be of interest to logicians and mathematicians. The tables of contents of the volumes were finalized after extensive discussions between handbook authors and second readers. This book is intended for theoretical computer scientists; logicians. Volume Co-ordinator:: S

This volume presents the refereed papers accepted for the international symposium Logical Foundations of Computer Science '94, Logic at St. Petersburg, held in St. Petersburg, Russia in July 1994. The symposium was the third in a series of joint efforts of logicians from both the former Soviet Union and the West.
The volume reflects that the interaction of logic and computer science is an especially fertile ground for interdisciplinary work providing mutual understanding and benefits. The totally 35 papers are devoted to topics as linear logic, Horn clauses, model-checking, lambda-calculi, modal logic, and problem complexity.

This book focuses on image based security techniques, namely visual cryptography, watermarking, and steganography. This book is divided into four sections. The first section explores basic to advanced concepts of visual cryptography. The second section of the book covers digital image watermarking including watermarking algorithms, frameworks for modeling watermarking systems, and the evaluation of watermarking techniques. The next section analyzes steganography and steganalysis, including the notion, terminology and building blocks of steganographic communication. The final section of the book describes the concept of hybrid approaches which includes all image-based security techniques. One can also explore various advanced research domains related to the multimedia security field in the final section. The book includes many examples and applications, as well as implementation using MATLAB, wherever required. Features: Provides a comprehensive introduction to visual cryptography, digital watermarking and steganography in one book Includes real-life examples and applications throughout Covers theoretical and practical concepts related to security of other multimedia objects using image based security techniques Presents the implementation of all important concepts in MATLAB

Formal specifications were first used in the description of program ming languages because of the central role that languages and their compilers play in causing a machine to perform the computations required by a programmer. In a relatively short time, specification notations have found their place in industry and are used for the description of a wide variety of software and hardware systems. A formal method - like VDM - must offer a mathematically-based specification language. On this language rests the other key element of the formal method: the ability to reason about a specification. Proofs can be empioyed in reasoning about the potential behaviour of a system and in the process of showing that the design satisfies the specification. The existence of a formal specification is a prerequisite for the use of proofs; but this prerequisite is not in itself sufficient. Both proofs and programs are large formal texts. Would-be proofs may therefore contain errors in the same way as code. During the difficult but inevitable process of revising specifications and devel opments, ensuring consistency is a major challenge. It is therefore evident that another requirement - for the successful use of proof techniques in the development of systems from formal descriptions - is the availability of software tools which support the manipu lation of large bodies of formulae and help the user in the design of the proofs themselves."

This volume contains the proceedings of the 15th International Conference on Application and Theory of Petri Nets, held at Zaragoza, Spain in June 1994. The annual Petri net conferences are usually visited by some 150 - 200 Petri net experts coming from academia and industry all over the world.
The 28 full papers were selected out of in total 85 submissions from 18 countries. Together with the 3 invited contributions, these papers give a state-of-the-art report on all relevant aspects of Petri nets.

This volume presents the proceedings of the Computer Science Logic Workshop CSL '92, held in Pisa, Italy, in September/October 1992. CSL '92 was the sixth of the series and the first one held as Annual Conference of the European Association for Computer Science Logic (EACSL). Full versions of the workshop contributions were collected after their presentation and reviewed. On the basis of 58 reviews, 26 papers were selected for publication, and appear here in revised final form. Topics covered in the volume include: Turing machines, linear logic, logic of proofs, optimization problems, lambda calculus, fixpoint logic, NP-completeness, resolution, transition system semantics, higher order partial functions, evolving algebras, functional logic programming, inductive definability, semantics of C, classes for a functional language, NP-optimization problems, theory of types and names, sconing and relators, 3-satisfiability, Kleene's slash, negation-complete logic programs, polynomial-time oracle machines, and monadic second-order properties.

This volume contains work on the decision problem done in Kazan (Russia), Tallinn (Estonia), and Vienna (Austria). The authors met several times to discuss and exchange their results and finally decided to write this monograph together. Besides a unified treatment of previously published results there are many new results first presented in this volume. The monograph opens with an introduction and a chapter on terminology, followed by chapters on: - Semantic clash resolution as decision procedure, - Completeness of ordering refinements, - Semantic tree based resolution variants, - Deciding the class K by an ordering refinement, - A resolution based method for building finite models. A final chapter on applications completes the volume.

This proceedings volume contains a selection of revised and extended papers presented at the Second International Workshop on Nonmonotonic and InductiveLogic, NIL '91, which took place at Reinhardsbrunn Castle, December 2-6, 1991. The volume opens with an extended version of a tutorial on nonmonotonic logic by G. Brewka, J. Dix, and K. Konolige. Fifteen selected papers follow, on a variety of topics. The majority of papers belong either to the area of nonmonotonic reasoning or to the field of inductive inference, but some papers integrate research from both areas. The first workshop in this series was held at the University of Karlsruhe in December 1990 and its proceedings were published as Lecture Notes in Artificial Intelligence Volume 543. The series of workshops was made possible by financial support from Volkswagen Stiftung, Hannover. This workshop was also supported by IBM Deutschland GmbH and Siemens AG.

The lambda calculus was developed in the 1930s by Alonzo Church. The calculus turned out to be an interesting model of computation and became theprototype for untyped functional programming languages. Operational and denotational semantics for the calculus served as examples for otherprogramming languages. In typed lambda calculi, lambda terms are classified according to their applicative behavior. In the 1960s it was discovered that the types of typed lambda calculi are in fact appearances of logical propositions. Thus there are two possible views of typed lambda calculi: - as models of computation, where terms are viewed as programs in a typed programming language; - as logical theories, where the types are viewed as propositions and the terms as proofs. The practical spin-off from these studies are: - functional programming languages which are mathematically more succinct than imperative programs; - systems for automated proof checking based on lambda caluli. This volume is the proceedings of TLCA '93, the first international conference on Typed Lambda Calculi and Applications, organized by the Department of Philosophy of Utrecht University. It includes29 papers selected from 51 submissions.

Drawing on the authors' use of the Hadamard-related theory in several successful engineering projects, Theory and Applications of Higher-Dimensional Hadamard Matrices, Second Edition explores the applications and dimensions of Hadamard matrices. This edition contains a new section on the applications of higher-dimensional Hadamard matrices to the areas of telecommunications and information security. The first part of the book presents fast algorithms, updated constructions, existence results, and generalized forms for Walsh and Hadamard matrices. The second section smoothly transitions from two-dimensional cases to three-, four-, and six-dimensional Walsh and Hadamard matrices and transforms. In the third part, the authors discuss how the n-dimensional Hadamard matrices of order 2 are applied to feed-forward networking, stream ciphers, bent functions, and error correcting codes. They also cover the Boolean approach of Hadamard matrices. The final part provides examples of applications of Hadamard-related ideas to the design and analysis of one-dimensional sequences and two-dimensional arrays. The theory and ideas of Hadamard matrices can be used in many areas of communications and information security. Through the research problems found in this book, readers can further explore the fascinating issues and applications of the theory of higher-dimensional Hadamard matrices.

This volume presents the proceedings of the workshop CSL '91 (Computer Science Logic) held at the University of Berne, Switzerland, October 7-11, 1991. This was the fifth in a series of annual workshops on computer sciencelogic (the first four are recorded in LNCS volumes 329, 385, 440, and 533). The volume contains 33 invited and selected papers on a variety of logical topics in computer science, including abstract datatypes, bounded theories, complexity results, cut elimination, denotational semantics, infinitary queries, Kleene algebra with recursion, minimal proofs, normal forms in infinite-valued logic, ordinal processes, persistent Petri nets, plausibility logic, program synthesis systems, quantifier hierarchies, semantics of modularization, stable logic, term rewriting systems, termination of logic programs, transitive closure logic, variants of resolution, and many others.

This volume contains the proceedings of JELIA '92, les Journ es Europ ennes sur la Logique en Intelligence Artificielle, or the Third European Workshop on Logics in Artificial Intelligence. The volume contains 2 invited addresses and 21 selected papers covering such topics as: - Logical foundations of logic programming and knowledge-based systems, - Automated theorem proving, - Partial and dynamic logics, - Systems of nonmonotonic reasoning, - Temporal and epistemic logics, - Belief revision. One invited paper, by D. Vakarelov, is on arrow logics, i.e., modal logics for representing graph information. The other, by L.M. Pereira, J.J. Alferes, and J.N. Apar cio, is on default theory for well founded semantics with explicit negation.

This volume contains papers presented at the second International Workshop on Word Equations and Related Topics (IWWERT '91), held at the University ofRouen in October 1991. The papers are on the following topics: general solution of word equations, conjugacy in free inverse monoids, general A- and AX-unification via optimized combination procedures, wordequations with two variables, a conjecture about conjugacy in free groups, acase of termination for associative unification, theorem proving by combinatorial optimization, solving string equations with constant restriction, LOP (toward a new implementation of Makanin's algorithm), word unification and transformation of generalizedequations, unification in the combination of disjoint theories, on the subsets of rank two in a free monoid (a fast decision algorithm), and a solution of the complement problem in associative-commutative theories.