MMMarcello Mamino

Marcello Mamino

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Marcello Mamino has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Vector spaces with a union of independent subspaces

    by Alessandro Berarducci, Marcello Mamino, Rosario Mennuni

    We study the theory of K-vector spaces with a predicate for the union X of an infinite family of independent subspaces. We show that if K is infinite then the theory is complete and admits quantifier elimination in the language of K-vector spaces with predicates for the n-fold sums of X with itself. If K is finite this is no longer true, but we still have that a natural completion is near-model-complete.

  • Open Access

    ORTHOGONAL DECOMPOSITION OF DEFINABLE GROUPS

    by Alessandro Berarducci, Pantelis E. Eleftheriou, Marcello Mamino

    Orthogonality in model theory captures the idea of absence of non-trivial interactions between definable sets. We introduce a somewhat opposite notion of cohesiveness, capturing the idea of interaction among all parts of a given definable set. A cohesive set is indecomposable, in the sense that if it is internal to the product of two orthogonal sets, then it is internal to one of the two. We prove that a definable group in an o-minimal structure is a product of cohesive orthogonal subsets. If the group has dimension one, or it is definably simple, then it is itself cohesive. As an application, we show that an abelian group definable in the disjoint union of finitely many o-minimal structures is a quotient, by a discrete normal subgroup, of a direct product of locally definable groups in the single structures.

  • Open Access

    Vector spaces with a union of independent subspaces

    by Alessandro Berarducci, Marcello Mamino, Rosario Mennuni

    Motivated by the theory of locally definable groups, we study the theory of $K$-vector spaces with a predicate for the union $X$ of an infinite family of independent subspaces. We show that if $K$ is infinite then the theory is complete and admits quantifier elimination in the language of $K$-vector spaces with predicates for the $n$-fold sums of $X$ with itself. If $K$ is finite this is no longer true, but we still have that a natural completion is near-model-complete.

  • Open Access

    Provability logic: models within models in Peano Arithmetic

    by Alessandro Berarducci, Marcello Mamino

    In 1994 Jech gave a model-theoretic proof of Gödel’s second incompleteness theorem for Zermelo–Fraenkel set theory in the following form: $${{\,\mathrm{\mathrm {ZF}}\,}}$$ ZF does not prove that $${{\,\mathrm{\mathrm {ZF}}\,}}$$ ZF has a model. Kotlarski showed that Jech’s proof can be adapted to Peano Arithmetic with the role of models being taken by complete consistent extensions. In this note we take another step in the direction of replacing proof-theoretic by model-theoretic arguments. We show, without the need of formalizing the proof of the completeness theorem within $${{\,\mathrm{\mathrm {PA}}\,}}$$ PA , that the existence of a model of $${{\,\mathrm{\mathrm {PA}}\,}}$$ PA of complexity $$\Sigma ^0_2$$ Σ 2 0 is independent of $${{\,\mathrm{\mathrm {PA}}\,}}$$ PA , where a model is identified with the set of formulas with parameters which hold in the model. Our approach is based on a new interpretation of the provability logic of Peano Arithmetic where $$\Box \phi $$ □ ϕ is defined as the formalization of “ $$\phi $$ ϕ is true in every $$\Sigma ^0_2$$ Σ 2 0 -model”.


  • Open Access

    Orthogonal decomposition of definable groups

    by Alessandro Berarducci, Pantelis E. Eleftheriou, Marcello Mamino

    Orthogonality in model theory captures the idea of absence of non-trivial interactions between definable sets. We introduce a somewhat opposite notion of cohesiveness, capturing the idea of interaction among all parts of a given definable set. A cohesive set is indecomposable, in the sense that if it is internal to the product of two orthogonal sets, then it is internal to one of the two. We prove that a definable group in an o-minimal structure is a product of cohesive orthogonal subsets. If the group has dimension one, or it is definably simple, then it is itself cohesive. Finally, we show that an abelian group definable in the disjoint union of finitely many o-minimal structures is a quotient, by a discrete normal subgroup, of a direct product of locally definable groups in the single structures.

  • Open Access

    Provability Logic: models within models in Peano Arithmetic

    by Alessandro Berarducci, Marcello Mamino

    In 1994 Jech gave a model theoretic proof of G\"odel's second incompleteness theorem for Zermelo-Fraenkel set theory in the following form: ZF does not prove that ZF has a model. Kotlarski showed that Jech's proof can be adapted to Peano Arithmetic with the role of models being taken by complete consistent extensions. In this note we take another step in the direction of replacing proof-theoretic by model-theoretic arguments. We show, without passing through the arithmetized completeness theorem, that the existence of a model of PA of complexity $\Sigma^0_2$ is independent of PA, where a model is identified with the set of formulas with parameters which hold in the model. Our approach is based on a new interpretation of the provability logic of Peano Arithmetic with the modal operator interpreted as truth in every $\Sigma^0_2$-model.

  • Tropically Convex Constraint Satisfaction

    by Manuel Bodirsky, Marcello Mamino


  • Open Access

    Tropically convex constraint satisfaction

    by Manuel Bodirsky, Marcello Mamino

    A semilinear relation S is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be in the intersection of NP and co-NP, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinaer constraints in general into NP intersected co-NP. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of max-closed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in P; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not max-closed is added to L, the CSP becomes NP-hard.

  • Open Access

    Square Formation by Asynchronous Oblivious Robots

    by Marcello Mamino, Giovanni Viglietta

    A fundamental problem in Distributed Computing is the Pattern Formation problem, where some independent mobile entities, called robots, have to rearrange themselves in such a way as to form a given figure from every possible (non-degenerate) initial configuration. In the present paper, we consider robots that operate in the Euclidean plane and are dimensionless, anonymous, oblivious, silent, asynchronous, disoriented, non-chiral, and non-rigid. For this very elementary type of robots, the feasibility of the Pattern Formation problem has been settled, either in the positive or in the negative, for every possible pattern, except for one case: the Square Formation problem by a team of four robots. Here we solve this last case by giving a Square Formation algorithm and proving its correctness. Our contribution represents the concluding chapter in a long thread of research. Our results imply that in the context of the Pattern Formation problem for mobile robots, features such as synchronicity, chirality, and rigidity are computationally irrelevant.