8 citations · 15 across the 15 of their papers we have counts for
15 papers
Preorder Preservation versus Congruence Preservation
Patrick Cégielski, Irène Guessarian
Looking at some monoids and (semi)rings (natural numbers, integers and -adic integers), and more generally, residually finite algebras (in a strong sense), we prove the equivale…
Congruence Preservation, Lattices and Recognizability
Patrick Cegielski, Serge Grigorieff, Irene Guessarian
We study in general algebras Gratzer's notion of congruence preserving function, characterizing functions in terms of stability under inverse image of particular Boolean algebras o…
Affine completeness of some free binary algebras
André Arnold, Patrick Cégielski, Irène Guessarian
A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. An algebra is said to be affine comp…
The algebra of binary trees is affine complete
Andre Arnold, Patrick Cegielski, Serge Grigorieff +1
A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binar…
The algebra of complete binary trees is affine complete
A. Arnold, P. Cegielski, S. Grigorieff +1
A function on an algebra is congruence preserving if, for any congruence, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of compl…
Congruence Preservation, Lattices and Recognizability
Patrick Cegielski, Serge Grigorieff, Irene Guessarian
Looking at some monoids and (semi)rings (natural numbers, integers and p-adic integers), and more generally, residually finite algebras (in a strong sense), we prove the equivalenc…
Congruence Preserving Functions on Free Monoids
Patrick Cégielski, Serge Grigorieff, Irène Guessarian
A function on an algebra is congruence preserving if, for any congruence, it maps congruent elements to congruent elements. We show that, on a free monoid generated by at least 3 l…
Arithmetical Congruence Preservation: from Finite to Infinite
Patrick Cégielski, Serge Grigorieff, Irène Guessarian
Various problems on integers lead to the class of congruence preserving functions on rings, i.e. functions verifying divides for all . We characterized these…
Characterizing congruence preserving functions via rational polynomials
Patrick Cegielski, Serge Grigorieff, Irene Guessarian
We introduce a basis of rational polynomial-like functions for the free module of functions . We then characterize the subfamily of congruence pr…
Newton representation of functions over natural integers having integral difference ratios
Patrick Cegielski, Serge Grigorieff, Irene Guessarian
Different questions lead to the same class of functions from natural integers to integers: those which have integral difference ratios, i.e. verifying $f(a)-f(b)\equiv0 \pmod {(a-b…
On Lattices of Regular Sets of Natural Integers Closed under Decrementation
Patrick Cégielski, Serge Grigorieff, Irène Guessarian
We consider lattices of regular sets of non negative integers, i.e. of sets definable in Presbuger arithmetic. We prove that if such a lattice is closed under decrement then it is…
Complexity of Monadic inf-datalog. Application to temporal logic
Eugénie Foustoucos, Irene Guessarian
In [11] we defined Inf-Datalog and characterized the fragments of Monadic inf-Datalog that have the same expressive power as Modal Logic (resp. , alternation-free Modal -ca…
Automatic generation of simplified weakest preconditions for integrity constraint verification
A. Ai T -Bouziad, Irene Guessarian, L. Vieille
Given a constraint assumed to hold on a database and an update to be performed on , we address the following question: will still hold after is performed? Wh…
Multiple serial episode matching
Patrick Cegielski, Irene Guessarian, Yuri Matiyasevich
In a previous paper we generalized the Knuth-Morris-Pratt (KMP) pattern matching algorithm and defined a non-conventional kind of RAM, the MP--RAMs (RAMS equipped with extra operat…
On relating CTL to Datalog
Foto Afrati, Theodore Andronikos, Vassia Pavlaki +2
CTL is the dominant temporal specification language in practice mainly due to the fact that it admits model checking in linear time. Logic programming and the database query langua…