BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Marcello Mamino

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.LOComputational Complexitycond-mat.dis-nncond-mat.stat-mechLogic in Computer ScienceComputational GeometryComputer Science and Game TheoryDistributed, Parallel, and Cluster Computingmath.OCphysics.soc-phRobotics

Catalog footprint

Research overview

14works
11topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

14 publications

preprint2022arXiv

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: 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 Σ20Σ^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 Σ20Σ^0_2-model.

Open access
preprint2020arXiv

Asymptotic analysis of Skolem's exponential functions

Skolem (1956) studied the germs at infinity of the smallest class of real valued functions on the positive real line containing the constant 11, the identity function xx, and such that whenever ff and gg are in the set, f+g,fgf+g,fg and fgf^g are in the set. This set of germs is well ordered and Skolem conjectured that its order type is epsilon-zero. Van den Dries and Levitz (1984) computed the order type of the fragment below 22x2^{2^x}. Here we prove that the set of asymptotic classes within any archimedean class of Skolem functions has order type ωω. As a consequence we obtain, for each positive integer nn, an upper bound for the fragment below 2nx2^{n^x}. We deduce an epsilon-zero upper bound for the fragment below 2xx2^{x^x}, improving the previous epsilon-omega bound by Levitz (1978). A novel feature of our approach is the use of Conway's surreal number for asymptotic calculations.

Open access
preprint2019arXiv

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

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 functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

Open access
preprint2016arXiv

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 access
preprint2015arXiv

On definably proper maps

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 is definably proper if and only if it is proper morphism in the category of definable spaces. We give several other characterizations of definably proper including one involving the existence of limits of definable types. We also prove the basic properties of definably proper maps and the invariance of definably proper in elementary extensions and o-minimal expansions.

Open access
preprint2014arXiv

Condensation and topological phase transitions in a dynamical network model with rewiring of the links

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 attachment with rewiring of the links. Rewiring probabilities are modulated by the negative fitness of the nodes and by the constraint for the network to be a simple graph. At low temperatures and high rewiring rates, this constraint induces a Bose-Einstein condensation of paths of length 2, i.e. a new phase transition with an extended condensate of links. The phase space of the model includes further transitions in the scaling of the connected component and the degeneracy of the network.

Open access
preprint2014arXiv

Duality between preferential attachment and static random networks on hyperbolic spaces

There is a complex relation between the mechanism of preferential attachment, scale-free degree distributions and hyperbolicity in complex networks. In fact, both preferential attachment and hidden hyperbolic spaces often generate scale-free networks. We show that there is actually a duality between a class of growing spatial networks based on preferential attachment on the sphere and a class of static random networks on the hyperbolic plane. Both classes of networks have the same scale-free degree distribution as the Barabasi-Albert model. As a limit of this correspondence, the Barabasi-Albert model is equivalent to a static random network on an hyperbolic space with infinite curvature.

Open access
preprint2014arXiv

On the Computing Power of ++, −-, and ×\times

Modify the Blum-Shub-Smale model of computation replacing the permitted computational primitives (the real field operations) with any finite set BB of real functions semialgebraic over the rationals. Consider the class of boolean decision problems that can be solved in polynomial time in the new model by machines with no machine constants. How does this class depend on BB? We prove that it is always contained in the class obtained for B={+,−,×}B = \{+, -, \times\}. Moreover, if BB is a set of continuous semialgebraic functions containing ++ and −-, and such that arbitrarily small numbers can be computed using BB, then we have the following dichotomy: either our class is P\mathsf P or it coincides with the class obtained for B={+,−,×}B = \{+, -, \times\}.

Open access
preprint2013arXiv

Groups definable in two orthogonal sorts

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 two-sorted structure). We show that if one of the two structures is superstable of finite Lascar rank and the Lascar rank is definable, then G is an extension of a group internal to the (possibly) unstable sort by a definable subgroup internal to the stable sort. In the final part of the paper we show that if the unstable sort is an o-minimal expansion of the reals, then G has a natural Lie structure and the extension is a topological cover.

Open access
preprint2012arXiv

Discrete subgroups of locally definable groups

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 group G in this category is a cover of a definable group. We prove that this is the case under a natural convexity assumption inspired by the same authors, which in fact gives a necessary and sufficient condition. The proof is based on the study of the zero-dimensional compatible subgroups of G. Given a locally definable connected group G (not necessarily definably generated), we prove that the n-torsion subgroup of G is finite and that every zero-dimensional compatible subgroup of G has finite rank. Under a convexity hypothesis we show that every zero-dimensional compatible subgroup of G is finitely generated.

Open access
preprint2012arXiv

On the computational complexity of a game of cops and robbers

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 moving cops attempt to capture a single robber, all moving at the same speed. The players are allowed to pick their starting positions at the first move. The question of the computational complexity of deciding this game was raised in the '90s by Goldstein and Reingold. We prove that the game is hard for PSPACE.

Open access
preprint2011arXiv

Splitting definably compact groups in o-minimal structures

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 definably compact definably connected groups definable in an o-minimal expansion of a real closed field. As opposed to the Lie case, however, we provide an example showing that the derived subgroup may not have a definable semidirect complement.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.