Marcello Mamino
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:
- Alessandro Berarducci
Dipartimento di Matematica, Università di Pisa, Pisa, Italy
6 shared publications - Manuel Bodirsky
Institut für Algebra, TU Dresden, Dresden, Germany
2 shared publications - Pantelis E. Eleftheriou
Department of Mathematics and Statistics, University of Konstanz, Box 216, 78457 Konstanz, Germany
2 shared publications - Rosario Mennuni
DIPARTIMENTO DI MATEMATICA UNIVERSIT À DI MILANO VIA SALDINI 50 20133 MILANO ITALY
2 shared publications - Giovanni Viglietta
University of Aizu
1 shared publication Manuel Bodirsky
TU Dresden
1 shared publication
Latest Publications
- Open Access
- 17 February 2024
- Published by Springer Nature in Archive for Mathematical Logic
- Vol. 63 (3-4) , 499-507
Vector spaces with a union of independent subspaces
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.
- 17 February 2024
- Published by Springer Nature in Archive for Mathematical Logic
- Vol. 63 (3-4) , 499-507
Open AccessVector spaces with a union of independent subspaces
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
- 1 August 2023
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 89 (3) , 1158-1179
ORTHOGONAL DECOMPOSITION OF DEFINABLE GROUPS
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.
- 1 August 2023
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 89 (3) , 1158-1179
Open AccessORTHOGONAL DECOMPOSITION OF DEFINABLE GROUPS
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
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 AccessVector spaces with a union of independent subspaces
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
- 7 May 2022
- Published by Springer Nature in Bollettino dell'Unione Matematica Italiana
- Vol. 16 (1) , 1-17
Provability logic: models within models in Peano Arithmetic
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}}\,}}$$ does not prove that $${{\,\mathrm{\mathrm {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}}\,}}$$ , that the existence of a model of $${{\,\mathrm{\mathrm {PA}}\,}}$$ of complexity $$\Sigma ^0_2$$ is independent of $${{\,\mathrm{\mathrm {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$$ -model”.- 7 May 2022
- Published by Springer Nature in Bollettino dell'Unione Matematica Italiana
- Vol. 16 (1) , 1-17
Open AccessProvability logic: models within models in Peano Arithmetic
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}}\,}}$$ does not prove that $${{\,\mathrm{\mathrm {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}}\,}}$$ , that the existence of a model of $${{\,\mathrm{\mathrm {PA}}\,}}$$ of complexity $$\Sigma ^0_2$$ is independent of $${{\,\mathrm{\mathrm {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$$ -model”. - Open Access
Orthogonal decomposition of definable groups
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 AccessOrthogonal decomposition of definable groups
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
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.Open AccessProvability Logic: models within models in Peano Arithmetic
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. - 17 April 2017
- Published by Springer Nature in Theory of Computing Systems
- Vol. 62 (3) , 481-509
Tropically Convex Constraint Satisfaction
- 17 April 2017
- Published by Springer Nature in Theory of Computing Systems
- Vol. 62 (3) , 481-509
Tropically Convex Constraint Satisfaction
- Open Access
Tropically convex constraint satisfaction
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 AccessTropically convex constraint satisfaction
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.
- 31 May 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 88-101
Max-Closed Semilinear Constraint Satisfaction
- 31 May 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 88-101
Max-Closed Semilinear Constraint Satisfaction
- Open Access
Square Formation by Asynchronous Oblivious Robots
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.
Open AccessSquare Formation by Asynchronous Oblivious Robots
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.