- Contacts/Reaching LIFO
- Teaching
Contact
LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2
Email:
contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37
Go to Research Reports of Year : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018
RR-2000-01 Confluence of the BSlambda_p calculus
F. LOULERGUE
Abstract :
Keywords :
RR-2000-03 A symmetric frequency-adaptative join algorithm for Shared Nothing machines
M. BAMHA, G. HAINS
Abstract : Research has shown that the join operation is parallelizable with near-linear speed-up on shared nothing machines only under ideal balancing conditions. Data skew can have a disastrous effect on performance. Although many skew-handling algorithms have been proposed they remain generally inefficient in the case of multi-joins due to join product skew, costly and unnecessary redistribution and communication costs. A parallel join algorithm called fa_join (frequency-adaptive join) has been introduced in an earlier paper with deterministic and near-perfect balancing properties. Despite its advantages, fa_join is sensitive to the correlation of the attribute value distributions in both relations. We present here an improved version of the algorithm called Sfa_join with a symmetric treatment of both relations. Its predictably low join-product and attribute-value skew makes it suitable for repeated use in multi-join operations. Its tradeoff between balancing overhead and speedup is analyzed using the scalable and portable BSP (BSP : Bulk-synchronous parallelism) cost model which predicts a negligible join product skew and a near-linear speed-up. This prediction is confirmed by a series of tests, some of which show the algorithm's superiority over its predecessor: fa_join.
Keywords : PDBMS (Parallel Database Management Systems); Intra-transaction parallelism; Parallel joins; Multi-joins; Data-skew; Join-product skew; Dynamic load balancing.
RR-2000-04 Chaotic iterations for constraint propagation and labeling
J. ARSOUZE, G. FERRAND, A. LALLOUET
Abstract : Here is an attempt to define a uniform semantic framework for constraint solving based on chaotic iterations and downward closure operators, taking into account both propagation and labeling. We extend the formalism of Montanari and Rossi cite{MontanariR:AI91} with more general rules of two kinds: while relaxation rules narrow the search space and preserve solutions, new restriction rules split the search space to explore it piece by piece. We show that independence of the computed approximation extends in some sense to labeling. Moreover, this framework can be used to model various approaches including the glass-box one used for finite domain constraint solving in Gnu-Prolog.
Keywords : constraint propagation; chaotic iterations; labeling; co-induction; semantics
RR-2000-05 An optimal and skew-insensitive join algorithm for Shared Nothing machines
M. BAMHA
Abstract : Joins constitute a computation-intensive part of database request and their parallelization is necessary for dealing with very large data sets. However, effectiveness of parallel joins depends on the ability to evenly divide load among processors. Research has shown that the join operation is parallelizable with near-linear speed-up on shared nothing machines only under ideal balancing conditions. Data skew can have a disastrous effect on performance. Although many skew-handling algorithms have been proposed they remain generally inefficient in the case of multi-joins due to join product skew, costly and unnecessary redistribution and communication costs. In this paper, we introduce a new parallel join algorithm with optimal complexity and deterministic perfect balancing. Its predictably low join-product and attribute-value skews makes it suitable for repeated use in multi-join operations. Its tradeoff between balancing overhead and speedup is analyzed using the scalable and portable BSP (Bulk Synchronous parallel) cost model which predicts a negligible join product skew and a near-linear speed-up. The algorithm presented here, improves our fa_join and sfa_join algorithms by reducing their communication and synchronisation cost to a minimum while offering the same load balancing properties.
Keywords : PDBMS (Parallel Database Management Systems); Intra-transaction parallelism; Parallel joins; Multi-joins; Data-skew; Join-product skew; Dynamic load balancing
RR-2000-06 Partitionable graphs arising from near-factorizations of finite groups
A. PECHER
Abstract : Since a counter-example to the Strong Perfect Graph Conjecture would be a partitionable graph, any 'new' construction for making partitionable graphs is of interest. In this paper, we investigate the near-factorizations of finite groups in general, and their associated Cayley graphs which are all partitionable. In particular we show that near-factorizations of the dihedral groups produce every CGPW graph of even order. We present some results about near-factorizations in finite groups which imply that a finite abelian group with a near-factorization (A,B) such that the cardinal of A is at most four, must be cyclic (already proved. One of these results may be used to speed up exhaustive calculations. At last, we prove that there is no counter-example to the Strong Perfect Graph Conjecture arising from near-factorizations of a finite abelian group of even order.
Keywords : partitionable; perfect; graph; near-factorization; group
RR-2000-07 Titre a venir
F. MOAL
Abstract :
Keywords :
RR-2000-08 Located concurrent constraint programming
N. ROMERO
Abstract : The Located Concurrent Constraint Programming model enhances the Saraswat's Concurrent Constraint Programming framework (cc) with distribution- and time-aware primitives. The unique global constraint store is split into several locations, which are local stores together with some associated processes. Each one can be dynamically created and moves on its own initiative to be interfaced with others. Multiform time awareness appears with the ability to detect local store modifications, to start and to suspend locations. A formal syntax and its operational semantics are defined. We then discuss several examples to show that these minimal changes lead to a powerful distributed concurrent constraint framework.
Keywords : Constraint Programming; Concurrent Programming; Distributed Programming; Operational Semantics.
RR-2000-09 Value withdrawal explanation in CLP
G. FERRAND, W. LESAINT, A. TESSIER
Abstract : This work is devoted to constraint solving motivated by the debugging of constraint logic programs a la GNU-Prolog. The paper focuses only on the constraints. In this framework, constraint solving amounts to domain reduction. A computation is formalized by a chaotic iteration. The computed result is described as a closure. This model is well suited to the design of debugging notions and tools, for example failure explanations or error diagnosis. In this paper we detail an application of the model to an explanation of a value withdrawal in a domain. Some other works have already shown the interest of such a notion of explanation not only for failure analysis.
Keywords : CSP; debugging; explanation; constraint programmation
RR-2000-10 Actes des journées de vérification formelle
Pierre RETY (editor)
Abstract :
Keywords :
RR-2000-11 Cayley partitionable graphs
A. PECHER
Abstract : In this paper we investigate the class of Cayley partitionable graphs. This investigation is motivated by the Strong Perfect Graph Conjecture. Cayley partitionable graphs are Cayley Graphs which are closely related to near-factorizations of finite groups. We prove that near-factorizations satisfy a strong structural property. We used it to speed up exhaustive computations, which revealed a Cayley partitionable graph with fifty vertices, which is not generated by all constructions of partitionable graphs known so far.
Keywords : partitionable; perfect; Cayley; graph; near-factorization; group
RR-2000-12 About facets of the stable set polytope of a graph
A. PECHER
Abstract : No complete characterization of rank facet producing graphs is known. In 1977, Balas and Zemel gave a necessary for a graph to be rank-facet producing, and in 1975, Chvátal gave a sufficient condition, which motivated the study of the class of critical graphs. We give two strengthening of Balas and Zemel's necessary condition, and one of Chvátal's sufficient condition.
Keywords : graph; stable set polytope; vertex packing polytope; facet; rank facet
RR-2000-13 A condition for a graph to contain k independent edges
A. P. WOJDA
Abstract : Let k, l, n be nonnegative integers such that 0< k < n/2, and let G be a graph of order n with the minimum vertex-degree at most l. We find the minimum function F such that if the size e(G) of G verifies e(G) > F(n,k,l) then G contains the matching of size k. Moreover, if e(G) = F(n,k,l) and G contains no matching of size k, then l
Keywords : graph; subgraph; forest.
RR-2000-14 On self-complementary supergraphs of (n,n) graphs
A. P. WOJDA, M. WOZNIAK, I. A. ZIOLO
Abstract : We prove that, with one exception, each (n,n)-graph G that is embeddable in its complement has a self-complementary supergraph of order n.
Keywords : graph; embedding; self-complementary graph.
RR-2000-15 Une version parallèle extensible de l'algorithme Particle Mesh Ewald
S. DROURI, G. HAINS
Abstract : We present the results of an applied mini-project conducted as part of the iHPerf'98 initiative of the ARP CNRS-GDR research network. The project was a collaboration with the CNRS-Orléans' CBM (biomolecular research center) and supported by ARP. It deals with the scalability analysis and parallel implementation of the Particle Mesh Ewald (PME) algorithm, which plays a fundamental role in molecular simulation: it evaluates electrostatic interactions. We propose a parallel version of PME for distributed-memory architectures. It optimises the ratio of computation, communication and synchronisation according the the BSP (bulk-synchronous parallelism) model. A new scalable parallel version of the Fast Fourier Transform (FFT) is also proposed since PME requires this algorithm. Our first tests on a Cray T3E architecture show an almost-linear acceleration.
Keywords : Molecular simulation; electrostatic interactions; Particle Mesh Ewald algorithm; parallel algorithms; scalability;
RR-2000-16 Synchronized Tree Languages Revisited and New Applications
V. GOURANTON, P. RETY, H. SEIDL
Abstract : We present a new formulation for tree-tuple synchronized languages, much simpler than the existing one. This new formulation allows us to prove stronger structural results. As a consequence, synchronized languages give rise to new applications : - to rewriting : given tree languages L1 (synchronized), L2 (regular), Rel(L1) subset of L2 is decidable for several rewrite-like relations Rel. - to concurrency : we prove decidability of the logic EF for a process calculus allowing some bounded form of communication. Consequently, the absence of deadlocks is decidable.
Keywords : tree-tuple language; rewriting; concurrency
RR-2000-17 Weakly Regular Relations and Applications
S. LIMET, P. RETY, H. SEIDL
Abstract : A new class of tree-tuple languages is introduced : the weakly regular relations. It is an extension of the regular case (regular relations) and a restriction of tree-tuple synchronized languages, that has all usual nice properties, except closure by complement. Two applications are presented : to unification modulo a rewrite system, and to one-step rewriting.
Keywords : Tree language; Rewriting; Unification
LIFO Research Report for Year 2000
RR-2000-01
Confluence of the BSlambda_p calculus
F. LOULERGUE
Date : 2000-00-00
Abstract
RR-2000-03
A symmetric frequency-adaptative join algorithm for Shared Nothing machines
M. BAMHA, G. HAINS
Date : 2000-02-22
Abstract Download
RR-2000-04
Chaotic iterations for constraint propagation and labeling
J. ARSOUZE, G. FERRAND, A. LALLOUET
Date : 2000-03-23
Abstract Download
RR-2000-05
An optimal and skew-insensitive join algorithm for Shared Nothing machines
M. BAMHA
Date : 2000-04-21
Abstract Download
RR-2000-06
Partitionable graphs arising from near-factorizations of finite groups
A. PECHER
Date : 2000-04-27
Abstract Download
RR-2000-07
Titre a venir
F. MOAL
Date : 2000-00-00
Abstract Download
RR-2000-08
Located concurrent constraint programming
N. ROMERO
Date : 2000-05-16
Abstract Download
RR-2000-09
Value withdrawal explanation in CLP
G. FERRAND, W. LESAINT, A. TESSIER
Date : 2000-05-17
Abstract Download
RR-2000-10
Actes des journées de vérification formelle
Pierre RETY (editor)
Date : 2000-06-08
Abstract Download
RR-2000-11
Cayley partitionable graphs
A. PECHER
Date : 2000-09-18
Abstract Download
RR-2000-12
About facets of the stable set polytope of a graph
A. PECHER
Date : 2000-09-18
Abstract Download
RR-2000-13
A condition for a graph to contain k independent edges
A. P. WOJDA
Date : 2000-09-20
Abstract Download
RR-2000-14
On self-complementary supergraphs of (n,n) graphs
A. P. WOJDA, M. WOZNIAK, I. A. ZIOLO
Date : 2000-09-20
Abstract Download
RR-2000-15
Une version parallèle extensible de l'algorithme Particle Mesh Ewald
S. DROURI, G. HAINS
Date : 2000-10-10
Abstract Download
RR-2000-16
Synchronized Tree Languages Revisited and New Applications
V. GOURANTON, P. RETY, H. SEIDL
Date : 2000-10-24
Abstract Download
RR-2000-17
Weakly Regular Relations and Applications
S. LIMET, P. RETY, H. SEIDL
Date : 2000-12-05
Abstract Download
Abstracts of Research Reports
RR-2000-01 Confluence of the BSlambda_p calculus
F. LOULERGUE
Abstract :
Keywords :
RR-2000-03 A symmetric frequency-adaptative join algorithm for Shared Nothing machines
M. BAMHA, G. HAINS
Abstract : Research has shown that the join operation is parallelizable with near-linear speed-up on shared nothing machines only under ideal balancing conditions. Data skew can have a disastrous effect on performance. Although many skew-handling algorithms have been proposed they remain generally inefficient in the case of multi-joins due to join product skew, costly and unnecessary redistribution and communication costs. A parallel join algorithm called fa_join (frequency-adaptive join) has been introduced in an earlier paper with deterministic and near-perfect balancing properties. Despite its advantages, fa_join is sensitive to the correlation of the attribute value distributions in both relations. We present here an improved version of the algorithm called Sfa_join with a symmetric treatment of both relations. Its predictably low join-product and attribute-value skew makes it suitable for repeated use in multi-join operations. Its tradeoff between balancing overhead and speedup is analyzed using the scalable and portable BSP (BSP : Bulk-synchronous parallelism) cost model which predicts a negligible join product skew and a near-linear speed-up. This prediction is confirmed by a series of tests, some of which show the algorithm's superiority over its predecessor: fa_join.
Keywords : PDBMS (Parallel Database Management Systems); Intra-transaction parallelism; Parallel joins; Multi-joins; Data-skew; Join-product skew; Dynamic load balancing.
RR-2000-04 Chaotic iterations for constraint propagation and labeling
J. ARSOUZE, G. FERRAND, A. LALLOUET
Abstract : Here is an attempt to define a uniform semantic framework for constraint solving based on chaotic iterations and downward closure operators, taking into account both propagation and labeling. We extend the formalism of Montanari and Rossi cite{MontanariR:AI91} with more general rules of two kinds: while relaxation rules narrow the search space and preserve solutions, new restriction rules split the search space to explore it piece by piece. We show that independence of the computed approximation extends in some sense to labeling. Moreover, this framework can be used to model various approaches including the glass-box one used for finite domain constraint solving in Gnu-Prolog.
Keywords : constraint propagation; chaotic iterations; labeling; co-induction; semantics
RR-2000-05 An optimal and skew-insensitive join algorithm for Shared Nothing machines
M. BAMHA
Abstract : Joins constitute a computation-intensive part of database request and their parallelization is necessary for dealing with very large data sets. However, effectiveness of parallel joins depends on the ability to evenly divide load among processors. Research has shown that the join operation is parallelizable with near-linear speed-up on shared nothing machines only under ideal balancing conditions. Data skew can have a disastrous effect on performance. Although many skew-handling algorithms have been proposed they remain generally inefficient in the case of multi-joins due to join product skew, costly and unnecessary redistribution and communication costs. In this paper, we introduce a new parallel join algorithm with optimal complexity and deterministic perfect balancing. Its predictably low join-product and attribute-value skews makes it suitable for repeated use in multi-join operations. Its tradeoff between balancing overhead and speedup is analyzed using the scalable and portable BSP (Bulk Synchronous parallel) cost model which predicts a negligible join product skew and a near-linear speed-up. The algorithm presented here, improves our fa_join and sfa_join algorithms by reducing their communication and synchronisation cost to a minimum while offering the same load balancing properties.
Keywords : PDBMS (Parallel Database Management Systems); Intra-transaction parallelism; Parallel joins; Multi-joins; Data-skew; Join-product skew; Dynamic load balancing
RR-2000-06 Partitionable graphs arising from near-factorizations of finite groups
A. PECHER
Abstract : Since a counter-example to the Strong Perfect Graph Conjecture would be a partitionable graph, any 'new' construction for making partitionable graphs is of interest. In this paper, we investigate the near-factorizations of finite groups in general, and their associated Cayley graphs which are all partitionable. In particular we show that near-factorizations of the dihedral groups produce every CGPW graph of even order. We present some results about near-factorizations in finite groups which imply that a finite abelian group with a near-factorization (A,B) such that the cardinal of A is at most four, must be cyclic (already proved. One of these results may be used to speed up exhaustive calculations. At last, we prove that there is no counter-example to the Strong Perfect Graph Conjecture arising from near-factorizations of a finite abelian group of even order.
Keywords : partitionable; perfect; graph; near-factorization; group
RR-2000-07 Titre a venir
F. MOAL
Abstract :
Keywords :
RR-2000-08 Located concurrent constraint programming
N. ROMERO
Abstract : The Located Concurrent Constraint Programming model enhances the Saraswat's Concurrent Constraint Programming framework (cc) with distribution- and time-aware primitives. The unique global constraint store is split into several locations, which are local stores together with some associated processes. Each one can be dynamically created and moves on its own initiative to be interfaced with others. Multiform time awareness appears with the ability to detect local store modifications, to start and to suspend locations. A formal syntax and its operational semantics are defined. We then discuss several examples to show that these minimal changes lead to a powerful distributed concurrent constraint framework.
Keywords : Constraint Programming; Concurrent Programming; Distributed Programming; Operational Semantics.
RR-2000-09 Value withdrawal explanation in CLP
G. FERRAND, W. LESAINT, A. TESSIER
Abstract : This work is devoted to constraint solving motivated by the debugging of constraint logic programs a la GNU-Prolog. The paper focuses only on the constraints. In this framework, constraint solving amounts to domain reduction. A computation is formalized by a chaotic iteration. The computed result is described as a closure. This model is well suited to the design of debugging notions and tools, for example failure explanations or error diagnosis. In this paper we detail an application of the model to an explanation of a value withdrawal in a domain. Some other works have already shown the interest of such a notion of explanation not only for failure analysis.
Keywords : CSP; debugging; explanation; constraint programmation
RR-2000-10 Actes des journées de vérification formelle
Pierre RETY (editor)
Abstract :
Keywords :
RR-2000-11 Cayley partitionable graphs
A. PECHER
Abstract : In this paper we investigate the class of Cayley partitionable graphs. This investigation is motivated by the Strong Perfect Graph Conjecture. Cayley partitionable graphs are Cayley Graphs which are closely related to near-factorizations of finite groups. We prove that near-factorizations satisfy a strong structural property. We used it to speed up exhaustive computations, which revealed a Cayley partitionable graph with fifty vertices, which is not generated by all constructions of partitionable graphs known so far.
Keywords : partitionable; perfect; Cayley; graph; near-factorization; group
RR-2000-12 About facets of the stable set polytope of a graph
A. PECHER
Abstract : No complete characterization of rank facet producing graphs is known. In 1977, Balas and Zemel gave a necessary for a graph to be rank-facet producing, and in 1975, Chvátal gave a sufficient condition, which motivated the study of the class of critical graphs. We give two strengthening of Balas and Zemel's necessary condition, and one of Chvátal's sufficient condition.
Keywords : graph; stable set polytope; vertex packing polytope; facet; rank facet
RR-2000-13 A condition for a graph to contain k independent edges
A. P. WOJDA
Abstract : Let k, l, n be nonnegative integers such that 0< k < n/2, and let G be a graph of order n with the minimum vertex-degree at most l. We find the minimum function F such that if the size e(G) of G verifies e(G) > F(n,k,l) then G contains the matching of size k. Moreover, if e(G) = F(n,k,l) and G contains no matching of size k, then l
Keywords : graph; subgraph; forest.
RR-2000-14 On self-complementary supergraphs of (n,n) graphs
A. P. WOJDA, M. WOZNIAK, I. A. ZIOLO
Abstract : We prove that, with one exception, each (n,n)-graph G that is embeddable in its complement has a self-complementary supergraph of order n.
Keywords : graph; embedding; self-complementary graph.
RR-2000-15 Une version parallèle extensible de l'algorithme Particle Mesh Ewald
S. DROURI, G. HAINS
Abstract : We present the results of an applied mini-project conducted as part of the iHPerf'98 initiative of the ARP CNRS-GDR research network. The project was a collaboration with the CNRS-Orléans' CBM (biomolecular research center) and supported by ARP. It deals with the scalability analysis and parallel implementation of the Particle Mesh Ewald (PME) algorithm, which plays a fundamental role in molecular simulation: it evaluates electrostatic interactions. We propose a parallel version of PME for distributed-memory architectures. It optimises the ratio of computation, communication and synchronisation according the the BSP (bulk-synchronous parallelism) model. A new scalable parallel version of the Fast Fourier Transform (FFT) is also proposed since PME requires this algorithm. Our first tests on a Cray T3E architecture show an almost-linear acceleration.
Keywords : Molecular simulation; electrostatic interactions; Particle Mesh Ewald algorithm; parallel algorithms; scalability;
RR-2000-16 Synchronized Tree Languages Revisited and New Applications
V. GOURANTON, P. RETY, H. SEIDL
Abstract : We present a new formulation for tree-tuple synchronized languages, much simpler than the existing one. This new formulation allows us to prove stronger structural results. As a consequence, synchronized languages give rise to new applications : - to rewriting : given tree languages L1 (synchronized), L2 (regular), Rel(L1) subset of L2 is decidable for several rewrite-like relations Rel. - to concurrency : we prove decidability of the logic EF for a process calculus allowing some bounded form of communication. Consequently, the absence of deadlocks is decidable.
Keywords : tree-tuple language; rewriting; concurrency
RR-2000-17 Weakly Regular Relations and Applications
S. LIMET, P. RETY, H. SEIDL
Abstract : A new class of tree-tuple languages is introduced : the weakly regular relations. It is an extension of the regular case (regular relations) and a restriction of tree-tuple synchronized languages, that has all usual nice properties, except closure by complement. Two applications are presented : to unification modulo a rewrite system, and to one-step rewriting.
Keywords : Tree language; Rewriting; Unification
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 