- 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-1998-01 Designing FPLA combinatorial circuits by conditional rewriting
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Abstract : We present a rewrite based method to design FPLA combinational circuits. It is based on the maximal unit strategy method with built-in algebras. Basic operations on natural integers and boolean algebra are done by the use of efficient usual methods. The formalism of constraint is used,;,efficient, correct heuristic and goal-oriented deletion criteria and strategies are used without losing correctness and completeness. A beta version named CDR (for Circuit Design by Rewriting), of our method is under experiment. A brief description of CDR and some results are presented at the end of the paper.
Keywords : Conditional rewriting; constraints; built-in algebras; combinational circuit design; strategies; expert system
RR-1998-02
G. FERRAND, A. TESSIER
Abstract : This report proposes a reformulation of the contraint logic program semantics in terms of positive and negative semantics, using an uniform inductive framework. It is a natural and elegant way to express and study correctness and completeness results. In particular, we state a completeness for negative semantics by using some infinite sets of contraints. This theoretical framework is an original extension of the grammatical view of logic programming.
Keywords : semantics, constraint logic programming, correctness, completeness, induction, co-induction.
RR-1998-03 Translating view updates using inversion of relational algebra
F. BENTAYEB, D. LAURENT
Abstract : Views over databases have been studied in various directions for many years. Among these directions, translating view updates in terms of updates on the base relations bs81,il83 , and materialized views and their maintenance blt86, cw91 have motivated many research efforts. Nowadays, materialized views are finding increased research activity with applications in decision support which is relevant for data warehousing. In this paper, we study the translation process in the relational model. We propose a method for characterizing translations of view updates, based on the notion of inverse of a relational expression. Moreover, we characterize two kinds of updates: (1) deterministic updates regardless to the database state, and (2) deterministic updates according to some database state, and finally, we give an overview of performing view updates using the criterion of updates determinism.
Keywords : relational views; view update translations; inverses; inverse-images; strongly deterministic view updates; weakly deterministic view updates
RR-1998-04 A conditional rewrite-based method for designing combinational logic circuits
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Abstract : We present a conditional rewrite-based method to design not trivial combinational logic circuits using only Small Scale Integrated (SSI) elements. For this, we develop a maximal unit strategy method, using built-in algebras. In the present work, we assume that natural integers and boolean algebra are built-in. The formalism of constraint is used and the search space is reduced by suppressing rules according to a new goal-oriented deletion rule criteria.
Keywords : electronic components; logical gates; SSI; conditional rewriting; constraints; built-in algebras; combinational circuit design; strategies; expert system;
RR-1998-06 Graphs with chordless cycles of bounded length
I. RUSU
Abstract : The perfection of weakly triangulated graphs, i.e. antihole-free graphs whose induced cycles are isomorphic either to C_{3} or to C_{4}, was proved by Hayward and generated intense studies to efficiently solve the classical NP-complete problems which become polynomial on perfect graphs. If we replace, in the definition above, the C_{4} by an arbitrary C_{p} (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this paper. In fact, we prove a more general result: for any even integer p>=6, the graphs whose induced cycles are isomorphic either to C_{3} or to one of C_{p}, C_{p+2},..., C_{2p-6} are perfect.
Keywords : perfectness; weakly triangulated graphs; dominating pair
RR-1998-07 A System for the High-Level Parallelization and Cooperation of Constraint Solvers
L. GRANVILLIERS, G. HAINS, Q. MILLER, N. ROMERO
Abstract : A general system, Bs-Solve, is presented for the high-level programming and reuse of cooperative and parallel constraint solvers. The parallelization of two common algorithms is outlined : Groebner-basis computation for polynomial systems and Waltz consistency algorithm for continuous domains.
Keywords : Constraint solvers; cooperation; parallel strategies
RR-1998-08 Demand-driven search in functional logic programs
M. HANUS, P. RETY
Abstract : In this paper we discuss the advantage of lazy functional logic languages to solve search problems. We show that the lazy evaluation strategy of such languages can be easily exploited to implement a solver that explores only the dynamically demanded parts of the search space. In contrast to pure logic programming, the use of non-deterministic functions enables a modular and simple implementation without the risk of floundering. Furthermore, a local encapsulation of search is useful to avoid the combinatorial explosion of the demanded search space. The necessary features (laziness, non-deterministic functions, encapsulated search) are available in Curry, a new declarative language intended to combine functional and logic programming techniques. We demonstrate the advantage of this approach by a musical application implemented in Curry: the generation of appropriate chords for the accompaniment of a given melody.
Keywords : Functional logic programming; lazy evaluation; search; practical application
RR-1998-09 An introduction to BS-lambda
F. LOULERGUE, G. HAINS
Abstract : This paper is an introduction to BS-lambda a calculus of parallel-recursive BSP programs. The calculus is presented, its confluence is stated and examples are given in an ML-like syntax.
Keywords : BSP; extension of the lambda-calculus; parallel-recursive programs; confluence
RR-1998-10 Recognizing i-triangulated graphs in O(mn)
F. ROUSSEL, I. RUSU
Abstract : We use lexicographic breadth-first search and contractions of subgraphs to give a new (and better, from a complexity point of view) algorithm to recognize i-triangulated graphs.
Keywords : recognition algorithm; lexicographic breadth-first search; triangulated graph; i-triangulated graph
RR-1998-11 A linear algorithm to color i-triangulated graphs
F. ROUSSEL, I. RUSU
Abstract : We show that i-triangulated graphs can be colored in linear time by applying lexicographic breadth-first search and the greedy coloring algorithm.
Keywords : greedy algorithm; triangulated graph; i-triangulated graph; Lex-BFS
RR-1998-12 A New Result about the Decidability of the Existential One-step Rewriting Theory
S. LIMET, P. RETY
Abstract : We give a decision procedure for the whole existential fragment of one-step rewriting first-order theory, in the case where rewrite systems are linear, non left-left-overlapping (i.e. without critical pairs), and non epsilon-left-right-overlapping (i.e. no left-hand-side overlaps on top with the right-hand-side of the same rewrite rule). The procedure is defined by means of tree-tuple synchronized grammars.
Keywords : one-step rewriting; tree languages
LIFO Research Report for Year 1998
RR-1998-01
Designing FPLA combinatorial circuits by conditional rewriting
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Date : 1998-09-22
Abstract Download
RR-1998-02
G. FERRAND, A. TESSIER
Date : 1998-00-00
Abstract Download
RR-1998-03
Translating view updates using inversion of relational algebra
F. BENTAYEB, D. LAURENT
Date : 1998-00-00
Abstract Download
RR-1998-04
A conditional rewrite-based method for designing combinational logic circuits
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Date : 1998-11-12
Abstract Download
RR-1998-06
Graphs with chordless cycles of bounded length
I. RUSU
Date : 1998-00-00
Abstract Download
RR-1998-07
A System for the High-Level Parallelization and Cooperation of Constraint Solvers
L. GRANVILLIERS, G. HAINS, Q. MILLER, N. ROMERO
Date : 1998-09-21
Abstract Download
RR-1998-08
Demand-driven search in functional logic programs
M. HANUS, P. RETY
Date : 1998-09-10
Abstract Download
RR-1998-09
An introduction to BS-lambda
F. LOULERGUE, G. HAINS
Date : 1998-09-15
Abstract Download
RR-1998-10
Recognizing i-triangulated graphs in O(mn)
F. ROUSSEL, I. RUSU
Date : 1998-09-21
Abstract Download
RR-1998-11
A linear algorithm to color i-triangulated graphs
F. ROUSSEL, I. RUSU
Date : 1998-11-30
Abstract Download
RR-1998-12
A New Result about the Decidability of the Existential One-step Rewriting Theory
S. LIMET, P. RETY
Date : 1998-12-18
Abstract Download
Abstracts of Research Reports
RR-1998-01 Designing FPLA combinatorial circuits by conditional rewriting
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Abstract : We present a rewrite based method to design FPLA combinational circuits. It is based on the maximal unit strategy method with built-in algebras. Basic operations on natural integers and boolean algebra are done by the use of efficient usual methods. The formalism of constraint is used,;,efficient, correct heuristic and goal-oriented deletion criteria and strategies are used without losing correctness and completeness. A beta version named CDR (for Circuit Design by Rewriting), of our method is under experiment. A brief description of CDR and some results are presented at the end of the paper.
Keywords : Conditional rewriting; constraints; built-in algebras; combinational circuit design; strategies; expert system
RR-1998-02
G. FERRAND, A. TESSIER
Abstract : This report proposes a reformulation of the contraint logic program semantics in terms of positive and negative semantics, using an uniform inductive framework. It is a natural and elegant way to express and study correctness and completeness results. In particular, we state a completeness for negative semantics by using some infinite sets of contraints. This theoretical framework is an original extension of the grammatical view of logic programming.
Keywords : semantics, constraint logic programming, correctness, completeness, induction, co-induction.
RR-1998-03 Translating view updates using inversion of relational algebra
F. BENTAYEB, D. LAURENT
Abstract : Views over databases have been studied in various directions for many years. Among these directions, translating view updates in terms of updates on the base relations bs81,il83 , and materialized views and their maintenance blt86, cw91 have motivated many research efforts. Nowadays, materialized views are finding increased research activity with applications in decision support which is relevant for data warehousing. In this paper, we study the translation process in the relational model. We propose a method for characterizing translations of view updates, based on the notion of inverse of a relational expression. Moreover, we characterize two kinds of updates: (1) deterministic updates regardless to the database state, and (2) deterministic updates according to some database state, and finally, we give an overview of performing view updates using the criterion of updates determinism.
Keywords : relational views; view update translations; inverses; inverse-images; strongly deterministic view updates; weakly deterministic view updates
RR-1998-04 A conditional rewrite-based method for designing combinational logic circuits
N. ANDRIANARIVELO, W. BOUSDIRA, J. CHABIN, Z. MAAZOUZI
Abstract : We present a conditional rewrite-based method to design not trivial combinational logic circuits using only Small Scale Integrated (SSI) elements. For this, we develop a maximal unit strategy method, using built-in algebras. In the present work, we assume that natural integers and boolean algebra are built-in. The formalism of constraint is used and the search space is reduced by suppressing rules according to a new goal-oriented deletion rule criteria.
Keywords : electronic components; logical gates; SSI; conditional rewriting; constraints; built-in algebras; combinational circuit design; strategies; expert system;
RR-1998-06 Graphs with chordless cycles of bounded length
I. RUSU
Abstract : The perfection of weakly triangulated graphs, i.e. antihole-free graphs whose induced cycles are isomorphic either to C_{3} or to C_{4}, was proved by Hayward and generated intense studies to efficiently solve the classical NP-complete problems which become polynomial on perfect graphs. If we replace, in the definition above, the C_{4} by an arbitrary C_{p} (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this paper. In fact, we prove a more general result: for any even integer p>=6, the graphs whose induced cycles are isomorphic either to C_{3} or to one of C_{p}, C_{p+2},..., C_{2p-6} are perfect.
Keywords : perfectness; weakly triangulated graphs; dominating pair
RR-1998-07 A System for the High-Level Parallelization and Cooperation of Constraint Solvers
L. GRANVILLIERS, G. HAINS, Q. MILLER, N. ROMERO
Abstract : A general system, Bs-Solve, is presented for the high-level programming and reuse of cooperative and parallel constraint solvers. The parallelization of two common algorithms is outlined : Groebner-basis computation for polynomial systems and Waltz consistency algorithm for continuous domains.
Keywords : Constraint solvers; cooperation; parallel strategies
RR-1998-08 Demand-driven search in functional logic programs
M. HANUS, P. RETY
Abstract : In this paper we discuss the advantage of lazy functional logic languages to solve search problems. We show that the lazy evaluation strategy of such languages can be easily exploited to implement a solver that explores only the dynamically demanded parts of the search space. In contrast to pure logic programming, the use of non-deterministic functions enables a modular and simple implementation without the risk of floundering. Furthermore, a local encapsulation of search is useful to avoid the combinatorial explosion of the demanded search space. The necessary features (laziness, non-deterministic functions, encapsulated search) are available in Curry, a new declarative language intended to combine functional and logic programming techniques. We demonstrate the advantage of this approach by a musical application implemented in Curry: the generation of appropriate chords for the accompaniment of a given melody.
Keywords : Functional logic programming; lazy evaluation; search; practical application
RR-1998-09 An introduction to BS-lambda
F. LOULERGUE, G. HAINS
Abstract : This paper is an introduction to BS-lambda a calculus of parallel-recursive BSP programs. The calculus is presented, its confluence is stated and examples are given in an ML-like syntax.
Keywords : BSP; extension of the lambda-calculus; parallel-recursive programs; confluence
RR-1998-10 Recognizing i-triangulated graphs in O(mn)
F. ROUSSEL, I. RUSU
Abstract : We use lexicographic breadth-first search and contractions of subgraphs to give a new (and better, from a complexity point of view) algorithm to recognize i-triangulated graphs.
Keywords : recognition algorithm; lexicographic breadth-first search; triangulated graph; i-triangulated graph
RR-1998-11 A linear algorithm to color i-triangulated graphs
F. ROUSSEL, I. RUSU
Abstract : We show that i-triangulated graphs can be colored in linear time by applying lexicographic breadth-first search and the greedy coloring algorithm.
Keywords : greedy algorithm; triangulated graph; i-triangulated graph; Lex-BFS
RR-1998-12 A New Result about the Decidability of the Existential One-step Rewriting Theory
S. LIMET, P. RETY
Abstract : We give a decision procedure for the whole existential fragment of one-step rewriting first-order theory, in the case where rewrite systems are linear, non left-left-overlapping (i.e. without critical pairs), and non epsilon-left-right-overlapping (i.e. no left-hand-side overlaps on top with the right-hand-side of the same rewrite rule). The procedure is defined by means of tree-tuple synchronized grammars.
Keywords : one-step rewriting; tree languages
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 