This work deals with logical formalization and problem solving using automated solvers. We present the automatic translator TouIST that provides a simple language to generate logical formulas from a problem description. Our tool allows us to model many static or dynamic combinatorial problems and to benefit from the regular improvements of SAT, QBF or SMT solvers in order to solve these problems efficiently. In particular, we show how to use TouIST to solve different classes of planning tasks in Artificial Intelligence.

If work in psychology has clearly brought to light that ‘conceptual flexibility’ exists in the categorization of objects, which led to re-questioning the traditional conception of categorization which considers rigid and discontinuous categories, it is not the case in linguistics and psycholinguistics. We propose, through highlighting the role of analogy in the categorization of verbs, to defend the idea of semantic flexibility which constitutes a linguistic counterpart to psychologists' advances on categorization. Accordingly, it is shown that the production of ‘metaphoric’ verbal utterances by adults and more particularly by 2/3-year-old children reflects analogical categorization of verbs which makes it possible to argue in favour of a computational model of the role of analogy in the semantic network of the verb lexicon.

In this paper we present a decision procedures for modal logics with transitive models together with additionnal properties like confluence and density. These procedures are tableaux-based, and we show how to handle them in this well-known framework by generalizing usual tableaux (which are trees) to richer structures: directed acyclic graphs.

We present the basic framework of a logic of actions and plans defined in terms of modal logic combined with a notion of dependence. The latter is used as a weak causal connection between actions and literals. In this paper we focus on the frame problem and demonstrate how it can be solved in our framework in a simple and monotonic way. We give the semantics, and associate an axiomatics and a decision procedure to it. The decision procedure is based on a sound and complete tableau method with single step rules to treat dependence. We show how it can be used to generate plans. Our solution is formally assessed by a translation of Gelfond and Lifschitz' logic A. We briefly sketch the second part of the paper, showing how we can go beyond A by some examples involving nondeterminism and ramifications.

In this paper we generalize the existing tableau methods for modal logics. First of all, while usual modal tableaux are based on trees, our basic structures are rooted directed acyclic graphs (RDAG). This allows natural tableau rules for some modal logics that are difficult to capture in the usual way (such as those having an accessibility relation that is dense or confluent). Second, tableau rules rewrite patterns, which are (schemas of) parts of a RDAG. A particular case of these rules are the single-step rules recently proposed by Massacci. This allows in particular tableau rule presentations for K5, KD5, K45, KD45, and S5 that respect the subformula property. Third, we divide modal tableau rules into propagation rules and structural rules. Structural rules construct new edges and nodes (without adding formulas to nodes), while propagation rules add formulas to nodes. This distinction allows to prove completeness in a modular way.

We prove that a natural and simple predicate modal logic with the Barcan formula, namely QBF-KD plus the axiom of density, is not Kripke complete. Although incompleteness results are known in Kripke semantics, most of the methods used can only apply to logics stronger than QBF-S4 as they are based in a translation from intermediate logics. We give here an original proof of this incompleteness result.