April 2016 - Annonce

publications: two papers accepted at Spin'15
by Alexandre Duret-Lutz 20 Jun '16

20 Jun '16

I am happy to announce that the following two papers have been accepted at the 22nd International SPIN Symposium on Model Checking of Software (SPIN 2015) to be held in Stellenbosch, South Africa on 24–26 August 2015. --- On Refinement of Büchi Automata for Explicit Model Checking František Blahoudek¹, Alexandre Duret-Lutz², Vojtěch Rujbr¹, and Jan Strejček¹ ¹Faculty of Informatics, Masaryk University, Brno, Czech Republic ²LRDE, EPITA, Le Kremlin-Bicêtre, France https://www.lrde.epita.fr/wiki/Publications/blahoudek.15.spin Abstract: In explicit model checking, systems are typically described in an implicit and compact way. Some valid information about the system can be easily derived directly from this description, for example that some atomic propositions cannot be valid at the same time. The paper shows several ways to apply this information to improve the Büchi automaton built from an LTL specification. As a result, we get smaller automata with shorter edge labels that are easier to understand andmore importantly, for which the explicit model checking process performs better. --- Practical Stutter-Invariance Checks for ω-Regular Languages Thibaud Michaud and Alexandre Duret-Lutz LRDE, EPITA, Le Kremlin-Bicêtre, France https://www.lrde.epita.fr/wiki/Publications/michaud.15.spin Abstract: We propose several automata-based constructions that check whether a specification is stutter-invariant. These constructions assume that a specification and its negation can be translated into Büchi automata, but aside from that, they are independent of the specification formalism. These transformations were inspired by a construction due to Holzmann and Kupferman, but that we broke down into two operations that can have different realizations, and that can be combined in different ways. As it turns out, implementing only one of these operations is needed to obtain a functional stutter-invariant check. Finally we have implemented these techniques in a tool so that users can easily check whether an LTL or PSL formula is stutter-invariant. -- Alexandre Duret-Lutz

3 2

New Publication: CIAA 2016
by Akim Demaille 26 Apr '16

26 Apr '16

We are happy to announce that the following paper was accepted to the 21st International Conference on Implementation and Application of Automata (CIAA 2016). Multitape Rational Expressions Akim Demaille EPITA/LRDE We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator | to build multitape expressions such as (a⁺|x + b⁺|y)*. We define expansions, which generalize the concept of derivative of a rational expression, but relieved from the need of a free monoid. We propose an algorithm based on expansions to build multitape automata from multitape expressions.

1 0

New Publication: TPAMI
by Yongchao Xu 12 Apr '16

12 Apr '16

We are pleased to announce that the following paper has been accepted for publication in the IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI). Find the title and abstract below. Title and corresponding authors: Hierarchical Segmentation Using Tree-Based Shape Spaces Yongchao Xu(13), Edwin Carlinet(1), Thierry Geraud(1), Laurent Najman(2) (1) LRDE, EPITA, Kremlin-Bicêtre, France (2) LIGM, Équipe A3SI, ESIEE Paris, 93160 Noisy-le-Grand, France (3) LTCI, CNRS, Téléecom ParisTech, 75013, Paris, France Abstract: Current trends in image segmentation are to compute a hierarchy of image segmentations from fine to coarse. A classical approach to obtain a single meaningful image partition from a given hierarchy is to cut it in an optimal way, following the seminal approach of the scale-set theory. While interesting in many cases, the resulting segmentation, being a non-horizontal cut, is limited by the structure of the hierarchy. In this paper, we propose a novel approach that acts by transforming an input hierarchy into a new saliency map. It relies on the notion of shape space: a graph representation of a set of regions extracted from the image. Each region is characterized with an attribute describing it. We weigh the boundaries of a subset of meaningful regions (local minima) in the shape space by extinction values based on the attribute. This extinction-based saliency map represents a new hierarchy of segmentations highlighting regions having some specific characteristics. Each threshold of this map represents a segmentation which is generally different from any cut of the original hierarchy. This new approach thus enlarges the set of possible partition results that can be extracted from a given hierarchy. Qualitative and quantitative illustrations demonstrate the usefulness of the proposed method.

1 0

Spot 2.0 has been released
by Alexandre Duret-Lutz 11 Apr '16

11 Apr '16

We are happy to announce the release of Spot 2.0! Spot is a C++ library for model checking and manipulation of temporal logic formula and omega-automata. It also comes with command-line tools and Python bindings. You can find the new release here: http://www.lrde.epita.fr/dload/spot/spot-2.0.tar.gz See https://spot.lrde.epita.fr/ for documentation and installation instructions. Spot 2.0 is the result of 28 months of work, as we starting working on this branch after the release of Spot 1.2.1 (Dec 2013). It includes contributions from Alexandre Lewkowicz, Amaury Fauchille, Étienne Renault, Laurent Xu, Thibaud Michaud, and myself. For people upgrading from Spot 1.2.6 (or older), the main news are as follows: * Automata now support acceptance conditions expressed as arbitrary formulas over "marks" that must be seen infinitely often or finitely often. * The C++ API has been seriously overhauled and now requires a C++11 compiler. Backward compatibility has been broken in many ways: see https://spot.lrde.epita.fr/upgrade2.html for help about migrating old code. But now that the dust has settled, you should not expect further API breakage in upcoming 2.x releases. * The shell commands now include tools for processing automata. See https://spot.lrde.epita.fr/tools.html for a list of all the tools, and check https://spot.lrde.epita.fr/autfilt.html in particular. The default interchange format is the Hanoi Omega Automata format (HOA), but other formats are supported as well. * The Python bindings are more complete, and even allow prototyping low-level algorithms (for instance the page https://spot.lrde.epita.fr/ipynb/product.html shows how to implement a product of two automata with arbitrary acceptance). Python bindings also interface nicely with IPython/Jupyter notebooks. See https://spot.lrde.epita.fr/tut.html for short examples of various tasks implemented in shell, C++, and Python. For those upgrading from 1.99.9, the difference with Spot 2.0 is rather thin. The following changes were included in Spot 2.0 (2016-04-11): Command-line tools: * ltlfilt now also support the --accept-word=WORD and --reject-word=WORD options that were introduced in autfilt in the previous version. Python: * The output of spot.atomic_prop_collect() is printable and can now be passed directly to spot.ltsmin.model.kripke(). Library: * digraph::valid_trans() renamed to digraph::is_valid_edge(). Documentation: * The concepts page (https://spot.lrde.epita.fr/concepts.html) now includes a highlevel description of the architecture, and some notes aboute automata properties. * More Doxygen documentation for spot::formula and spot::digraph. See https://gitlab.lrde.epita.fr/spot/spot/blob/spot-2-0/NEWS for the complete history of NEWS entries across previous releases. Please direct any feedback to <spot(a)lrde.epita.fr>. -- Alexandre Duret-Lutz

1 0

[CFPart] ELS'16, 9th European Lisp Symposium, May 9-10, Kraków, Poland
by Didier Verna 06 Apr '16

06 Apr '16

ELS'16 - 9th European Lisp Symposium Department of Computer Science AGH University of Science and Technology Kraków, Poland May 9-10, 2016 In cooperation with: ACM SIGPLAN Sponsored by EPITA, Franz Inc., LispWorks Ltd., IdEx and Dept. of Computer Science AGH UST http://www.european-lisp-symposium.org/ Recent news: - Full programme now available online - Registration now open (early registration deadline: April 25) The purpose of the European Lisp Symposium is to provide a forum for the discussion and dissemination of all aspects of design, implementation and application of any of the Lisp and Lisp-inspired dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, Hop and so on. We encourage everyone interested in Lisp to participate. Keynote speakers: - Pierre Castéran -- Program Proving with Coq - Stephan Karpinski -- Julia: to Lisp or Not to Lisp? - Francis Sergeraert -- Lexical Closures and Complexity Important dates: - 25 Apr 2016 Early registration deadline - 9-10 May 2016 Symposium Programme chair: Irène Durand, LaBRI, University of Bordeaux, France Local chair: Michał Psota, Emergent Network Defense, Kraków, Poland Programme committee: Antonio Leitao — INESC-ID / Instituto Superior Técnico, Universidade de Lisboa, Portugal Charlotte Heerzel — IMEC, Leuven, Belgium Christian Queinnec — University Pierre et Marie Curie, Paris 6, France Christophe Rhodes — Goldsmiths, University of London, United Kingdom Didier Verna — EPITA Research and Development Laboratory, France Erick Gallesio — University of Nice-Sophia Antipolis, France François-René Rideau, Google, USA Giuseppe Attardi — University of Pisa, Italy Kent Pitman, HyperMeta Inc., USA Leonie Dreschler-Fischer — University of Hamburg, Germany Pascal Costanza — Intel Corporation, Belgium Robert Strandh — University of Bordeaux, France Search Keywords: #els2016, ELS 2016, ELS '16, European Lisp Symposium 2016, European Lisp Symposium '16, 9th ELS, 9th European Lisp Symposium, European Lisp Conference 2016, European Lisp Conference '16 -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

1 0

New Publication: STTT
by Etienne Renault 06 Apr '16

06 Apr '16

We are pleased to announce that the following paper has been accepted for publication in the International Journal on Software Tools for Technology Transfer (STTT). Find the title and abstract below. Title and corresponding authors: Variations on Parallel Explicit Emptiness Checks for Generalized Büchi Automata Etienne Renault(1), Alexandre Duret-Lutz(1), Fabrice Kordon(2,3) and Denis Poitrenaud(3,4) (1) LRDE, EPITA, Kremlin-Bicêtre, France (2) Sorbonne Universités, UPMC Univ. Paris 06, France (3) CNRS UMR 7606, LIP6, F-75005 Paris, France (4) USPC, Université Paris Descartes, Paris, France Abstract: We present new parallel explicit emptiness checks for LTL model checking. Unlike existing parallel emptiness checks, these are based on a Strongly Connected Component (SCC) enumeration, support generalized Büchi acceptance, and require no synchronization points nor recomputing procedures. A salient feature of our algorithms is the use of a global union-find data structure in which multiple threads share structural information about the automaton checked. Besides these basic algorithms, we present one architectural variant isolating threads that write to the union-find, and one extension that decomposes the automaton based on the strength of its SCCs to use more optimized emptiness checks. The results from an extensive experimentation of our algorithms and their variations show encouraging performances, especially when the decomposition technique is used.

1 0