IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Charlas Invitadas > 2014 > Counting Models of Linear-time Temporal Logic
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Hazem Torfah

miércoles 12 de marzo de 2014

10:30am Meeting room 302 (Mountain View), level 3

Hazem Torfah, PhD Student, Saarland University, Germany

Counting Models of Linear-time Temporal Logic

Abstract:

We investigate the model counting problem for safety speci- fications expressed in linear-time temporal logic (LTL). Model counting has previously been studied for propositional logic; in planning, for example, propositional model counting is used to compute the plan’s robust- ness in an incomplete domain. Counting the models of an LTL formula opens up new applications in verification and synthesis. We distinguish word and tree models of an LTL formula. Word models are labeled sequences that satisfy the formula. Counting the number of word models can be used in model checking to determine the number of errors in a system. Tree models are labeled trees where every branch satisfies the formula. Counting the number of tree models can be used in synthesis to determine the number of implementations that satisfy a given formula. We present algorithms for the word and tree model counting problems, and compare these direct constructions to an indirect approach based on encodings into propositional logic.