International Journal of Foundations of Computer Science

In this paper we consider a new variant of Networks of Polarized Evolutionary Processors (NPEP) named Generalized Networks of Evolutionary Polarized Processors (GNPEP) and propose them as solvers of combinatorial optimization problems. Unlike the NPEP model, GNPEP uses its numerical evaluation over the processed data from a quantitative perspective, hence this model might be more suitable to solve specific hard problems in a more efficient and economic way. In particular, we propose a GNPEP network to solve a well-known NP-hard problem, namely the $N$-queens. We prove that this GNPEP algorithm requires a linear time in the size of a given instance. This result suggests that the GNPEP model is more suitable to address problems related to combinatorial optimization in which integer restrictions have a relevant role.

The Parikh matrix mapping plays an important role in the study of words through numerical properties. The Parikh $q$-matrix mapping, introduced by Egecioglu and Ibarra (2004) as an extension of the Parikh matrix mapping, maps words to matrices with polynomial entries in $q.$ A word $w$ over an ordered alphabet $\mathrm{\Sigma }$ is said to be $q$-ambiguous if there exists another word $v$ over $\mathrm{\Sigma }$ such that both the words have same Parikh $q$-matrix. Here we derive several properties of $q$-ambiguous words, in particular, for a binary alphabet.

M-rate 0L systems are interactionless Lindenmayer systems together with a function assigning to every string a set of multisets of productions that may be applied simultaneously to the string. Some questions that have been left open in the forerunner papers are examined, and the computational power of deterministic M-rate 0L systems is investigated, where also tabled and extended variants are taken into consideration.

In this paper, we study the behavior (processes) of reaction systems where the context is not arbitrary, but it has its own structure. In particular, we consider a model where the context for a reaction system originates from a network of reaction systems. Such a network is formalized as a graph with reaction systems residing at its nodes, where each reaction system contributes to defining the context of all its neighbors. This paper provides a framework for investigating the behavior of reaction systems receiving contexts from networks of reaction systems, provides a characterisation of their state sequences, and considers different topologies of context networks.

We study how the generative power of networks of evolutionary processors decreases if special codes and ideals are used as input and output filters of the nodes instead of arbitrary regular languages. We show that all recursively enumerable languages can be generated if the filters are right ideals or left ideals. With respect to codes, we obtain a hierarchy of evolutionary language families which is almost identical to that of the families of codes.

This work answers some questions proposed by Bottoni, Labella, and Mitrana (Theoretical Computer Science 682, 2017) regarding the prefix–suffix reduction on words. The operation is defined as a reduction by one half of every square that is present as either a prefix or a suffix of a word, leading thus to a finite set of words associated to the starting one. The iterated case considers consecutive applications of the operations, on all the resulting words. We show that the classes of linear and context-free language are closed under iterated bounded prefix–suffix square reduction, and that for a given word we can determine in ${𝒪}(n^2\mathrm{\text{log}}n)$ time all of its primitive prefix–suffix square roots.

Ant Colony Systems have been widely employed in optimization issues primarily focused on path finding optimization, such as Traveling Salesman Problem. The main advantage lies in the choice of the edge to be explored, defined using the idea of pheromone. This article proposes the use of Ant Colony Systems to explore a Backus-Naur form grammar whose elements are solutions to a given problem. Similar studies, without using Ant Colonies, have been used to solve optimization problems, such as Grammatical Swarm (based on Particle Swarm Optimization) and Grammatical Evolution (based on Genetic Algorithms). Proposed algorithm opens the way to a new branch of research in Swarm Intelligence, which until now has been almost non-existent, using ant colony algorithms to solve problems described by a grammar.

We investigate the spiking neural P systems with communication on request (SNQ P systems) that are devices in the area of neural like P systems abstracting the way in which neurons work and process information. Here we discuss the SNQ P systems using the rule application strategy as defined by Linqiang Pan and collaborators and we are able to improve their result of universality of such systems using two types of spikes. In the current work, we prove that only one type of spikes is sufficient for reaching the computational power of Turing Machines for these devices, bringing closer to implementation such a device. The result holds both in maximum parallel manner application of the rules as well as the maximum-sequentiality application of rules.

In this paper, we investigate the compensation loops, a DNA rearrangement in chromosomes due to unequal crossing over. We study the effect of compensation loops over the gene duplication, and we formalize it as a restricted case of gene duplication in general. We study this biological process under the point of view of formal languages, and we provide some results about the languages defined in this way.

The output of an association rule miner is often huge in practice. This is why several concise lossless representations have been proposed, such as the “essential” or “representative” rules. A previously known algorithm for mining representative rules relies on an incorrect mathematical claim, and can be seen to miss part of its intended output; in previous work, two of the authors of the present paper have offered a complete but, often, somewhat slower alternative. Here, we extend this alternative to the case of closure-based redundancy. The empirical validation shows that, in this way, we can improve on the original time efficiency, without sacrificing completeness.