13 citations · 46 across the 21 of their papers we have counts for
26 papers
Reflections on Trusting Lean
Lorenzo Bresolin, Marcello Mamino
It is known, by works of Werner and Carneiro, that the type theory of Lean (and indeed of CIC plus a version of choice) is equiconsistent with ZFC plus "there are infinitely many s…
Vector spaces with a union of independent subspaces
Alessandro Berarducci, Marcello Mamino, Rosario Mennuni
Motivated by the theory of locally definable groups, we study the theory of -vector spaces with a predicate for the union of an infinite family of independent subspaces. We…
Provability Logic: models within models in Peano Arithmetic
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: ZF does not prove that ZF has a model. Kot…
Orthogonal decomposition of definable groups
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 th…
One Lie group to define them all
Annalisa Conversano, Marcello Mamino
We produce a connected real Lie group that, as a first order structure in the group language, interprets the real field expanded with a predicate for the integers. Moreover, the do…
Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables
Manuel Bodirsky, Marcello Mamino, Caterina Viola
Many combinatorial optimisation problems can be modelled as valued constraint satisfaction problems. In this paper, we present a polynomial-time algorithm solving the valued constr…
Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
Manuel Bodirsky, Marcello Mamino, Caterina Viola
Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost f…
Asymptotic analysis of Skolem's exponential functions
Alessandro Berarducci, Marcello Mamino
Skolem (1956) studied the germs at infinity of the smallest class of real valued functions on the positive real line containing the constant , the identity function , and suc…
A polynomial-time algorithm for median-closed semilinear constraints
Manuel Bodirsky, Marcello Mamino
A subset of Q^n is called semilinear (or piecewise linear) if it is Boolean combination of linear half-spaces. We study the computational complexity of the constraint satisfaction…
The complexity of disjunctive linear Diophantine constraints
Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1
We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.
Fundamental group in o-minimal structures with definable Skolem functions
Bruno Dinis, Mário J. Edmundo, Marcello Mamino
In this paper we work in an arbitrary o-minimal structure with definable Skolem functions and we prove that definably connected, locally definable manifolds are uniformly definably…
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
Manuel Bodirsky, Marcello Mamino, Caterina Viola
Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs dependin…
Square Formation by Asynchronous Oblivious Robots
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 a…
On the o-minimal Hilbert's fifth problem
Mario J. Edmundo, Marcello Mamino, Luca Prelli +2
Let be an arbitrary o-minimal structure. Let be a definably compact definably connected abelian definable group of dimension . Here we compute the new the intr…
Strategy Recovery for Stochastic Mean Payoff Games
Marcello Mamino
We prove that to find optimal positional strategies for stochastic mean payoff games when the value of every state of the game is known, in general, is as hard as solving such game…
Tropically convex constraint satisfaction
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…
On definably proper maps
Mário Edmundo, Marcello Mamino, Luca Prelli
In this paper we work in o-minimal structures with definable Skolem functions and show that a continuous definable map between Hausdorff locally definably compact definable spaces…
On the Computing Power of , , and
Marcello Mamino
Modify the Blum-Shub-Smale model of computation replacing the permitted computational primitives (the real field operations) with any finite set of real functions semialgebraic…
Condensation and topological phase transitions in a dynamical network model with rewiring of the links
Luca Ferretti, Marcello Mamino, Ginestra Bianconi
Growing network models with both heterogeneity of the nodes and topological constraints can give rise to a rich phase structure. We present a simple model based on preferential att…
Groups definable in two orthogonal sorts
Alessandro Berarducci, Marcello Mamino
This work can be thought as a contribution to the model theory of group extensions. We study the groups G which are interpretable in the disjoint union of two structures (seen as a…
On the computational complexity of a game of cops and robbers
Marcello Mamino
We study the computational complexity of a perfect-information two-player game proposed by Aigner and Fromme. The game takes place on an undirected graph where n simultaneously mov…
Discrete subgroups of locally definable groups
Alessandro Berarducci, Mário Edmundo, Marcello Mamino
We work in the category of locally definable groups in an o-minimal expansion of a field. Eleftheriou and Peterzil conjectured that every definably generated abelian connected grou…
Splitting definably compact groups in o-minimal structures
Marcello Mamino
An argument of A.Borel shows that every compact connected Lie group is homeomorphic to the Cartesian product of its derived subgroup and a torus. We prove a parallel result for def…
On the homotopy type of definable groups in an o-minimal structure
A. Berarducci, M. Mamino
Given a definably compact group G in a saturated o-minimal structure, there is a canonical homomorphism from G to a compact real Lie group F(G). We establish a similar result for t…