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
LIFO Research Report for Year 2005
RR-2005-01
Visualisation de larges terrains multi-modaux dans les environnements multi-écrans pilotés par grappe de PC
Valérie Gouranton, Sébastien Limet, Souley Madougou, Emmanuel Melin, Cyril Nortet
Date : 2005-04-29
Abstract Download
RR-2005-02
Solving First Order Formulae of Pseudo-Regular Theory
Sébastien Limet and Pierre Pillot
Date : 2005-03-09
Abstract Download
RR-2005-03
A Fully Dynamic Recognition Algorithm for weak bisplit graphs
Jean-Marie Vanherpe and Soumia Ziti
Date : 2005-03-14
Abstract Download
RR-2005-04
Minimal interval completions
Pinar Heggerness, Karol Suchan, Ioan Todinca, and Yngve Villanger
Date : 2005-04-13
Abstract Download
RR-2005-05
Abstract geometrical computation 1 : embedding Black hole computations with rational numbers
Jérome Durand-Lose
Date : 2005-12-07
Abstract Download
RR-2005-07
Représentation des langages de n-uplets d'arbres par des programmes logiques et applications
Sébastien Limet
Date : 2005-12-07
Abstract Download
Abstracts of Research Reports
RR-2005-01 Visualisation de larges terrains multi-modaux dans les environnements multi-écrans pilotés par grappe de PC
Valérie Gouranton, Sébastien Limet, Souley Madougou, Emmanuel Melin, Cyril Nortet
Abstract : Large terrains rendering at interactive rates is of increasing interest
in many areas. In Geographic Information Systems (GIS), for example, the
elevation data are often associated to various other information such as
rivers, drill-holes, roads, mineral densities and so on. The issue is
then to find the right levels of detail algorithm that both scales well
with raw data and preserves the other important features. As a
contribution to this research, we present a generic mipmap method that
intrinsically implies implementing a morphing support and which is
applicable to any kind of per-vertex data. The method is integrated in a
parallel framework for geometry-driven levels of detail rendering of
large height fields. Relying on recent advances in PC cluster computing,
we distribute in a consistent manner both geometry and extra data among
cluster nodes. The previous levels of detail algorithm is combined with
our mipmap method to process them in parallel. To optimize the use of
the interconnecting network bandwidth a compact data structure is
defined for data transfer. As a consequence, the framework sustains
smooth interactive appearance-preserving rendering of gigabyte-sized
terrain models.
Keywords : LOD rendering, parallel rendering, parallelism, Massive, data rendering
RR-2005-02 Solving First Order Formulae of Pseudo-Regular Theory
Sébastien Limet and Pierre Pillot
Abstract : In this paper, we study the class of pseudo-regular relations which
is an extension of regular relations that weakens some restrictions
on the "synchronization" between tuple components of the
relation. We choose logic programming as formalism to describe tree
tuple languages (i.e. relations) and logic program transformation
techniques for computing operations on them. We show that even if
pseudo-regular cs-programs are syntactically less restrictive than
regular ones, they define the same class of tree tuple
languages. However, pseudo-regular relations allows ones to define
classes of term rewrite systems the transitive closure of which is a
regular relation. We apply this result to give a decidable class
of first order formulae based on the joinability predicate
of a pseudo-regular term rewrite system.
Keywords : tree languages; term rewriting; logic programming; decidability
RR-2005-03 A Fully Dynamic Recognition Algorithm for weak bisplit graphs
Jean-Marie Vanherpe and Soumia Ziti
Abstract : We provide efficient fully dynamic recognition algorithms involving vertex or edge insertions or deletions for the class of weak bisplit graphs, a class of bipartite graphs closely related to cographs and split graphs.
Keywords : Module; Decomposition; Canonical Decomposition; Tree; Cograph; Bipartite Graph; K+S Graph; Weak Bisplit Graph; Dynamic Algorithm.
RR-2005-04 Minimal interval completions
Pinar Heggerness, Karol Suchan, Ioan Todinca, and Yngve Villanger
Abstract : We study the problem of adding edges to an arbitrary graph so that the
resulting graph is an interval graph. Our objective is to add an
inclusion minimal set of edges, which means
that no proper subset of the added edges can
result in an interval graph when added to the original graph. This
problem is closely related to the problem of adding an inclusion minimal
set of edges to a graph to obtain a chordal graph, which is a well studied
problem and which motivates an analogous study of minimal interval completions.
However, whereas there
are nice properties that result in efficient algorithms for obtaining a
chordal graph in this way, the same problem for obtaining an interval
graph is more difficult, and its computational complexity has been open
until now. In this paper we give a polynomial time algorithm to obtain a
minimal interval completion of an arbitrary graph, thereby resolving the
complexity of this problem.
Keywords : graph, triangulation, interval, completion, online, algorithm, polynomial, decomposition, order, partition, refinement
RR-2005-05 Abstract geometrical computation 1 : embedding Black hole computations with rational numbers
Jérome Durand-Lose
Abstract : The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable (r.e.) problem.
In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers (and not real numbers), has the same property: it can simulate any Turing machine and can decide any r.e. problem through the creation of an accumulation.
Finitely many signals can leave any accumulation, and it can be known whether anything leaves.
This corresponds to a black hole effect.
Keywords : Abstract geometrical computation;
Black hole model;
Energy conservation;
Malament-Hogarth space-time;
Super-Turing computation;
Turing universality;
Zeno phenomena.
RR-2005-07 Représentation des langages de n-uplets d'arbres par des programmes logiques et applications
Sébastien Limet
Abstract : Dans le domaine de l'informatique théorique, on manipule très souvent des relations sur les termes du 1er ordre. Par conséquent, il est important d'avoir des représentations finies de ces relations, encore appelées langages de n-uplets d'arbres. Nous avons étudié différentes représentations possibles pour une classe de langages appelée langages synchronisés. Nous avons plus particulièrement étudié une représentation sous forme de programmes logiques et présenté un algorithme basé sur les techniques de transformation de programmes pour calculer les opérations sur les langages. Dans ce cadre, nous avons montré des propriétés intéressantes des langages synchronisés et de certaines de leurs sous-classes. Puis, nous avons appliqué les résultats obtenus à des problèmes liés aux domaines de la démonstration automatique et de la vérification. Ces résultats s'appuient sur une procédure de construction d'un programme logique qui décrit la clôture réflexive transitive de la relation induite par un système de réécriture.
Keywords :