Logic Colloquium 2024


Ludovico Fusco

University of Urbino

Talks at this conference:

  Friday, 14:50, J222

Modeling hyperproperties for RFID systems

Authors: Alessandro Aldini and Ludovico Fusco

Since its official patenting in the 1980s, the Radio-Frequency Identification (RFID) technology has experienced relentless advancement due to its extreme versatility and usability in a wide range of contexts. Moreover, as an enabling technology for the IoT computing paradigm, RFID today underpins new tools for object identification/data acquisition in smart environments.

Although there have been many contributions to the formal description and verification of RFID-based systems and protocols, there has yet to be much progress toward an explicit modeling of information flow policies for RFID systems in terms of hyperproperties [1]. In this work, we initiate a taxonomy of hyperproperties for RFID systems, laying the foundation for a general framework for their formalization. To this end, we introduce a low-level, trace-based model suitable for representing RFID systems implementing tree protocols for tag collision arbitration [3]. Our model features a component-oriented, event-based notion of state allowing us to express hyperproperties in terms of event satisfaction by component configurations.

In this context, we introduce and discuss three classes of hyperproperties for the analysis of tree-based anti-collision protocols for RFID tags: hyper-reachability, hyper-adaptivity, and generalized non-interference. For each of them, we provide a classical definition in the style of [1] and a formalization in a suitable hyperlogic [2]. Finally, we propose some insights about decidability issues.


  1. Clarkson, M.R., Schneider, F.B.,Hyperproperties,Journal of Computer Security,vol. XVIII (2010), no. VI, pp. 1157–1210.
  2. Coenen, N., Finkbeiner, B., Hahn, C., Hofmann, J.,The Hierarchy of Hyperlogics,LICS ‘19: Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science(Vancouver, Canada),article no. 39,2019,pp. 1–13.
  3. Popovski, P.,Tree-Based Anti-Collision Protocols for RFID Tags,RFID Systems: Research Trends and Challenges(Miodrag Bolic, David Simplot-Ryl, and Ivan Stojmenovic, editors),Wiley,2010,pp. 203–229.
  Tuesday, 17:45, J330

Multi-relation Agassiz sums of algebras

Authors: Ludovico Fusco and Francesco Paoli

Płonka sums are a simple yet powerful technique for building new algebras out of semilattice direct systems of algebras of a fixed type. First introduced by J. Płonka [2] in 1967, this construction immediately proved to be essential for the representation of algebras in regular varieties [3]. The aptness of Płonka sums to this purpose can be seen, at the same time, as a shortcoming, since this construction is of little avail outside this particular domain of application.

Remarkably, however, the literature teems with ‘Płonka-type’ constructions used for the representation of algebras in irregular varieties, or in varieties having certain properties stronger than regularity. All these constructions bear striking similarities to Płonka sums, but differ from them in some important respects. Examples include the representation of Polin algebras [4], T. Katriňák and J. Guričan’s representation of pseudocomplemented semilattices [1], or the recently introduced De Morgan-Pł,onka sums [5].

We aim at finding a convenient umbrella under which all these constructions can be subsumed. We introduce a multi-relation variant of G. Grätzer and J. Sichler’s sums over Agassiz systems of algebras (Agassiz sums) [6] that encompasses Płonka sums as a special case. We prove that the above-mentioned representations of Polin algebras and pseudocomplemented semilattices, as well as De Morgan-Płonka sums, can be recast in terms of sums over appropriate bi-relation Agassiz systems. Finally, we investigate the problem as to which identities are preserved by the construction.


  1. Katriňák, T., Guričan, J.,On a new construction of pseudocomplemented semilattices,Algebra Universalis,vol. LXXXII (2021), article no. 54.
  2. Płonka, J.,On a method of construction of abstract algebras,Fundamenta Mathematicae,vol. LXI (1967), no. II, pp. 183–189.
  3. —, On equational classes of abstract algebras defined by regular equations,Fundamenta Mathematicae,vol. LXIV (1969), no. II, pp. 241–247.
  4. Polin, S.V.,Identities in congruence lattices of universal algebras,Matematicheskie Zametki,vol. XXII (1977), no. III, pp. 443–451.
  5. Randriamahazaka, T.,De Morgan-Płonka sums,Studia Logica,forthcoming.
  6. Grätzer, G., Sichler, J.,Agassiz sums of algebras,Colloquium Mathematicum,vol. XXX (1974), no. I, pp. 57–59.