Decidability via Reduction in Logics and Their Combinations

Abstract: Decision problems in logic include semantic based problems like the satisfiability and the validity problems and deductive problems like the theoremhood and the consequence problems. Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in the meet-combination is proved to be decidable whenever the validity problems for the components are decidable. Some examples are discussed, namely, the meet-combination of modal logic and intuitionistic logic. Some ongoing work related to consequence problems in the context of consequence systems and their combination is pointed out. This talk reports on joint work with João Rasga and Walter Carnielli.

logic in computer sciencelogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic