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
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.
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.
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
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
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.
