In this paper we consider the relative expressive power of two very common operators applicable to sets and multisets: the with and the union operators. For such operators we prove that they are not mutually expressible by means of existentially quantified formulae In order to prove our results, canonical forms for set-theoretic and multiset-theoretic formulae are established and a particularly natural axiomatization of multisets is given and studied.

Comparing Expressiveness of Set Constructor Symbols

DOVIER, Agostino;PIAZZA, Carla;POLICRITI, Alberto
2000

Abstract

In this paper we consider the relative expressive power of two very common operators applicable to sets and multisets: the with and the union operators. For such operators we prove that they are not mutually expressible by means of existentially quantified formulae In order to prove our results, canonical forms for set-theoretic and multiset-theoretic formulae are established and a particularly natural axiomatization of multisets is given and studied.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/738669
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact