Giancarlo Mauri

TCS Journal 2022 Journal Article

Depth-two P systems can simulate Turing machines with NP oracles

• Alberto Leporati
• Luca Manzoni
• Giancarlo Mauri
• Claudio Zandron

Among the computational features that determine the computing power of polarizationless P systems with active membranes, the depth of the membrane hierarchy is one of the least explored. It is known that this model of P systems can solve Image 2 -complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P ∥ # P is characterized by monodirectional shallow P systems with minimal cooperation, whose depth is 1. No similar result is currently known for polarizationless systems without cooperation or other additional features. In this paper we show that these P systems, using a membrane hierarchy of depth 2, are able to solve at least all decision problems that are in the complexity class Image 3, the class of problems solved in polynomial time by deterministic Turing machines that are given the possibility to make a polynomial number of parallel queries to oracles for Image 4 problems.

I&C Journal 2022 Journal Article

On the complexity of approximately matching a string to a directed graph

• Riccardo Dondi
• Giancarlo Mauri
• Italo Zoppis

The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only to the graph labels or both to the graph labels and the query string. We show that deciding if there exists a path in a graph that represents a query string with edit operations to vertex labels is an NP-complete problem and it is fixed-parameter tractable when parameterized by the length of the input string. We show that the variants of approximate string matching we consider are not fixed-parameter tractable, when the parameter is (1) the length of the query string and (2) the number of edit operations. Moreover, we provide inapproximability results for these variants of the of approximate string matching problem.

JBHI Journal 2020 Journal Article

cuProCell: GPU-Accelerated Analysis of Cell Proliferation With Flow Cytometry Data

• Marco S. Nobile
• Eric Nisoli
• Thalia Vlachou
• Simone Spolaor
• Paolo Cazzaniga
• Giancarlo Mauri
• Pier Giuseppe Pelicci
• Daniela Besozzi

The investigation of cell proliferation can provide useful insights for the comprehension of cancer progression, resistance to chemotherapy and relapse. To this aim, computational methods and experimental measurements based on in vivo label-retaining assays can be coupled to explore the dynamic behavior of tumoral cells. ProCell is a software that exploits flow cytometry data to model and simulate the kinetics of fluorescence loss that is due to stochastic events of cell division. Since the rate of cell division is not known, ProCell embeds a calibration process that might require thousands of stochastic simulations to properly infer the parameterization of cell proliferation models. To mitigate the high computational costs, in this paper we introduce a parallel implementation of ProCell's simulation algorithm, named cuProCell, which leverages Graphics Processing Units (GPUs). Dynamic Parallelism was used to efficiently manage the cell duplication events, in a radically different way with respect to common computing architectures. We present the advantages of cuProCell for the analysis of different models of cell proliferation in Acute Myeloid Leukemia (AML), using data collected from the spleen of human xenografts in mice. We show that, by exploiting GPUs, our method is able to not only automatically infer the models' parameterization, but it is also 237× faster than the sequential implementation. This study highlights the presence of a relevant percentage of quiescent and potentially chemoresistant cells in AML in vivo, and suggests that maintaining a dynamic equilibrium among the different proliferating cell populations might play an important role in disease progression.

TCS Journal 2020 Journal Article

Subroutines in P systems and closure properties of their complexity classes

• Alberto Leporati
• Luca Manzoni
• Giancarlo Mauri
• Antonio E. Porreca
• Claudio Zandron

The literature on membrane computing describes several variants of P systems whose complexity classes C are “closed under exponentiation”, that is, they satisfy the inclusion Image 1, where Image 2 is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many other operations, such as regular operations (union, concatenation, Kleene star), intersection, complement, and polynomial-time mappings, which are inherited from Image 3. Such results are typically proved by showing how elements of a family Image 4 of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of Image 4 as subroutines. Here we focus on the latter construction, providing a description that, by abstracting from the technical details which depend on the specific variant of P system, describes a general strategy for proving closure under exponentiation. We also provide an example implementation using polarizationless P systems with active membranes and minimal cooperation.

TCS Journal 2019 Journal Article

Comparing incomplete sequences via longest common subsequence

• Mauro Castelli
• Riccardo Dondi
• Giancarlo Mauri
• Italo Zoppis

Inspired by scaffold filling, a recent approach for genome reconstruction from incomplete data, we consider a variant of the well-known longest common subsequence problem for the comparison of two sequences. The new problem, called Longest Filled Common Subsequence, aims to compare a complete sequence with an incomplete one, i. e. with some missing elements. Longest Filled Common Subsequence (LFCS), given a complete sequence A, an incomplete sequence B, and a multiset M of symbols missing in B, asks for a sequence B ⁎ obtained by inserting the symbols of M into B so that B ⁎ induces a common subsequence with A of maximum length. We investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol, and we give a polynomial time algorithm when the input sequences are over a constant-size alphabet. We give a 3 5 − approximation algorithm for the Longest Filled Common Subsequence problem. Finally, we present a fixed-parameter algorithm for the problem, when it is parameterized by the number of symbols inserted in B that “match” symbols of A.

TCS Journal 2019 Journal Article

On the tractability of finding disjoint clubs in a network

• Riccardo Dondi
• Giancarlo Mauri
• Italo Zoppis

We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t ≥ 2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s = 2, t = 3 and r = | V |. Moreover, we show that the problem is polynomial-time solvable when s ≥ 4, t = 3 and r = | V |, and when s ≥ 3, t = 2 and r = | V |. Finally, for s ≥ 2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices.

TCS Journal 2018 Journal Article

Editorial

• Riccardo Dondi
• Guillaume Fertin
• Giancarlo Mauri

TCS Journal 2017 Journal Article

A toolbox for simpler active membrane algorithms

• Alberto Leporati
• Luca Manzoni
• Giancarlo Mauri
• Antonio E. Porreca
• Claudio Zandron

We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions, such as sending out several, possibly contradictory results and keeping only the first one, or rejecting by halting without output, are also equivalent to the standard accepting conditions. The simulations we propose are always without significant loss of efficiency, and thus the results of this paper can hopefully simplify the design of algorithms for P systems with active membranes.

TCS Journal 2017 Journal Article

Computational complexity of finite asynchronous cellular automata

• Alberto Dennunzio
• Enrico Formenti
• Luca Manzoni
• Giancarlo Mauri
• Antonio E. Porreca

Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or Π 2 P -complete (universal version) for higher dimension.

TCS Journal 2017 Journal Article

The counting power of P systems with antimatter

• Alberto Leporati
• Luca Manzoni
• Giancarlo Mauri
• Antonio E. Porreca
• Claudio Zandron

We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P # P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class P ∥ # P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass P ∥ NP.

TCS Journal 2014 Journal Article

Space complexity equivalence of P systems with active membranes and Turing machines

• Artiom Alhazov
• Alberto Leporati
• Giancarlo Mauri
• Antonio E. Porreca
• Claudio Zandron

We prove that arbitrary single-tape Turing machines can be simulated by uniform families of P systems with active membranes with a cubic slowdown and quadratic space overhead. This result is the culmination of a series of previous partial results, finally establishing the equivalence (up to a polynomial) of many space complexity classes defined in terms of P systems and Turing machines. The equivalence we obtained also allows a number of classic computational complexity theorems, such as Savitch's theorem and the space hierarchy theorem, to be directly translated into statements about membrane systems.

I&C Journal 2014 Journal Article

Stochastic Hybrid Automata with delayed transitions to model biochemical systems with delays

• Giulio Caravagna
• Alberto d'Onofrio
• Marco Antoniotti
• Giancarlo Mauri

To study the effects of a delayed immune-response on the growth of an immunogenic neoplasm we introduce Stochastic Hybrid Automata with delayed transitions as a representation of hybrid biochemical systems with delays. These transitions abstractly model unknown dynamics for which a constant duration can be estimated, i. e. a delay. These automata are inspired by standard Stochastic Hybrid Automata, and their semantics is given in terms of Piecewise Deterministic Markov Processes. The approach is general and can be applied to systems where (i) components at low concentrations are modeled discretely (so to retain their intrinsic stochastic fluctuations), (ii) abundant component, e. g. , chemical signals, are well approximated by mean-field equations (so to simulate them efficiently) and (iii) missing components are abstracted with delays. Via simulations we show in our application that interesting delay-induced phenomena arise, whose quantification is possible in this new quantitative framework.

TCS Journal 2013 Journal Article

The l -Diversity problem: Tractability and approximability

• Riccardo Dondi
• Giancarlo Mauri
• Italo Zoppis

Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i. e. k -Anonymity and l -Diversity. Given an input table, these approaches partition its rows so that the computed partition satisfies some constraint, in order to prevent the inference of the individuals the data belong to. Then, the rows in a same set of the partition are related to the same rows by suppressing some of their entries. Here we focus on the l -Diversity problem, where the attributes of the input table are distinguished in sensitive attributes and quasi-identifier attributes. The goal is to partition the rows of the input table, so that each set C of the partition contains at most 1 l | C | rows having a specific value in the sensitive attribute, and the number of suppressions is minimized. In this paper we investigate the approximation and parameterized complexity of l -Diversity. First, we prove that the problem is not approximable within factor c ln l, for some constant c > 0, even if the input table consists of only two columns, and that the problem is APX-hard, even if l = 4 and the input table contains exactly three columns. Then we give an approximation algorithm of factor m (where m + 1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove that the problem is W[1]-hard when parameterized by the cost-bound, by l, and by the size of the alphabet. Then we prove that the problem admits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters.

TCS Journal 2012 Journal Article

A distance between populations for one-point crossover in genetic algorithms

• Luca Manzoni
• Leonardo Vanneschi
• Giancarlo Mauri

Genetic algorithms use transformation operators on the genotypic structures of the individuals to carry out a search. These operators define a neighborhood. To analyze various dynamics of the search process, it is often useful to define a distance in this space. In fact, using an operator-based distance can make the analysis more accurate and reliable than using distances which have no relationship with the genetic operators. In this paper we define a distance which is based on the standard one-point crossover. Given that the population strongly affects the neighborhood induced by the crossover, we first define a crossover-based distance between populations. Successively, we show that it is naturally possible to derive from this function a family of distances between individuals. Finally, we also introduce an algorithm to compute this distance efficiently.

TCS Journal 2012 Journal Article

A study of the neutrality of Boolean function landscapes in genetic programming

• Leonardo Vanneschi
• Yuri Pirola
• Giancarlo Mauri
• Marco Tomassini
• Philippe Collard
• Sébastien Verel

The neutrality of genetic programming Boolean function landscapes is investigated in this paper. Compared with some well-known contributions on the same issue, (i) we first define new measures which help in characterizing neutral landscapes; (ii) we use a new sampling methodology, which captures features that are disregarded by uniform random sampling; (iii) we introduce new genetic operators to define the neighborhood of tree structures; and (iv) we compare the fitness landscape induced by different sets of functional operators. This study indicates the existence of a relationship between our neutrality measures and the performance of genetic programming for the problems studied.

TCS Journal 2012 Journal Article

An excursion in reaction systems: From computer science to biology

• Luca Corolli
• Carlo Maj
• Fabrizio Marini
• Daniela Besozzi
• Giancarlo Mauri

Reaction systems are a formal model based on the regulation mechanisms of facilitation and inhibition between biochemical reactions, which underlie the functioning of living cells. The aim of this paper is to explore the expressive power of reaction systems as a modeling framework, showing how their basic assumptions and properties can be exploited to formalize computer science and biology oriented problems. In this view, we first provide a reaction-based description of an iterative algorithm to solve the Tower of Hanoi puzzle. Then, we show how the regulation of gene expression in the lac operon, involved in the metabolism of lactose in Escherichia coli cells, can be formalized in terms of reaction systems. Finally, we present a method to derive, given a reaction system with n reactions, a functionally equivalent system with n ′ ≤ n reactions using simplification methods of boolean expressions. Some final remarks and directions for future research conclude the paper.

MFCS Conference 2011 Conference Paper

On the Complexity of the l-diversity Problem

• Riccardo Dondi
• Giancarlo Mauri
• Italo Zoppis

Abstract The problem of publishing personal data without giving up privacy is becoming increasingly important. Different interesting formalizations have been recently proposed in this context, i. e. k-anonymity [17, 18] and l-diversity [12]. These approaches require that the rows in a table are clustered in sets satisfying some constraint, in order to prevent the identification of the individuals the rows belong to. In this paper we focus on the l-diversity problem, where the possible attributes are distinguished in sensible attributes and quasi-identifier attributes. The goal is to partition the set of rows, where for each set C of the partition it is required that the number of rows having a specific value in the sensible attribute is at most \(\frac{1}{l}\) | C |. We investigate the approximation and parameterized complexity of l-diversity. Concerning the approximation complexity, we prove the following results: (1) the problem is not approximable within factor c ln l, for some constant c > 0, even if the input table consists of two columns; (ii) the problem is APX-hard, even if l = 4 and the input table contains exactly 3 columns; (iii) the problem admits an approximation algorithm of factor m (where m + 1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove the following results: (i) the problem is W[1]-hard even if parameterized by the size of the solution, l, and the size of the alphabet; (ii) the problem admits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters.

TCS Journal 2010 Journal Article

Non-confluence in divisionless P systems with active membranes

• Antonio E. Porreca
• Giancarlo Mauri
• Claudio Zandron

We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class NP.

KER Journal 2009 Journal Article

Ontological modeling at a domain interface: bridging clinical and biomolecular knowledge

• Gianluca Colombo
• Daniele Merico
• Zoltán Nagy
• Flavio De Paoli
• Marco Antoniotti
• Giancarlo Mauri

Abstract In this paper, we discuss the challenges posed by the NEUROWEB project, as a case study of ontological modeling at a knowledge interface between neurovascular medicine and genomics. The aim of the project is the development of a support system for association studies. We identify the notion of clinical phenotypes, that is, the pathological condition of a patient, as the central construct of the knowledge model. Clinical phenotypes are assessed through the diagnostic activity, performed by clinical experts operating within communities of practice; the different communities operate according to specific procedures, but they also conform to the minimal requirements of international guidelines, displayed by the adoption of a common standard for the patient classification. We develop a central model for the clinical phenotypes, able to reconcile the different methodologies into a common classificatory system. To bridge neurovascular medicine and genomics, we identify the general theory of biological function as the common ground between the two disciplines; therefore, we decompose the clinical phenotypes into elementary phenotypes with a homogeneous physiological background, and we connect them to the biological processes, acting as the elementary units of the genomic world.

TCS Journal 2005 Journal Article

Algorithms for pattern matching and discovery in RNA secondary structure

• Giancarlo Mauri
• Giulio Pavesi

Text-indexing structures provide significant advantages in the solution of many problems related to string analysis and comparison, and are nowadays widely used in the analysis of biological sequences. In this paper, we present some applications of affix trees to problems of exact and approximate pattern matching and discovery in RNA sequences. By allowing bidirectional search for symmetric patterns in the sequences, affix trees permit to discover and locate in the sequences patterns describing not only sequence regions, but also containing information about the secondary structure that a given region could form, with improvements in terms of theoretical and practical efficiency over the existing methods. The search can be either exact or approximate, where the approximation can be defined simultaneously both for the sequence and the structure of patterns. The approach presented in this paper could provide significant help in the analysis of RNA sequences, where the functional motifs often involve not only sequence, but also the structural constraints.

TCS Journal 2005 Journal Article

Regular splicing languages and subclasses

• Paola Bonizzoni
• Giancarlo Mauri

Recent developments in the theory of finite splicing systems have revealed surprising connections between long-standing notions in the formal language theory and splicing operation. More precisely, the syntactic monoid and Schützenberger constant have strong interaction with the investigation of regular splicing languages. This paper surveys results of structural characterization of classes of regular splicing languages based on the above two notions and discusses basic questions that motivate further investigations in this field. In particular, we improve the result in [6] that provides a structural characterization of reflexive symmetric splicing languages by showing that it can be extended to the class of all reflexive splicing languages: this is the larger class for which a characterization is known.

MFCS Conference 2003 Invited Paper

On the Computational Complexity of Conservative Computing

• Giancarlo Mauri
• Alberto Leporati

Abstract In a seminal paper published in 1982, Fredkin and Toffoli have introduced conservative logic, a mathematical model that allows one to describe computations which reflect some properties of microdynamical laws of Physics, such as reversibility and conservation of the internal energy of the physical system used to perform the computations. In particular, conservativeness is defined as a mathematical property whose goal is to model the conservation of the energy associated to the data which are manipulated during the computation of a logic gate. Extending such notion to generic gates whose input and output lines may assume a finite number d of truth values, we define conservative computations and we show that they naturally induce a new NP–complete decision problem and an associated NP–hard optimization problem. Moreover, we briefly describe the results of five computer experiments performed to study the behavior of some polynomial time heuristics which give approximate solutions to such optimization problem. Since the computational primitive underlying conservative logic is the Fredkin gate, we advocate the study of the computational power of Fredkin circuits, that is circuits composed by Fredkin gates. Accordingly, we give some first basic results about the classes of Boolean functions which can be computed through polynomial–size constant–depth Fredkin circuits.

TCS Journal 2003 Journal Article

On three variants of rewriting P systems

• Claudio Ferretti
• Giancarlo Mauri
• Gheorghe Păun
• Claudio Zandron

We continue here the study of P systems with string objects processed by rewriting rules, by investigating some questions which are classic in formal language theory: leftmost derivation, conditional use of rules (permitting and forbidding conditions), relationships with language families in Chomsky and Lindenmayer hierarchies.

SODA Conference 1999 Conference Paper

Approximation Algorithms for Protein Folding Prediction

• Giancarlo Mauri
• Giulio Pavesi
• Antonio Piccolboni

TCS Journal 1999 Journal Article

Foreword

• Stefania Bandini
• Giancarlo Mauri

TCS Journal 1999 Journal Article

Multilayered cellular automata

• Stefania Bandini
• Giancarlo Mauri

In this paper multilayered cellular automata are formally defined as a generalization of multilayered automata networks. They are hierarchically organized on the basis of nested graphs, and can show different kinds of dynamics, which allow to use them to model, e. g. , complex biological systems comprised of different entities organized in a hierarchical framework. Finally, the simulation of the dynamic regulation of calcium-ion distribution in the subcompartments of a living cell by means of Multilayered Cellular Automata is presented, as an example that allows to show their modeling power.

STOC Conference 1981 Conference Paper

A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines

• Alberto Bertoni
• Giancarlo Mauri
• Nicoletta Sabadini

MFCS Conference 1981 Conference Paper

An Application of the Theory of Free Partially Commutative Monoids: Asymptotic Densities of Trace Languages

• Alberto Bertoni
• Marco Brambilla
• Giancarlo Mauri
• Nicoletta Sabadini

MFCS Conference 1977 Conference Paper

An Algebraic Approach to Problem Solution and Problem Semantics

• Alberto Bertoni
• Giancarlo Mauri
• Mauro Torelli

Abstract The usual approach to the synthesis of algorithms for the solution of problems in combinatorial mathematics consists of two steps. 1 — Description: the problem is embedded in a general structure which is rich enough to permit a mathematical modelling of the problem. 2 — Solution: the problem is solved by means of techniques "as simple as possible", with respect to some given notion of complexity. We give a formalization of this approach in the framework of category theory, which is general enough to get rid of unessential details. In particular such a framework will be provided by the category of ordered complete Σ-algebras, and we will describe the relation between description and solution by means of a variant of so called "Mezei-Wright like results" [10], relating the concept of least fixed point to that of a suitable natural transformation between functors.