The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We consider the problem of learning equilibria in a well known game theoretic traffic model due to Wardrop. We consider a distributed learning algorithm that we prove to converge to equilibria. The proof of convergence is based on a differential equation governing the global macroscopic evolution of the system, inferred from the local microscopic evolutions of agents. We prove that the differential...
In this paper we will try to understand how oracles and advice functions, which are mathematical abstractions in the theory of computability and complexity, can be seen as physical measurements in Classical Physics. First, we consider how physical measurements are a natural external source of information to an algorithmic computation, using a simple and engaging case study, namely: Hoyle’s algorithm...
Usual process algebras are working with one-to-one interactions, and so it is difficult to use them in order to describe complex biological systems like gene regulation where many-to-many interactions are involved. We overcome this limitation and present a stochastic fusion calculus suitable to describe the dynamic behaviour involving many-to-many interactions. We extend the semantics of the fusion...
P-systems represent an important class of biologically inspired computational models. In this paper, we study computational properties of a variation of P-systems with rules that model in an abstract way fusion and clonation of membranes. We focus our attention on extended P-systems with an interleaving semantics and symbol objects and we investigate decision problems like reachability of a configuration,...
Dynamical systems allow to modelize various phenomena or processes by only describing their way of evolution. It is an important matter to study the global and the limit behaviour of such systems. A possible description of this limit behaviour is via the omega-limit set: the set of points that can be limit of subtrajectories. The omega-limit set is in general uncomputable. It can be a set highly difficult...
In this paper, we study concentration controlled P systems having catalysts, bi-stable catalysts and mobile catalysts. We show that computational universality can be obtained for pure catalytic P systems using 2 bi-stable catalysts and 1 membrane, improving the known universality result [2]. We also give universality results using catalysts, and mobile catalysts. Further, we identify some subclasses...
The unit cost model is both convenient and largely realistic for describing integer decision algorithms over + ,×. Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such non-arithmetic primitives by presenting and analyzing...
Self-assembly has been immensely successful in creating complex patterns at the molecular scale. However, the use of self-assembly techniques at the macroscopic level has so far been limited to the formation of simple patterns. For example, in a number of prior works, self-assembling units or tiles formed aggregates based on the polarity of magnetic pads on their sides. The complexity of the resulting...
The notion of conceptual structure in CA rules that perform the density classification task (DCT) was introduced by [1]. Here we investigate the role of process-symmetry in CAs that solve the DCT, in particular the idea of conceptual similarity, which defines a novel search space for CA rules. We report on two new process-symmetric one-dimensional rules for the DCT which have the highest “balanced”...
We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems. Like circuits, membrane systems are defined as uniform families. To date, polynomial time uniformity has been the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC0 and L-uniformities and investigate the computational power...
Security in sensor networks, though an important issue for widely available wireless networks, has been studied less extensively than other properties of these networks, such as, for example, their reliability. The few security schemes proposed so far are based on classical cryptography. In contrast, the present paper develops a totally new security solution, based on quantum cryptography. The scheme...
It is shown that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in polynomial...
The theme of this paper is computation in Winfree’s Abstract Tile Assembly Model (TAM). We first review a simple, well-known tile assembly system (the “wedge construction”) that is capable of universal computation. We then extend the wedge construction to prove the following result: if a set of natural numbers is decidable, then it and its complement’s canonical two-dimensional representation self-assemble...
We consider several kinds of non-finitary computation, using ordinary Turing machines, as usual, as the reference case. The main problem which this short paper tries to address, is the problem of defining the output, or final message, of a machine which has run for a countably infinite number of steps. A modest scheme, using non-standard numbers, is proposed.
The design of fast arithmetic logic circuits is an important research topic for reversible and quantum computing. A special challenge in this setting is the computation of standard arithmetical functions without the generation of garbage. The CDKM-adder is a recent garbage-less reversible (quantum) ripple-carry adder. We optimize this design with a novel parallelization scheme wherein m parallel k...
Inspired by P systems initiated by Gheorghe Pãun, we study a computation model over a multiset of communicating objects. The objects in our model are instances of finite automata. They interact with each other by firing external transitions between two objects. Our model, called service automata, is intended to specify, at a high level, a service provided on top of network devices abstracted as communicating...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.