- 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-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 :
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 :
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 