Median based calculus for lattice polynomials and monotone Boolean functions

Miguel Couceiro 1 Pierre Mercuriali 2 Romain Péchoux 2 Abdallah Saffidine 3
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this document, we consider a median-based calculus for efficiently representing polynomial functions over distributive lattices. We extend an equational specification of median forms from the domain of Boolean functions to the domain of lattice polynomials. We show that it is sound and complete, and we illustrate its usefulness when simplifying median formulas algebraically. Furthermore, we propose a definition of median normal forms (MNF), that are thought of as minimal median formulas with respect to a structural ordering of expressions. We also investigate related complexity issues and show that the problem of deciding whether a formula is in MNF is in Σ^P_2. Moreover, we explore polynomial approximations of solutions to this problem through a sound term rewriting system extracted from the proposed equational specification.
Type de document :
Communication dans un congrès
ISMVL 2017 - 47th IEEE International Symposium on Multiple-Valued Logic, May 2017, Novi Sad, Serbia. IEEE Computer Society, pp.6, 2017
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01504010
Contributeur : Miguel Couceiro <>
Soumis le : samedi 8 avril 2017 - 01:09:01
Dernière modification le : lundi 15 janvier 2018 - 16:04:05
Document(s) archivé(s) le : dimanche 9 juillet 2017 - 12:16:05

Fichier

median-computations-Revised.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01504010, version 1

Citation

Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine. Median based calculus for lattice polynomials and monotone Boolean functions. ISMVL 2017 - 47th IEEE International Symposium on Multiple-Valued Logic, May 2017, Novi Sad, Serbia. IEEE Computer Society, pp.6, 2017. 〈hal-01504010〉

Partager

Métriques

Consultations de la notice

411

Téléchargements de fichiers

94