- 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-2006-01 Abstract Branching for Quantified Formulas
Marco Benedetti
Abstract :
Keywords :
RR-2006-02 Minimal proper interval completions
Ivan Rapaport, Karol Suchan, Ioan Todinca
Abstract : We study the problem of adding edges to an arbitrary graph so that the resulting graph is a proper 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 or an interval graph. However, whereas there are algorithms for obtaining a chordal graph or an interval graph in this way, the same problem for obtaining a proper interval graph has been open until now. In this paper we give a linear time algorithm to obtain a minimal proper interval completion of an arbitrary graph, thereby resolving the complexity of this problem.
Keywords : graph, triangulation, proper interval, completion, exploration, complexity, algorithm, polynomial, linear.
RR-2006-03 Automata for Analyzing and Querying Compressed Documents
Siva Anantharaman, Barbara Fila
Abstract : In a first part of this work, tree/dag automata are defined as extensions of (unranked) tree automata which can run indifferently on trees or dags; they can thus serve as tools for analyzing or querying any semi-structured document, whether or not given in a compressed format. In a second part of the work, we present a method for evaluating positive queries expressed in terms of Core XPath axes, on any XML document t, compressed or not. To each Core XPath location step of a certain basic type, we associate an automaton; these automata run on the hedges of the minimal straightline regular tree grammar associated to the document, or on its dependency dag. Any given Core XPath query can be decomposed into queries of the basic type; and the answers to the query can then be expressed as a sub-document of t, suitably labeled under the runs of such automata.
Keywords : Tree automata, Tree grammars, Dags, XML, Core XPath.
RR-2006-04 Deciding Satisfiability of positive Second Order Joinability Formulae
Sébastien Limet, Pierre Pillot
Abstract : This paper deals with a class of second order formulae where the only predicate is the joinability modulo a conditional term rewrite system, first order variables range over ground terms and second order variables are interpreted as relations on ground terms (i.e. sets of tuples of ground terms). We define a generic algorithm that decides the satisfiability of positive second order joinability formulae when an algorithm is known to finitely represent solutions of first order formulae. When the answer is positive, the algorithm computes one particular instance for the second order variables. We apply this technique to the class of positive second order pseudo-regular formulae. The result is then a logic program that represents the instance of the second order variables. We define a transformation to translate this instance into a CTRS. This result can be used to automatically synthetize a program that defines a relation from its specification.
Keywords : logic program, term rewrite system, tree language, second order.
RR-2006-05 Solving First-Order Constraints in the Theory of the Evaluated Trees
Thi-Bich-Hanh Dao, Khalil Djelloul
Abstract : We present in this paper a general algorithm for solving first-order constraints in the theory T of the evaluated trees which is a combination of the theory of finite or infinite trees and the theory of the rational numbers with addition and subtraction and a linear dense order relation. The algorithm is given in the form of 28 rewriting rules. It transforms a first-order formula P - which can possibly contain free variables - into a disjunction Q of solved formulas which is equivalent in T, without new free variables and such that Q is either the formula True or the formula False or a formula having at least one free variable and being equivalent neither to True nor to False in T. In particular if P does not contain free variables then Q is either the formula True or False. If Q has free variables then the solutions on free variables are expressed in an explicit way and Q can be directly transformed into a boolean combination of quantified conjunctions of atomic formulas which do not accept elimination of quantifiers. The correctness of our algorithm is another proof of the completeness of this theory.
Keywords : first-order constraints; theory of trees; theory of rational numbers with addition, subtraction and linear dense order; constraint solving; rewrite rules.
RR-2006-07 Extension of First-Order Theories into Trees
Khalil Djelloul, Thi-Bich-Hanh Dao
Abstract : We present in this paper an automatic way to combine any first-order theory T with the theory of finite or infinite trees. First of all, we present a new class of theories that we call zero-infinite-decomposable and show that every decomposable theory T accepts a decision procedure in the form of six rewriting which for every first order proposition give either true or false in T. We present then the axiomatization T* of the extension of T into trees and show that if T is flexible then its extension into trees T* is zero-infinite-decomposable and thus complete. The flexible theories are theories having elegant properties which enable us to eliminate quantifiers in particular cases.
Keywords : first-order theories, theory of finite or infinite trees, complete theories.
RR-2006-08 Minimal interval completion through graph exploration
Karol Suchan, Ioan Todinca
Abstract : Given an arbitrary graph $G=(V,E)$ and an interval graph $H=(V,F)$ with $E \subseteq F$ we say that $H$ is an \emph{interval completion} of $G$. The graph $H$ is called a \emph{minimal interval completion} of $G$ if, for any sandwich graph $H'=(V,F')$ with $E \subseteq F' \subset F$, $H'$ is not an interval graph. In this paper we give a $\compl$ time algorithm computing a \mic\ of an arbitrary graph. The output is an interval model of the completion.
Keywords :
RR-2006-09 Characterizing minimal interval completions: Towards better understanding of profile and pathwidth
Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger
Abstract : Minimal interval completions of graphs are central in understanding two important and widely studied graph parameters: profile and pathwidth. Such understanding seems necessary to be able to attack the problem of computing these parameters. An interval completion of a given graph is an interval supergraph of it on the same vertex set, obtained by adding edges. If no subset of the added edges can be removed without destroying the interval property, we call it a minimal interval completion. In this paper, we give the first characterization of minimal interval completions. We present a polynomial time algorithm for deciding whether a given interval completion of an arbitrary graph is minimal, thereby resolving the complexity of this problem.
Keywords :
RR-2006-10 Pathwidth of circular-arc graphs
Karol Suchan, Ioan Todinca
Abstract : The pathwidth of a graph $G$ is the minimum clique number of $H$ minus one, over all interval supergraphs $H$ of $G$. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time. We give in this paper an $\cO(n2)$-time algorithm computing the pathwidth of circular-arc graphs.
Keywords :
RR-2006-11 Problem Modeling and Solving in QCSP made Practical
Marco Benedetti, Arnaud Lallouet, Jérémie Vautard
Abstract :
Keywords :
RR-2006-12 La visualisation distante
S. Limet, S. Madougou, E. Melin, S. Robert
Abstract : La visualisation de données est de plus en plus exploitée dans de nombreux domaines scientifiques et devient un élément essentiel dans la compréhension de phénomènes étudiés dans les différentes disciplines scientifiques. De plus, face aux enjeux de la complexité des simulations sous-jacentes et de la taille des données générées, le développement des applications scientifiques se base désormais sur des systèmes parallèles et distribués. Ainsi, il devient classique d'envisager un déploiement d'une application sur plusieurs sites dont un qui réalise l'affichage des résultats. Cet état de l'art s'intéresse à ce dernier point et a été réalisé dans le cadre d'un contrat de recherche avec le CEA/DIF de Bruyères-le-Châtel. Nous nous sommes ainsi intéressés à différentes solutions de visualisation distante afin d'obtenir une classification permettant de juger de leur qualité en fonction des attentes des utilisateurs. Nous avons choisi d'aborder cette classification en fonction du lieu du rendu qui influe sur les performances en terme de taux de rafraîchissement de l'image par rapport à la qualité du réseau. Ce point de vue permet de traiter les différentes méthodes possibles pour répartir le pipeline graphique entre les deux sites impliqués et d'en voir les avantages et les inconvénients. La visualisation distante s'appuie également sur une infrastructure réseau dont dépendent les performances finales. Ces différentes infrastructures possibles seront décrites dans une deuxième partie, ainsi que les concepts plus généraux formalisant les aspects réseau pour des déploiements de type Grid. Enfin, il existe déjà aujourd'hui des systèmes que nous qualifions d'autonomes dédiés directement ou indirectement à la visualisation distante. Ils constituent la dernière partie de ce document et nous permettront de conclure sur la pérennité des systèmes existants et les différentes possibilités pour les systèmes à venir.
Keywords :
RR-2006-13 Synchronized-ContextFree Tree-tuple Languages
Jacques Chabin, Jing Chen, Pierre Réty
Abstract : Using logic programs, we define a new class of tree-(tuple) languages, that combines the synchronized-regular tree-(tuple) languages with the context-free tree languages. Thus, this class can express an unbounded counting both in several independent branches (like in a synchronized-regular language), and at two nested positions (like in a context-free language). Despite its bigger expressivity, the new class has the same useful properties as the former ones\,: closure under union, closure under intersection of one tuple-component with a regular tree language, decidability of membership and emptiness. Therefore, it should give rise to many applications.
Keywords : tree languages, logic programming, rewriting
RR-2006-14 Visibly Pushdown Languages and Term Rewriting
Jacques Chabin, Pierre Réty
Abstract : To combine tree languages with term rewriting, we introduce a new class of tree languages, that both extends regular languages and restricts context-free languages, and that is closed under intersection (unlike context-free languages). To do it, we combine the concept of visibly pushdown language, with top-down pushdown tree automata, and we get the visibly pushdown tree automata. Then, we use them to express the sets of descendants for a sub-class of growing term rewrite systems, and thanks to closure under intersection, we get that joinability and (restricted) unifiability are decidable.
Keywords : tree languages, term rewriting.
LIFO Research Report for Year 2006
RR-2006-01
Abstract Branching for Quantified Formulas
Marco Benedetti
Date : 2006-06-16
Abstract Download
RR-2006-02
Minimal proper interval completions
Ivan Rapaport, Karol Suchan, Ioan Todinca
Date : 2006-03-09
Abstract Download
RR-2006-03
Automata for Analyzing and Querying Compressed Documents
Siva Anantharaman, Barbara Fila
Date : 2006-03-07
Abstract Download
RR-2006-04
Deciding Satisfiability of positive Second Order Joinability Formulae
Sébastien Limet, Pierre Pillot
Date : 2006-05-29
Abstract Download
RR-2006-05
Solving First-Order Constraints in the Theory of the Evaluated Trees
Thi-Bich-Hanh Dao, Khalil Djelloul
Date : 2006-05-09
Abstract Download
RR-2006-07
Extension of First-Order Theories into Trees
Khalil Djelloul, Thi-Bich-Hanh Dao
Date : 2006-06-20
Abstract Download
RR-2006-08
Minimal interval completion through graph exploration
Karol Suchan, Ioan Todinca
Date : 2006-07-11
Abstract Download
RR-2006-09
Characterizing minimal interval completions: Towards better understanding of profile and pathwidth
Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger
Date : 2006-07-11
Abstract Download
RR-2006-10
Pathwidth of circular-arc graphs
Karol Suchan, Ioan Todinca
Date : 2006-07-11
Abstract Download
RR-2006-11
Problem Modeling and Solving in QCSP made Practical
Marco Benedetti, Arnaud Lallouet, Jérémie Vautard
Date : 2006-07-18
Abstract Download
RR-2006-12
La visualisation distante
S. Limet, S. Madougou, E. Melin, S. Robert
Date : 2006-12-20
Abstract Download
RR-2006-13
Synchronized-ContextFree Tree-tuple Languages
Jacques Chabin, Jing Chen, Pierre Réty
Date : 2006-09-20
Abstract Download
RR-2006-14
Visibly Pushdown Languages and Term Rewriting
Jacques Chabin, Pierre Réty
Date : 2006-12-22
Abstract Download
Abstracts of Research Reports
RR-2006-01 Abstract Branching for Quantified Formulas
Marco Benedetti
Abstract :
Keywords :
RR-2006-02 Minimal proper interval completions
Ivan Rapaport, Karol Suchan, Ioan Todinca
Abstract : We study the problem of adding edges to an arbitrary graph so that the resulting graph is a proper 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 or an interval graph. However, whereas there are algorithms for obtaining a chordal graph or an interval graph in this way, the same problem for obtaining a proper interval graph has been open until now. In this paper we give a linear time algorithm to obtain a minimal proper interval completion of an arbitrary graph, thereby resolving the complexity of this problem.
Keywords : graph, triangulation, proper interval, completion, exploration, complexity, algorithm, polynomial, linear.
RR-2006-03 Automata for Analyzing and Querying Compressed Documents
Siva Anantharaman, Barbara Fila
Abstract : In a first part of this work, tree/dag automata are defined as extensions of (unranked) tree automata which can run indifferently on trees or dags; they can thus serve as tools for analyzing or querying any semi-structured document, whether or not given in a compressed format. In a second part of the work, we present a method for evaluating positive queries expressed in terms of Core XPath axes, on any XML document t, compressed or not. To each Core XPath location step of a certain basic type, we associate an automaton; these automata run on the hedges of the minimal straightline regular tree grammar associated to the document, or on its dependency dag. Any given Core XPath query can be decomposed into queries of the basic type; and the answers to the query can then be expressed as a sub-document of t, suitably labeled under the runs of such automata.
Keywords : Tree automata, Tree grammars, Dags, XML, Core XPath.
RR-2006-04 Deciding Satisfiability of positive Second Order Joinability Formulae
Sébastien Limet, Pierre Pillot
Abstract : This paper deals with a class of second order formulae where the only predicate is the joinability modulo a conditional term rewrite system, first order variables range over ground terms and second order variables are interpreted as relations on ground terms (i.e. sets of tuples of ground terms). We define a generic algorithm that decides the satisfiability of positive second order joinability formulae when an algorithm is known to finitely represent solutions of first order formulae. When the answer is positive, the algorithm computes one particular instance for the second order variables. We apply this technique to the class of positive second order pseudo-regular formulae. The result is then a logic program that represents the instance of the second order variables. We define a transformation to translate this instance into a CTRS. This result can be used to automatically synthetize a program that defines a relation from its specification.
Keywords : logic program, term rewrite system, tree language, second order.
RR-2006-05 Solving First-Order Constraints in the Theory of the Evaluated Trees
Thi-Bich-Hanh Dao, Khalil Djelloul
Abstract : We present in this paper a general algorithm for solving first-order constraints in the theory T of the evaluated trees which is a combination of the theory of finite or infinite trees and the theory of the rational numbers with addition and subtraction and a linear dense order relation. The algorithm is given in the form of 28 rewriting rules. It transforms a first-order formula P - which can possibly contain free variables - into a disjunction Q of solved formulas which is equivalent in T, without new free variables and such that Q is either the formula True or the formula False or a formula having at least one free variable and being equivalent neither to True nor to False in T. In particular if P does not contain free variables then Q is either the formula True or False. If Q has free variables then the solutions on free variables are expressed in an explicit way and Q can be directly transformed into a boolean combination of quantified conjunctions of atomic formulas which do not accept elimination of quantifiers. The correctness of our algorithm is another proof of the completeness of this theory.
Keywords : first-order constraints; theory of trees; theory of rational numbers with addition, subtraction and linear dense order; constraint solving; rewrite rules.
RR-2006-07 Extension of First-Order Theories into Trees
Khalil Djelloul, Thi-Bich-Hanh Dao
Abstract : We present in this paper an automatic way to combine any first-order theory T with the theory of finite or infinite trees. First of all, we present a new class of theories that we call zero-infinite-decomposable and show that every decomposable theory T accepts a decision procedure in the form of six rewriting which for every first order proposition give either true or false in T. We present then the axiomatization T* of the extension of T into trees and show that if T is flexible then its extension into trees T* is zero-infinite-decomposable and thus complete. The flexible theories are theories having elegant properties which enable us to eliminate quantifiers in particular cases.
Keywords : first-order theories, theory of finite or infinite trees, complete theories.
RR-2006-08 Minimal interval completion through graph exploration
Karol Suchan, Ioan Todinca
Abstract : Given an arbitrary graph $G=(V,E)$ and an interval graph $H=(V,F)$ with $E \subseteq F$ we say that $H$ is an \emph{interval completion} of $G$. The graph $H$ is called a \emph{minimal interval completion} of $G$ if, for any sandwich graph $H'=(V,F')$ with $E \subseteq F' \subset F$, $H'$ is not an interval graph. In this paper we give a $\compl$ time algorithm computing a \mic\ of an arbitrary graph. The output is an interval model of the completion.
Keywords :
RR-2006-09 Characterizing minimal interval completions: Towards better understanding of profile and pathwidth
Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger
Abstract : Minimal interval completions of graphs are central in understanding two important and widely studied graph parameters: profile and pathwidth. Such understanding seems necessary to be able to attack the problem of computing these parameters. An interval completion of a given graph is an interval supergraph of it on the same vertex set, obtained by adding edges. If no subset of the added edges can be removed without destroying the interval property, we call it a minimal interval completion. In this paper, we give the first characterization of minimal interval completions. We present a polynomial time algorithm for deciding whether a given interval completion of an arbitrary graph is minimal, thereby resolving the complexity of this problem.
Keywords :
RR-2006-10 Pathwidth of circular-arc graphs
Karol Suchan, Ioan Todinca
Abstract : The pathwidth of a graph $G$ is the minimum clique number of $H$ minus one, over all interval supergraphs $H$ of $G$. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time. We give in this paper an $\cO(n2)$-time algorithm computing the pathwidth of circular-arc graphs.
Keywords :
RR-2006-11 Problem Modeling and Solving in QCSP made Practical
Marco Benedetti, Arnaud Lallouet, Jérémie Vautard
Abstract :
Keywords :
RR-2006-12 La visualisation distante
S. Limet, S. Madougou, E. Melin, S. Robert
Abstract : La visualisation de données est de plus en plus exploitée dans de nombreux domaines scientifiques et devient un élément essentiel dans la compréhension de phénomènes étudiés dans les différentes disciplines scientifiques. De plus, face aux enjeux de la complexité des simulations sous-jacentes et de la taille des données générées, le développement des applications scientifiques se base désormais sur des systèmes parallèles et distribués. Ainsi, il devient classique d'envisager un déploiement d'une application sur plusieurs sites dont un qui réalise l'affichage des résultats. Cet état de l'art s'intéresse à ce dernier point et a été réalisé dans le cadre d'un contrat de recherche avec le CEA/DIF de Bruyères-le-Châtel. Nous nous sommes ainsi intéressés à différentes solutions de visualisation distante afin d'obtenir une classification permettant de juger de leur qualité en fonction des attentes des utilisateurs. Nous avons choisi d'aborder cette classification en fonction du lieu du rendu qui influe sur les performances en terme de taux de rafraîchissement de l'image par rapport à la qualité du réseau. Ce point de vue permet de traiter les différentes méthodes possibles pour répartir le pipeline graphique entre les deux sites impliqués et d'en voir les avantages et les inconvénients. La visualisation distante s'appuie également sur une infrastructure réseau dont dépendent les performances finales. Ces différentes infrastructures possibles seront décrites dans une deuxième partie, ainsi que les concepts plus généraux formalisant les aspects réseau pour des déploiements de type Grid. Enfin, il existe déjà aujourd'hui des systèmes que nous qualifions d'autonomes dédiés directement ou indirectement à la visualisation distante. Ils constituent la dernière partie de ce document et nous permettront de conclure sur la pérennité des systèmes existants et les différentes possibilités pour les systèmes à venir.
Keywords :
RR-2006-13 Synchronized-ContextFree Tree-tuple Languages
Jacques Chabin, Jing Chen, Pierre Réty
Abstract : Using logic programs, we define a new class of tree-(tuple) languages, that combines the synchronized-regular tree-(tuple) languages with the context-free tree languages. Thus, this class can express an unbounded counting both in several independent branches (like in a synchronized-regular language), and at two nested positions (like in a context-free language). Despite its bigger expressivity, the new class has the same useful properties as the former ones\,: closure under union, closure under intersection of one tuple-component with a regular tree language, decidability of membership and emptiness. Therefore, it should give rise to many applications.
Keywords : tree languages, logic programming, rewriting
RR-2006-14 Visibly Pushdown Languages and Term Rewriting
Jacques Chabin, Pierre Réty
Abstract : To combine tree languages with term rewriting, we introduce a new class of tree languages, that both extends regular languages and restricts context-free languages, and that is closed under intersection (unlike context-free languages). To do it, we combine the concept of visibly pushdown language, with top-down pushdown tree automata, and we get the visibly pushdown tree automata. Then, we use them to express the sets of descendants for a sub-class of growing term rewrite systems, and thanks to closure under intersection, we get that joinability and (restricted) unifiability are decidable.
Keywords : tree languages, term rewriting.
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 