- Contacts/Reaching LIFO
- Teaching

**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

# LIFO Research Report for Year 2001

## 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 : **

**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

University of Orléans | INSA Centre Val de Loire