Rezumat

We investigate a dynamical complexity measure defined for finite automata with translucent letters (FAwtl). Roughly, this measure counts the minimal number of necessary jumps for such an automaton in order to accept an input. The model considered here is the deterministic finite automaton with translucent letters (DFAwtl). Unlike in the case of the nondeterministic variant, the function describing the jump complexity of any DFAwtl is either bounded by a constant or it is linear. We give a polynomial-time algorithm for deciding whether the jump complexity of a DFAwtl is constant-bounded or linear and we prove that the equivalence problem for DFAwtl of O(1) jump complexity is decidable. We also consider another fundamental problem for extensions of finite automata models, deciding whether the language accepted by a FAwtl is regular. We give a positive partial answer for DFAwtl over the binary alphabet, in contrast with the case of NFAwtl, where the problem is undecidable. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Rezumat

We propose a direct simulation of an arbitrary network of splicing processors by a network of splicing processors having an underlying path graph. This is in line with similar simulations where the target network has other widely used graph topologies: complete graph, lattice graph, star graph, wheel graph, etc. Along with the effective construction, we provide an analysis of the size and time complexity of the obtained network. Our construction may not be the most economic conversion in terms of number of nodes, hence further investigation to find more succinct networks are of (at least) theoretical interest.

Rezumat

Rezumat

Motivated by the need of reducing the huge amount of data navigating simultaneously through a network of polarized splicing processors, we look to the possibility of introducing probabilities which theoretically could decrease this amount, at a price of some loss of certainty. We imagined two possible situations regarding the splicing step: to associate either fixed or dynamically computed probabilities with splicing rules in every node. Similarly to the splicing step, two situations could be considered for the communication step depending on the way the probabilities are associated: statically or dynamically. We believe that this new feature together with the communication protocol based on polarization might facilitate software simulations or hardware implementations. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Rezumat

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n, for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Omega(n) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O(log n) and O(root n) that accept non-regular languages. Several open problems and directions for further developments are finally discussed.

Rezumat

We consider networks whose nodes host splicing processors, that is processors that are able to simulate the DNA recombination by splicing. Several topologies for the underlying graph of these networks are investigated. More precisely, we show that each network of splicing processors with some underlying graph can be directly converted into an equivalent network having an underlying graph of a different topology. Several common topologies are considered: full-mesh, star, grid, and wheel (ring-star). We also investigate the time and size complexity of each of these simulations. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Rezumat

We propose a simulation of an arbitrary network of evolutionary processors by a network having a special underlying graph, namely a wheel (ring-star) graph. This work continues a series of papers devoted to simulations between networks of evolutionary processors with various topologies. Somehow unexpected, the simulation is time complexity preserving at the price of a much larger network.

Rezumat

Networks of splicing processors are one of the theoretical computational models that take inspiration from nature to efficiently solve problems that our current computational knowledge is not able to. One of the issues restricting/hindering is practical implementation is the arbitrariness of the underlying graph, since our computational systems usually conform to a predefined topology. We propose simulations of networks of splicing processors having arbitrary underlying graphs by networks whose underlying graphs are of a predefined topology: complete, star, and grid graphs. We show that all of these simulations are time efficient in the meaning that they preserve the time complexity of the original network: each computational step in that network is simulated by a fixed number of computational steps in the new topologic networks. Moreover, these simulations do not modify the order of magnitude of the network size.

Rezumat

This work is a survey of the main results reported for the degree of extension of two models defining non-regular languages, namely the context-free grammar and the extended automaton over groups. More precisely, we recall the main results regarding the degree on non-regularity of a context-free grammar as well as the degree of extension of finite automata over groups. Finally, we consider a similar measure for the finite automata with translucent letters and present some preliminary results. This measure could be considered for many mechanisms that extend a less expressive one. © V. Mitrana, M. Păun This work is licensed under the Creative Commons Attribution License.

Rezumat

We continue here the theoretical study initiated approximately twenty years ago on the possibility of using living cells for computing. In this paper, we reconsider the formal operations inspired by the intramolecular DNA rearrangements in the evolution of the macronucleus from the micronucleus in a group of ciliates. After introducing the concept of a valid string, we propose an efficient algorithm for checking this property for a given string. Then we investigate which of the considered operations preserve the property of a string to be valid. We also show that just one of the operations can be simulated by a finite transducer. The important problem regarding the order of applying the operations is then investigated showing that one operation can commute with the other two. Finally, we introduce the iterated variants and investigate a few properties. A sort of a normal form for the gene assembly in ciliates is obtained. The paper ends by a short discussion about open problems and further directions of research.