Alexandre Duret-Lutz

Generalized Büchi automata versus testing automata for model checking

By Ala Eddine Ben Salem, Alexandre Duret-Lutz, Fabrice Kordon

2011-05-25

In Proceedings of the second international workshop on scalable and usable model checking for petri net and other models of concurrency (SUMO’11)

Abstract

Geldenhuys and Hansen have shown that a kind of $\omega$-automaton known as testing automata can outperform the Buchi automata traditionally used in the automata-theoretic approach to model checking (geldenhuys.06.spin?). This work completes their experiments by including a comparison with generalized Buchi automata; by using larger state spaces derived from Petri nets; and by distinguishing violated formulæ (for which testing automata fare better) from verified formulæ (where testing automata are hindered by their two-pass emptiness check).

Continue reading

On-the-fly emptiness check of transition-based Streett automata

By Alexandre Duret-Lutz, Denis Poitrenaud, Jean-Michel Couvreur

2009-10-01

In Proceedings of the 7th international symposium on automated technology for verification and analysis (ATVA’09)

Abstract

In the automata theoretic approach to model checking, checking a state-space $S$ against a linear-time property $\varphi$ can be done in $\mathrm{O}(|S|\times 2^{\mathrm{O}(|\varphi|)})$ time. When model checking under $n$ strong fairness hypotheses expressed as a Generalized Büchi automaton, this complexity becomes $\mathrm{O}(|S|\times 2^{\mathrm{O}(|\varphi|+n)})$.Here we describe an algorithm to check the emptiness of Streett automata, which allows model checking under $n$ strong fairness hypotheses in $\mathrm{O}(|S|\times 2^{\mathrm{O}(|\varphi|)}\times n)$. We focus on transition-based Streett automata, because it allows us to express strong fairness hypotheses by injecting Streett acceptance conditions into the state-space without any blowup.

Continue reading

An XML format proposal for the description of weighted automata, transducers, and regular expressions

By Akim Demaille, Alexandre Duret-Lutz, Florian Lesaint, Sylvain Lombardy, Jacques Sakarovitch, Florent Terrones

2008-07-28

In Post-proceedings of the seventh international workshop on finite-state methods and natural language processing (FSMNLP’08)

Abstract

We present an XML format that allows to describe a large class of finite weighted automata and transducers. Our design choices stem from our policy of making the implementation as simple as possible. This format has been tested for the communication between the modules of our automata manipulation platform Vaucanson, but this document is less an experiment report than a position paper intended to open the discussion among the community of automata software writers.

Continue reading

A static C++ object-oriented programming (SCOOP) paradigmc mixing benefits of traditional OOP and generic programming

By Nicolas Burrus, Alexandre Duret-Lutz, Thierry Géraud, David Lesage, Raphaël Poss

2003-10-29

In Proceedings of the workshop on multiple paradigm with object-oriented languages (MPOOL)

Abstract

Object-oriented and generic programming are both supported in C++. OOP provides high expressiveness whereas GP leads to more efficient programs by avoiding dynamic typing. This paper presents SCOOP, a new paradigm which enables both classical OO design and high performance in C++ by mixing OOP and GP. We show how classical and advanced OO features such as virtual methods, multiple inheritance, argument covariance, virtual types and multimethods can be implemented in a fully statically typed model, hence without run-time overhead.

Continue reading

Multi-band segmentation using morphological clustering and fusion: Application to color image segmentation

By Heru Xue, Thierry Géraud, Alexandre Duret-Lutz

2003-04-10

In Proceedings of the IEEE international conference on image processing (ICIP)

Abstract

In this paper we propose a novel approach for color image segmentation. Our approach is based on segmentation of subsets of bands using mathematical morphology followed by the fusion of the resulting segmentation channels. For color images the band subsets are chosen as RG, RB and GB pairs, whose 2D histograms are processed as projections of a 3D histogram. The segmentations in 2D color spaces are obtained using the watershed algorithm. These 2D segmentations are then combined to obtain a final result using a region split-and-merge process. The CIE L a b color space is used to measure the color distance. Our approach results in improved performance and can be generalized for multi-band segmentation of images such as multi-spectral satellite images information.

Continue reading

Generic implementation of morphological image operators

By Jérôme Darbon, Thierry Géraud, Alexandre Duret-Lutz

2002-04-01

In Mathematical morphology, proceedings of the 6th international symposium (ISMM)

Abstract

Several libraries dedicated to mathematical morphology exist. But they lack genericity, that is to say, the ability for operators to accept input of different natures —2D binary images, graphs enclosing floating values, etc. We describe solutions which are integrated in Olena, a library providing morphological operators. We demonstrate with some examples that translating mathematical formulas and algorithms into source code is made easy and safe with Olena. Moreover, experimental results show that no extra costs at run-time are induced.

Continue reading

Expression templates in Ada 95

By Alexandre Duret-Lutz

2001-05-01

In Proceedings of the 6th international conference on reliable software technologies (ada-europe)

Abstract

High-order matrix or vector expressions tend to be penalized by the use of huge temporary variables. Expression templates is a C++ technique which can be used to avoid these temporaries, in a way that is transparent to the user. We present an Ada adaptation of this technique which - while not transparent - addresses the same efficiency issue as the original. We make intensive use of the signature idiom to combine packages together, and discuss its importance in generic programming. Finally, we express some concerns about generic programming in Ada.

Continue reading

Applying generic programming to image processing

By Thierry Géraud, Yoann Fabre, Alexandre Duret-Lutz

2001-02-01

In Proceedings of the IASTED international conference on applied informatics (AI)—symposium on advances in computer applications

Abstract

This paper presents the evolution of algorithms implementation in image processing libraries and discusses the limits of these implementations in terms of reusability. In particular, we show that in C++, an algorithm can have a general implementation; said differently, an implementation can be generic, i.e., independent of both the input aggregate type and the type of the data contained in the input aggregate. A total reusability of algorithms can therefore be obtained; moreover, a generic implementation is more natural and does not introduce a meaningful additional cost in execution time as compared to an implementation dedicated to a particular input type.

Continue reading

Generic design patterns in C++

By Alexandre Duret-Lutz, Thierry Géraud, Akim Demaille

2001-01-01

In Proceedings of the 6th USENIX conference on object-oriented technologies and systems (COOTS)

Abstract

Generic programming is a paradigm whose wide adoption by the C++ community is quite recent. In this approach most classes and procedures are parameterized, leading to the construction of general and efficient software components. In this paper, we show how some design patterns from Gamma et al. can be adapted to this paradigm. Although these patterns rely highly on dynamic binding. We show that, by making intensive use of parametric polymorphism in the context of generic programming, the method calls in these patterns can be resolved at compile-time. The speed-up achieved using these patterns is significant.

Continue reading

Olena: A component-based platform for image processing, mixing generic, generative and OO programming

By Alexandre Duret-Lutz

2000-10-01

In Proceedings of the 2nd international symposium on generative and component-based software engineering (GCSE)—young researchers workshop; published in “net.ObjectDays2000”

Abstract

This paper presents Olena, a toolkit for programming and designing image processing chains in which each processing is a component. But since there exist many image types (different structures such as 2D images, 3D images or graphs, as well as different value types) the platform has been designed with genericity and reusability in mind: each component is written as a generic C++ procedure, à la STL. Other libraries, such as Khoros have a different approach where a processing component contains an implementation for each type supported by the library. This makes code maintenance hard and prevents easy addition of new image types. Still, Olena is not only a generic component library, it shall contain additional tools such as a visual programming environment (VPE). Those tools may be programmed in a classical object-oriented fashion (using operation and inclusion polymorphism) which may seems antagonist with the generic programming paradigm used in the library. Section 2 outlines the architecture of Olena and elaborates more on the design problems resulting from the use of generic components. Section 3 presents the solution chosen to address these problems.

Continue reading

Search

Tags