This book constitutes the refereed proceedings of the International Seminar on Proof Theory in Computer Science, PTCS 2001, held in Dagstuhl Castle, Germany, in October 2001. The 13 thoroughly revised full papers were carefully reviewed and selected for inclusion in the book. Among the topics addressed are higher type recursion, lambda calculus, complexity theory, transfinite induction, categories, induction-recursion, post-Turing analysis, natural deduction, implicit characterization, iterate logic, and Java programming.
The book is meant to serve two purposes. The first and more obvious one is to present state of the art results in algebraic research into residuated structures related to substructural logics. The second, less obvious but equally important, is to provide a reasonably gentle introduction to algebraic logic. At the beginning, the second objective is predominant. Thus, in the first few chapters the reader will find a primer of universal algebra for logicians, a crash course in nonclassical logics for algebraists, an introduction to residuated structures, an outline of Gentzen-style calculi as well as some titbits of proof theory - the celebrated Hauptsatz, or cut elimination theorem, among them. These lead naturally to a discussion of interconnections between logic and algebra, where we try to demonstrate how they form two sides of the same coin. We envisage that the initial chapters could be used as a textbook for a graduate course, perhaps entitled Algebra and Substructural Logics. As the book progresses the first objective gains predominance over the second. Although the precise point of equilibrium would be difficult to specify, it is safe to say that we enter the technical part with the discussion of various completions of residuated structures. These include Dedekind-McNeille completions and canonical extensions. Completions are used later in investigating several finiteness properties such as the finite model property, generation of varieties by their finite members, and finite embeddability. The algebraic analysis of cut elimination that follows, also takes recourse to completions. Decidability of logics, equational and quasi-equational theories comes next, where we show how proof theoretical methods like cut elimination are preferable for small logics/theories, but semantic tools like Rabin's theorem work better for big ones. Then we turn to Glivenko's theorem, which says that a formula is an intuitionistic tautology if and only if its double negation is a classical one. We generalise it to the substructural setting, identifying for each substructural logic its Glivenko equivalence class with smallest and largest element. This is also where we begin investigating lattices of logics and varieties, rather than particular examples. We continue in this vein by presenting a number of results concerning minimal varieties/maximal logics. A typical theorem there says that for some given well-known variety its subvariety lattice has precisely such-and-such number of minimal members (where values for such-and-such include, but are not limited to, continuum, countably many and two). In the last two chapters we focus on the lattice of varieties corresponding to logics without contraction. In one we prove a negative result: that there are no nontrivial splittings in that variety. In the other, we prove a positive one: that semisimple varieties coincide with discriminator ones. Within the second, more technical part of the book another transition process may be traced. Namely, we begin with logically inclined technicalities and end with algebraically inclined ones. Here, perhaps, algebraic rendering of Glivenko theorems marks the equilibrium point, at least in the sense that finiteness properties, decidability and Glivenko theorems are of clear interest to logicians, whereas semisimplicity and discriminator varieties are universal algebra par exellence. It is for the reader to judge whether we succeeded in weaving these threads into a seamless fabric.
A logic view of 0-1 integer programming problems, providing new insights into the structure of problems that can lead the researcher to more effective solution techniques depending on the problem class. Operations research techniques are integrated into a logic programming environment. The first monographic treatment that begins to unify these two methodological approaches. Logic-based methods for modelling and solving combinatorial problems have recently started to play a significant role in both theory and practice. The application of logic to combinatorial problems has a dual aspect. On one hand, constraint logic programming allows one to declaratively model combinatorial problems over an appropriate constraint domain, the problems then being solved by a corresponding constraint solver. Besides being a high-level declarative interface to the constraint solver, the logic programming language allows one also to implement those subproblems that cannot be naturally expressed with constraints. On the other hand, logic-based methods can be used as a constraint solving technique within a constraint solver for combinatorial problems modelled as 0-1 integer programs.
Formal methods enable computer architecture and software design to be mathematically proved correct before they are implemented. The complexity and time-consuming nature of such proofs have limited the applications of formal methods in the main to defence and safety-critical applications. The mural project (a joint Alvey-funded project between Manchester University and Rutherford Appleton Laboratories) has developed a software support system to help the user of formal methods. mural has created a user-friendly software environment (with extensive use of windows) that makes best use of human talents to produce computer systems that are proved to be correctly designed. Professor Cliff Jones is internationally known as the developer of the VDM system of formal notation (Vienna Development Method). This book describes the requirements, concepts, and realisation of the mural system. The authors present systematically and completely the results of this substantial research project, from the basic theoretical level to its effective implementation. The book will be of equal interest to academics working on formal methods at research level (and perhaps to graduate research students), and to practitioners and software engineers who are using - or who will have to use for defence contracts, etc. - formal methods.
This volume constitutes the refereed proceedings of the Fourth International Conference on Conceptual Structures, ICCS '96, held in Sydney, Australia, in August 1996. The book presents five full papers by the invited speakers together with 15 revised full papers selected for presentation at the conference from a respectable number of submissions. The issues addressed are natural language processing, information retrieval, graph operations, conceptual graph and Peirce theory, knowledge acquisition, theorem proving and CG programming, and order-based organisation and encoding.
This book constitutes the refereed proceedings of the First International Workshop on Cooperative Information Agents - DAI Meets Databases, CIA-97, held in Kiel, Germany, in February 1997. The book opens with 6 invited full papers by internationally leading researchers surveying the state of the art in the area. The 16 revised full research papers presented were carefully selected during a highly competitive round of reviewing. The papers are organized in topical sections on databases and agent technology, agents for database search and knowledge discovery, communication and cooperation among information agents, and agent-based access to heterogeneous information sources.
The ECOOP '91 Workshop on Object-Based Concurrent Computing was organized toprovide a forum on concurrent, distributed and open-ended computing. The emphasis was on conceptual, theoretical and formal aspects, as well as practical aspects and sound experience, since such a viewpoint was deemed indispensible to investigate and establish a basis for future development. This volume contains 12 papers selected from 25 presented at the workshop, together with a paper by J.A. Goguen, who was an invited speaker at the workshop. The papers are classified into four categories: Formal methods (1): three papers are concerned with the formal semantics of concurrent objects based on process calculi. Formal methods (2): four papers are concerned with various formal approaches to the semantics of concurrent programs. Concurrent programming: three papers. Models: three papers areconcerned with models for concurrent systems.
The International Workshop on Compiler Construction provides a forum for thepresentation and discussion of recent developments in the area of compiler construction. Its scope ranges from compilation methods and tools to implementation techniques for specific requirements of languages and target architectures. This volume contains the papers selected for presentation at the 4th International Workshop on Compiler Construction, CC '92, held in Paderborn, Germany, October 5-7, 1992. The papers present recent developments on such topics as structural and semantic analysis, code generation and optimization, and compilation for parallel architectures and for functional, logical, and application languages.
Term indexing supports the construction of efficient automated reasoning systems, as e.g. automated theorem provers, by allowing rapid access to first order predicate calculus terms with specific properties. This monograph provides a comprehensive, well-written survey on term indexing in general and presents new indexing techniques for the retrieval and maintenance of data that help to overcome program degradation in automated reasoning systems. Theoretical foundations and applicational aspects are treated in detail; finally the PURR prover for parallel unit resulting resolution is discussed to demonstrate the importance of careful implementations.
The theme of this book is the potential of new advanced database systems. The volume presents the proceedings of the 10th British National Conference on Databases, held in Aberdeen, Scotland, in July 1992. The volume contains two invited papers, one on the promise of distributed computing andthe challenges of legacy systems by M.L. Brodie, and the other on object-oriented requirements capture and analysis and the Orca project by D.J.L. Gradwell. The following four parts each contain three submitted papers selected from a total of 36 submissions. The parts are entitled: - Object-oriented databases - Parallel implementationsand industrial systems - Non-relational data models - Logic programming and databases
Thank you for visiting our website. Would you like to provide feedback on how we could improve your experience?
This site does not use any third party cookies with one exception — it uses cookies from Google to deliver its services and to analyze traffic.Learn More.