Article
Computer Science, Theory & Methods
David Orellana-Martin, Luis Valencia-Cabrera, Mario J. Perez-Jimenez
Summary: Since the creation of Membrane Computing field in 1998, several research lines have been opened focusing on theoretical questions and applications in various fields. The study investigates the computational power of P systems and their applications in biology, ecology, economy, robotics, and fault diagnosis. Techniques in computability theory and computational complexity theory are explained in this work.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Theory & Methods
Bosheng Song, Kenli Li, David Orellana-Martin, Mario J. Perez-Jimenez, Ignacio Perez-Hurtado
Summary: Nature-inspired computing, specifically membrane computing, is based on paradigms, mechanisms, and principles of natural systems. This bio-inspired computing paradigm is motivated by the internal membrane function and structure of biological cells. The state-of-the-art computability theory and computational complexity theory are presented, along with applications and open problems of P systems.
ACM COMPUTING SURVEYS
(2021)
Article
Computer Science, Information Systems
Shanchen Pang, Tong Ding, XiaoBing Mao, Neal N. Xiong
Summary: This study presents a new model of P system called conditional enzymatic numerical P system (DENPS), which introduces a series of decisional enzymes and rebuilds the cell structures to achieve a more flexible decision-making mechanism. The validation experiments demonstrate that DENPS is logical and efficient in processing large-scale decision tasks, with prior results being achieved 188.28 times faster and decision tree based on DENPS being 119.85 times faster than the general serial framework.
INFORMATION SCIENCES
(2021)
Article
Computer Science, Theory & Methods
David Orellana-Martin, Luis Valencia-Cabrera, Mario J. Perez-Jimenez
Summary: P systems are computing devices based on sets of rules to efficiently solve NP-complete problems. This work improves a previous result and provides an efficient solution for solving QBF-SAT or QSAT problems.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Mathematics
David Orellana-Martin, Antonio Ramirez-de-Arellano, Jose Antonio Andreu-Guzman, Alvaro Romero-Jimenez, Mario J. Perez-Jimenez
Summary: This paper discusses the class R of recognizer membrane systems that can provide polynomial-time and uniform solutions for NP-complete problems, defining it as an efficient class. By representing R as a class of efficient recognizer cell-like P systems with object evolution rules, communication rules, and dissolution rules, the polynomial-time complexity class PMCR is obtained, encompassing both the NP and co-NP classes. The DP class, which includes languages that can be expressed as the difference between any two languages in NP, is considered as a more complex class than the NP class and serves as promising candidates for studying the P vs NP problem. This paper extends previous results to include any class R of efficient recognizer tissue-like membrane systems and presents a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems.
Article
Computer Science, Artificial Intelligence
Linqiang Pan, Bosheng Song, Claudio Zandron
Summary: Tissue P systems with evolutional symport/antiport rules can solve problems beyond NP, including all problems in the complexity class PP for deterministic systems and all problems in the class PSPACE for non-deterministic systems.
KNOWLEDGE-BASED SYSTEMS
(2023)
Article
Quantum Science & Technology
Hannes Leipold, Federico M. Spedalieri
Summary: Recent advances in adiabatic quantum computing and quantum annealing have focused on using advanced and novel Hamiltonian representations to solve optimization problems. A significant advancement has been the development of driver Hamiltonians that can commute with the constraints of an optimization problem, providing an alternative method for satisfying those constraints. However, the design of successful driver Hamiltonians for multiple constraints currently relies on specific problem intuition and there is no simple general algorithm for generating them.
QUANTUM SCIENCE AND TECHNOLOGY
(2022)
Article
Computer Science, Information Systems
Pedro Garcia-Victoria, Matteo Cavaliere, Miguel A. Gutierrez-Naranjo, Miguel Cardenas-Montes
Summary: This paper explores the spreading of strategies in populations using Evolutionary Game Theory and membrane computing. It proposes a novel approach that combines these two fields to study the spreading of behaviors in structured populations. The approach not only expands research in membrane systems, population, and ecological dynamics, but also presents a bioinspired framework based on formal languages theory to investigate the dynamics of evolving structured populations.
INFORMATION SCIENCES
(2022)
Article
Mathematics, Applied
David Orellana-Martin, Luis Valencia-Cabrera, Mario J. Perez-Jimenez
Summary: A widely studied field in membrane computing is computational complexity theory, where adding syntactic or semantic ingredients to membrane systems can improve their problem-solving efficiency. This study successfully solved the SAT problem using evolutional symport/antiport rules and passive environmental participation in recognizer P systems.
Article
Computer Science, Theory & Methods
Leqi Zhu
Summary: In the consensus problem, protocols must ensure that all processes output the same value, which is the input value of one of the processes. Protocols with progress guarantees must use at least n-1 registers.
SIAM JOURNAL ON COMPUTING
(2021)
Article
Computer Science, Theory & Methods
David Orellana-Martin, Luis Valencia-Cabrera, Mario J. Perez-Jimenez
Summary: P systems are computational models where the environment plays a passive role and later tissue P systems were introduced allowing communication between cells and the environment. A special alphabet represents the chemical elements and their interaction with cells. The behavior of this alphabet can be simulated by evolutionary communication rules and/or division/separation rules, maintaining efficiency even if the environment is not active.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Engineering, Chemical
Alberto Arteta Albert, Ernesto Diaz-Flores, Luis Fernando de Mingo Lopez, Nuria Gomez Blas
Summary: Intractable problems in Computer Science have led researchers to explore alternative computing models such as Quantum Computing and cell computing, as traditional computers face limitations in dealing with complex problems and large input data. This proposal introduces an in vivo framework inspired by membrane computing and aims to enhance the performance of applications by accelerating the information processing speed and possibly achieving results that are currently impossible with conventional architectures.
Article
Computer Science, Hardware & Architecture
Vajiheh Farhadi, Fidan Mehmeti, Ting He, Thomas F. La Porta, Hana Khamfroush, Shiqiang Wang, Kevin S. Chan, Konstantinos Poularakis
Summary: Mobile edge computing enables wireless users to utilize cloud computing with reduced communication delay. This paper proposes a two-time-scale framework to jointly optimize service placement and request scheduling, while considering various constraints. Developed polynomial-time algorithms achieve near-optimal performance in extensive simulations.
IEEE-ACM TRANSACTIONS ON NETWORKING
(2021)
Article
Computer Science, Information Systems
Nicholas Woolsey, Xingyue Wang, Rong-Rong Chen, Mingyue Ji
Summary: We propose a flexible low complexity design (FLCD) of coded distributed computing (CDC) and evaluate it empirically on Amazon EC2. FLCD utilizes the design freedom to define map and reduce functions and develop asymptotic homogeneous systems for varying IV sizes under a general MapReduce framework. Compared to existing designs, FLCD offers greater flexibility and significantly reduces implementation complexity. This is the first low-complexity CDC design that can operate on a network with an arbitrary number of nodes and computation load. Empirical evaluations demonstrate its speedup compared to conventional MapReduce, reduction in total time, and wider operating network parameters compared to existing CDC schemes.
IEEE TRANSACTIONS ON CLOUD COMPUTING
(2023)
Article
Computer Science, Information Systems
Arash Yazdanialahabadi, Masoud Ardakani
Summary: In this work, a multilayer coding strategy is proposed to allow some helpers to assist with decoding in distributed computing, solving the straggling issue. By decoding at different layers, it simplifies the decoding burden on the master node and minimizes the overall completion time.
IEEE INTERNET OF THINGS JOURNAL
(2021)
Article
Computer Science, Hardware & Architecture
Leonardo Rundo, Andrea Tangherloni, Paolo Cazzaniga, Matteo Mistri, Simone Galimberti, Ramona Woitek, Evis Sala, Giancarlo Mauri, Marco S. Nobile
Summary: Image texture extraction and analysis are crucial in computer vision, especially in the biomedical field where quantitative imaging methods play a significant role in predicting, prognosing, and evaluating treatment responses. CHASM, an accelerated method on GPUs, shows great potential in achieving significant speed-up factors compared to traditional sequential versions, highlighting the importance of GPUs in clinical research.
JOURNAL OF SUPERCOMPUTING
(2021)
Article
Computer Science, Theory & Methods
Riccardo Dondi, Giancarlo Mauri, Italo Zoppis
Summary: This paper investigates the problem of matching a query string to a directed graph, with edit operations allowed on both the graph labels and the query string. The complexity of approximate matching problem is analyzed, showing that deciding the existence of a path in the graph representing a query string with edit operations on vertex labels is an NP-complete problem. The fixed-parameter tractability of this problem is also discussed when parameterized by the length of the input string. The paper further explores the variants of approximate string matching and provides inapproximability results.
INFORMATION AND COMPUTATION
(2022)
Article
Biochemical Research Methods
Andrea Tangherloni, Marco S. Nobile, Paolo Cazzaniga, Giulia Capitoli, Simone Spolaor, Leonardo Rundo, Giancarlo Mauri, Daniela Besozzi
Summary: Mathematical models of biochemical networks are crucial for understanding cellular processes, but the computational demands for large-scale models may exceed the capabilities of traditional CPUs. Using GPUs for acceleration can be an effective solution to overcome these limitations and improve computational efficiency in Systems Biology.
PLOS COMPUTATIONAL BIOLOGY
(2021)
Article
Medicine, General & Internal
Leonardo Rundo, Roberta Eufrasia Ledda, Christian di Noia, Evis Sala, Giancarlo Mauri, Gianluca Milanese, Nicola Sverzellati, Giovanni Apolone, Maria Carla Gilardi, Maria Cristina Messa, Isabella Castiglioni, Ugo Pastorino
Summary: The research demonstrates the significant potential of LDCT-based radiomics in evaluating the characteristics of PN and optimizing screening recall intervals, including automatic classification of PN types and predicting malignant probabilities. The classifier's performance on the blinded test dataset has verified significant progress in improving early detection rates of lung cancer.
Article
Medical Informatics
Rosy Tsopra, Xose Fernandez, Claudio Luchinat, Lilia Alberghina, Hans Lehrach, Marco Vanoni, Felix Dreher, O. Ugur Sezerman, Marc Cuggia, Marie de Tayrac, Edvins Miklasevics, Lucian Mihai Itu, Marius Geanta, Lesley Ogilvie, Florence Godey, Cristian Nicolae Boldisor, Boris Campillo-Gimenez, Cosmina Cioroboiu, Costin Florian Ciusdel, Simona Coman, Oliver Hijano Cubelos, Alina Itu, Bodo Lange, Matthieu Le Gallo, Alexandra Lespagnol, Giancarlo Mauri, H. Okan Soykam, Bastien Rance, Paola Turano, Leonardo Tenori, Alessia Vignoli, Christoph Wierling, Nora Benhabiles, Anita Burgun
Summary: AI technologies have the potential to revolutionize healthcare systems, but their implementation is limited due to a lack of reliable validation procedures. The European ITFoC consortium has designed a framework for the clinical validation of AI technologies for predicting treatment response in oncology, based on seven key steps including intended use, target population, evaluation timing, datasets, data safety, performance metrics, and explainability. This framework forms the basis of a validation platform for assessing and comparing AI algorithms for predicting treatment response in triple-negative breast cancer with real-world data.
BMC MEDICAL INFORMATICS AND DECISION MAKING
(2021)
Article
Computer Science, Theory & Methods
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Claudio Zandron
Summary: The paper investigates the computational power of polarizationless P systems with active membranes and the impact of membrane hierarchy depth. It shows that P systems with a membrane hierarchy depth of 2 can solve all decision problems in the complexity class P-parallel to(NP).
THEORETICAL COMPUTER SCIENCE
(2022)
Editorial Material
Computer Science, Artificial Intelligence
Tomasz Gwizdalla, Luca Manzoni, Giancarlo Mauri
Article
Computer Science, Artificial Intelligence
Alberto Leporati, Giancarlo Mauri, Claudio Zandron
Summary: This paper presents the main ideas and interesting variants of spiking neural P systems inspired by the neuro-physiological behavior of biological neurons. It discusses the computational power and efficiency in solving hard problems under different assumptions for information encoding, rules, and system parameters.
Article
Computer Science, Artificial Intelligence
Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Gloria Pietropolli, Claudio Zandron
Summary: Inferring the structure and operation of a computing model from its behavior is a challenging task. This paper proposes a constrained version of this problem and applies an evolutionary algorithm to find an individual that approximates the original model. The results show that the proposed approach is promising for the automatic synthesis of P systems.
SWARM AND EVOLUTIONARY COMPUTATION
(2023)
Editorial Material
Computer Science, Artificial Intelligence
Stefania Bandini, Bastien Chopard, Giancarlo Mauri
Article
Computer Science, Theory & Methods
Artiom Alhazov, Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Claudio Zandron
Summary: This paper discusses the definition of space complexity in P systems with active membranes. It reviews the main results related to solving computationally hard problems and highlights the requirement of different resources in each solution. Possible alternative solutions requiring different resources are also discussed.
JOURNAL OF MEMBRANE COMPUTING
(2022)
Article
Computer Science, Interdisciplinary Applications
Riccardo Dondi, Mohammad Mehdi Hosseinzadeh, Giancarlo Mauri, Italo Zoppis
Summary: The central problem in graph mining is the discovery of dense subgraphs, with a recent focus on finding a set of densest subgraphs. The Top-k-Overlapping Densest Subgraphs problem aims to find a set of k dense subgraphs that may share vertices, with an objective function considering density, parameter lambda, and distance. Research has shown a 1/10-factor approximation algorithm for this problem, while also proving its NP-hardness.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2021)
