- 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-2001-01 Cartographie de textes, une nouvelle approche pour l'exploration sémantique des corpus homogènes de grande dimension
I. DEBOURGES, S. GUILLORE-BILLOT, C. VRAIN
Abstract : We present an ongoing research project on the new field of Text Mapping that all ows a novice user to explore a new domain by navigation through an homogeneous corpus thanks to interactive conceptual maps. A map is composed of concepts (the nodes) depending on the user's request and its evolution, and semantic/lexical relations (the links). Machine Learning techniques are combined with Natural Language Processing methodologies to build the maps. The algorithms are implemented in a prototype. Experiments on different english and french corpora show encouraging results.
Keywords : Text Mapping | Information Retrieval | Information Extraction | Machine Learning
RR-2001-02 Net Juggler Guide
J. ALLARD, L. LECOINTRE, V. GOURANTON, E. MELIN, B. RAFFIN
Abstract : The Net Juggler library allows to run on a cluster the virtual reality environment VR Juggler. Net Juggler Guide details Net Juggler installation, use and programming.
Keywords :
RR-2001-03 Chordal embeddings of planar graphs
V. BOUCHITTE, F. MAZOIT, I. TODINCA
Abstract : Robertson and Seymour conjectured that the treewidth of a planar graph and the treewidth of its geometric dual differ by at most one. Lapoire solved the conjecture in the affirmative, using algebraic techniques. We give here a much shorter proof of this result.
Keywords : planar graphs; duality; chordal graphs; treewidth
RR-2001-04 On treewidth approximations
V. BOUCHITTE, D. KRATSCH, H. MULLER, I TODINCA
Abstract : We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(log OPT) approximation algorithm for the treewidth of arbitrary graphs.
Keywords : treewidth; asteroidal number; graph algorithms; approximation algorithms
RR-2001-05 Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction
G. FERRAND, W. LESAINT, A. TESSIER
Abstract : Constraint programming is an important programming paradigm of the last years. It combines declarativity and efficiency thanks to constraint solvers which are implemented for specific domains. We are interested here in the case of reduction of finite domains. In the paper, it is formalized with chaotic iterations of monotonic operators. A first notion of explanation, which have been proved very useful in many applications, is then defined in a declarative way in terms of closure. An explanation set for a value removal is a set of operators which always remove this value whatever the order of application of these operators is. A monotonic operator can always be defined by a set of rules (in the sense of inductive definition of Aczel). Furthermore, the paper shows that for classical notions of local consistency, such a system of rules can be expressed in a natural way. They express value removals as consequences of other value removals. So, a more precise notion of explanation can be obtained: the linking of these rules allows to inductively define proof trees. Such a proof tree clearly explains the removal of a value (the root of the tree) by the solver, it is then called an explanation for this value withdrawal. Explanations are the essence of domain reduction.
Keywords : CSP; constraint programming; domain reduction explanation
RR-2001-06 Learning Constraints between Variables in Inductive Logic Programming
A. BRAUD, C. VRAIN
Abstract : In Inductive Logic Programming, a critical point is the complexity of the algorithms inherent in first order representations. An interesting solution to this, called propositionalization, consists in reformulating a relational problem into an attribute-value one. A pattern describing the general form of the rules is given or learned, and the system has to specialize it by learning either symbolic constraints, as for instance equality relations between variables, or numeric ones. We propose to use a genetic approach to specialize such patterns. In this paper, we are interested in learning suitable equality constraints between variables. The main originality of our approach relies on the coding of these constraints and the corresponding genetic operators. Instead of coding in an individual whether pairs of variables are equal or not, we represent the equivalence classes involved by the equality relations, and apply set-based operators on them to produce new individuals.
Keywords : Inductive Logic Programming; Propositionalization; Genetic Algorithms
RR-2001-07 Equational Unification, Rewrite Reachability, and Labelled Dag Automata
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Abstract : $E$-unification problems are central in automated deduction. Their study is often closely related to problems from other fields (e.g., linear diophantine equations, tree automata). In this paper, we consider theories $E$ that are extensions of the well-known $AC$ or $ACU$, such as $ACID$ and $ACUIH^C$, and relate their study to language problems over automata on term-dags with or without labels, and reachability problems on Minsky machine configurations. By attaching suitable rewrite semantics to executions of instructions on such machines, we first show that unification modulo the theory $ACUIH^C$ -- i.e. $ACU$ plus idempotence and a set of commuting homomorphisms -- is undecidable in general. Next, by looking at these machines from a slightly different angle and by attaching rewrite semantics to incorrect machine behavior this time, we derive a proof that the universality of $t$-dag automata is undecidable; a corollary is that $t$-dag automata are not stable under complementation. We then consider the class of of labelled $t$-dag automata, extending that of $t$-dag automata -- which are not stable under complementation either, and for which universality remains undecidable. We finally show that the $ACID$-unification problem, i.e. unification modulo $AC$ plus idempotence and distributivity, can be solved in NEXPTIME, in terms of such labelled automata.
Keywords :
LIFO Research Report for Year 2001
RR-2001-01
Cartographie de textes, une nouvelle approche pour l'exploration sémantique des corpus homogènes de grande dimension
I. DEBOURGES, S. GUILLORE-BILLOT, C. VRAIN
Date : 2001-03-07
Abstract Download
RR-2001-02
Net Juggler Guide
J. ALLARD, L. LECOINTRE, V. GOURANTON, E. MELIN, B. RAFFIN
Date : 2001-06-15
Abstract Download
RR-2001-03
Chordal embeddings of planar graphs
V. BOUCHITTE, F. MAZOIT, I. TODINCA
Date : 2001-10-04
Abstract Download
RR-2001-04
On treewidth approximations
V. BOUCHITTE, D. KRATSCH, H. MULLER, I TODINCA
Date : 2001-10-17
Abstract Download
RR-2001-05
Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction
G. FERRAND, W. LESAINT, A. TESSIER
Date : 2001-11-22
Abstract Download
RR-2001-06
Learning Constraints between Variables in Inductive Logic Programming
A. BRAUD, C. VRAIN
Date : 2001-12-21
Abstract Download
RR-2001-07
Equational Unification, Rewrite Reachability, and Labelled Dag Automata
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Date : 2001-12-27
Abstract Download
Abstracts of Research Reports
RR-2001-01 Cartographie de textes, une nouvelle approche pour l'exploration sémantique des corpus homogènes de grande dimension
I. DEBOURGES, S. GUILLORE-BILLOT, C. VRAIN
Abstract : We present an ongoing research project on the new field of Text Mapping that all ows a novice user to explore a new domain by navigation through an homogeneous corpus thanks to interactive conceptual maps. A map is composed of concepts (the nodes) depending on the user's request and its evolution, and semantic/lexical relations (the links). Machine Learning techniques are combined with Natural Language Processing methodologies to build the maps. The algorithms are implemented in a prototype. Experiments on different english and french corpora show encouraging results.
Keywords : Text Mapping | Information Retrieval | Information Extraction | Machine Learning
RR-2001-02 Net Juggler Guide
J. ALLARD, L. LECOINTRE, V. GOURANTON, E. MELIN, B. RAFFIN
Abstract : The Net Juggler library allows to run on a cluster the virtual reality environment VR Juggler. Net Juggler Guide details Net Juggler installation, use and programming.
Keywords :
RR-2001-03 Chordal embeddings of planar graphs
V. BOUCHITTE, F. MAZOIT, I. TODINCA
Abstract : Robertson and Seymour conjectured that the treewidth of a planar graph and the treewidth of its geometric dual differ by at most one. Lapoire solved the conjecture in the affirmative, using algebraic techniques. We give here a much shorter proof of this result.
Keywords : planar graphs; duality; chordal graphs; treewidth
RR-2001-04 On treewidth approximations
V. BOUCHITTE, D. KRATSCH, H. MULLER, I TODINCA
Abstract : We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(log OPT) approximation algorithm for the treewidth of arbitrary graphs.
Keywords : treewidth; asteroidal number; graph algorithms; approximation algorithms
RR-2001-05 Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction
G. FERRAND, W. LESAINT, A. TESSIER
Abstract : Constraint programming is an important programming paradigm of the last years. It combines declarativity and efficiency thanks to constraint solvers which are implemented for specific domains. We are interested here in the case of reduction of finite domains. In the paper, it is formalized with chaotic iterations of monotonic operators. A first notion of explanation, which have been proved very useful in many applications, is then defined in a declarative way in terms of closure. An explanation set for a value removal is a set of operators which always remove this value whatever the order of application of these operators is. A monotonic operator can always be defined by a set of rules (in the sense of inductive definition of Aczel). Furthermore, the paper shows that for classical notions of local consistency, such a system of rules can be expressed in a natural way. They express value removals as consequences of other value removals. So, a more precise notion of explanation can be obtained: the linking of these rules allows to inductively define proof trees. Such a proof tree clearly explains the removal of a value (the root of the tree) by the solver, it is then called an explanation for this value withdrawal. Explanations are the essence of domain reduction.
Keywords : CSP; constraint programming; domain reduction explanation
RR-2001-06 Learning Constraints between Variables in Inductive Logic Programming
A. BRAUD, C. VRAIN
Abstract : In Inductive Logic Programming, a critical point is the complexity of the algorithms inherent in first order representations. An interesting solution to this, called propositionalization, consists in reformulating a relational problem into an attribute-value one. A pattern describing the general form of the rules is given or learned, and the system has to specialize it by learning either symbolic constraints, as for instance equality relations between variables, or numeric ones. We propose to use a genetic approach to specialize such patterns. In this paper, we are interested in learning suitable equality constraints between variables. The main originality of our approach relies on the coding of these constraints and the corresponding genetic operators. Instead of coding in an individual whether pairs of variables are equal or not, we represent the equivalence classes involved by the equality relations, and apply set-based operators on them to produce new individuals.
Keywords : Inductive Logic Programming; Propositionalization; Genetic Algorithms
RR-2001-07 Equational Unification, Rewrite Reachability, and Labelled Dag Automata
S. ANANTHARAMAN, P. NARENDRAN, M. RUSINOWITCH
Abstract : $E$-unification problems are central in automated deduction. Their study is often closely related to problems from other fields (e.g., linear diophantine equations, tree automata). In this paper, we consider theories $E$ that are extensions of the well-known $AC$ or $ACU$, such as $ACID$ and $ACUIH^C$, and relate their study to language problems over automata on term-dags with or without labels, and reachability problems on Minsky machine configurations. By attaching suitable rewrite semantics to executions of instructions on such machines, we first show that unification modulo the theory $ACUIH^C$ -- i.e. $ACU$ plus idempotence and a set of commuting homomorphisms -- is undecidable in general. Next, by looking at these machines from a slightly different angle and by attaching rewrite semantics to incorrect machine behavior this time, we derive a proof that the universality of $t$-dag automata is undecidable; a corollary is that $t$-dag automata are not stable under complementation. We then consider the class of of labelled $t$-dag automata, extending that of $t$-dag automata -- which are not stable under complementation either, and for which universality remains undecidable. We finally show that the $ACID$-unification problem, i.e. unification modulo $AC$ plus idempotence and distributivity, can be solved in NEXPTIME, in terms of such labelled automata.
Keywords :
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 