Decision and feasibility problems in verification based on predicate logics A. Slissenko University Paris 12 The purpose of this talk is to discuss some results, open questions and possible approaches to the development efficient decidability algorithms for verification in the framework of predicate logics with explicit time. The application domain is (timed) distributed algorithms, in particular, cryptographic protocols.