Search Results

Deduction systems are computer procedures that employ inference or transition rules, search strategies, and multiple supporting algorithms, to solve problems by logico-deductive reasoning. They are at the heart of SAT/SMT solvers, theorem provers, and proof assistants. The wide range of successful applications of these tools shows how logico-deductive reasoning is well-suited for machines. Nonetheless, satisfiability and validity are difficult problems, and applications require reasoners to handle large and heterogeneous knowledge bases, and to generate proofs and models of increasing size and diversity. Thus, a vast array of techniques was developed, leading to what was identified during the seminar as a crisis of growth. This crisis manifests itself also as a software crisis, called automated reasoning software crisis at the seminar. Many deduction systems remain prototypes, while relatively few established systems resort to assemble techniques into portfolios that are useful for experiments, but do not lead to breakthroughs. In order to address this crisis of growth, the Dagstuh Seminar "The Next Generation of Deduction Systems: From Composition to Compositionality" (23471) focused on the key concept of composition, that is, a combination where properties of the components are preserved. Composition applies to all building blocks of deduction: rule systems, strategies, proofs, and models. All these instances of compositions were discussed during the seminar, including for example composition of instance-based and superposition-based inference systems, and composition of modules towards proof production in SMT solvers. Other kinds of composition analyzed during the seminar include the composition of reasoning and learning, and the composition of reasoning systems and knowledge systems. Indeed, reasoners learn within and across derivations, while for applications, from verification to robotics, provers and solvers need to work with other knowledge-based components. In order to address the automated reasoning software crisis, the seminar elaborated the concept of compositionality, as the engineering counterpart of what is composition at the theory and design levels. The seminar clearly identified modularity as the first step towards compositionality, proposing to decompose existing systems into libraries of modules that can be recomposed in new systems. The ensuing discussion led to the distinction between automated reasoners that are industry powertools and automated reasoners that are pedagogical tools. At the societal level, this distinction is important to counter the phenomenon whereby new students are either discouraged by the impossibility of competing with industry powertools, or induced to join only those research groups that work on industry powertools. In summary, the seminar fully succeeded in promoting the exchange of ideas and suggestions for future work.

Logical reasoning plays a key role in fields as diverse as verification and synthesis, programming language foundations, knowledge engineering, and computer mathematics. Logical reasoning is increasingly important in intelligent systems, such as decision support systems, agent programming environments, and data processing systems, where deduction may provide explanation, course of action, and the capability of learning from missing information. Problem formalization in these domains typically involves multiple mathematical theories, knowledge bases, and ontologies, all of which may be very large. Problem solving requires both efficient automation and sophisticated human-machine interaction. The thrust of this seminar was that the key to unleash the power of computerized logical reasoning is integration, at different abstraction levels. This seminar offered a forum to discuss the issues related to integration of deduction in a diverse range of applications. In terms of reasoning procedures, the presence of both theories and quantifiers in problems from many contexts calls for methodologies to integrate state-of-the-art SMT solvers and automated theorem provers. This leads to investigate techniques such as model-based reasoning and semantic guidance, that were presented and discussed at the seminar. Similarly, the integration of inference rules for higher-order reasoning in inference systems that were born for first-order reasoning, such as superposition, was prominent among the topics debated at the seminar. At the architectural level, the sheer difficulty of the problems calls for the integration of provers and solvers into interactive reasoning environments. These range from higher-order proof assistants with background reasoners as hammers, to interactive program verifiers, both widely covered at the seminar in talks and discussions. The seminar showed how the application of deduction to intelligent systems necessitates the integration of deduction with other paradigms, such as probabilistic reasoning and statistical inferences. In fact, it emerged from the seminar that even systems that are not natively deductive, such as agent programming environments and industrial tools for ontology-based processing, benefit significantly from the integration of deduction. A clear and shared uptake from the seminar was that scalability and usability are crucial challenges at all levels of integration. The seminar fully succeded in promoting the exchange of new ideas and suggestions for future research.