We study translations of dyadic first-order sentences into equalities between relational expressions. The proposed translation techniques (which work also in the converse direction) exploit a graphical representation of formulae in a hybrid of the two formalisms. A major enhancement relative to previous work is that we can cope with the relational complement construct and with the negation connective. Complementation is handled by adopting a Smullyan-like uniform notation to classify and decompose relational expressions; negation is treated by means of a generalized graph-representation of formulae in ℒ+, and through a series of graph-transformation rules which reflect the meaning of connectives and quantifiers.
Keywords: algebra of binary relations, quantifier elimination, graph transformation
@article{ITA_2012__46_2_261_0,
author = {Cantone, Domenico and Formisano, Andrea and Asmundo, Marianna Nicolosi and Omodeo, Eugenio Giovanni},
title = {A graphical representation of relational formulae with complementation},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {261--289},
year = {2012},
publisher = {EDP-Sciences},
volume = {46},
number = {2},
doi = {10.1051/ita/2012003},
mrnumber = {2931249},
zbl = {1254.03020},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012003/}
}
TY - JOUR AU - Cantone, Domenico AU - Formisano, Andrea AU - Asmundo, Marianna Nicolosi AU - Omodeo, Eugenio Giovanni TI - A graphical representation of relational formulae with complementation JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 261 EP - 289 VL - 46 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012003/ DO - 10.1051/ita/2012003 LA - en ID - ITA_2012__46_2_261_0 ER -
%0 Journal Article %A Cantone, Domenico %A Formisano, Andrea %A Asmundo, Marianna Nicolosi %A Omodeo, Eugenio Giovanni %T A graphical representation of relational formulae with complementation %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 261-289 %V 46 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012003/ %R 10.1051/ita/2012003 %G en %F ITA_2012__46_2_261_0
Cantone, Domenico; Formisano, Andrea; Asmundo, Marianna Nicolosi; Omodeo, Eugenio Giovanni. A graphical representation of relational formulae with complementation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 2, pp. 261-289. doi: 10.1051/ita/2012003
Cité par Sources :