34 citations · 121 across the 14 of their papers we have counts for
14 papers
Injective and pseudo-injective polynomial equations: From permutations to dynamical systems
Antonio E. Porreca, Marius Rolland
We study the computational complexity of decomposing finite discrete dynamical systems (FDDSs) in terms of the semiring operations of alternative and synchronous execution, which i…
Solving "pseudo-injective" polynomial equations over finite dynamical systems
Antonio E. Porreca, Marius Rolland
We consider the semiring of abstract finite dynamical systems up to isomorphism, with the operations of alternative and synchronous execution. We continue searching for efficient a…
Injectivity of polynomials over finite discrete dynamical systems
Antonio E. Porreca, Marius Rolland
The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviors and, conversely, starting from a desired behavior allows the…
Unconventional complexity classes in unconventional computing (extended abstract)
Antonio E. Porreca
Many unconventional computing models, including some that appear to be quite different from traditional ones such as Turing machines, happen to characterise either the complexity c…
Roots in the semiring of finite deterministic dynamical systems
François Doré, Kévin Perrot, Antonio E. Porreca +2
Finite discrete-time dynamical systems (FDDS) model phenomena that evolve deterministically in discrete time. It is possible to define sum and product operations on these systems (…
Polynomial-delay generation of functional digraphs up to isomorphism
Oscar Defrain, Antonio E. Porreca, Ekaterina Timofeeva
We describe a procedure for the generation of functional digraphs up to isomorphism; these are digraphs with uniform outdegree 1, also called mapping patterns, finite endofunctions…
Decomposition and factorisation of transients in Functional Graphs
François Doré, Enrico Formenti, Antonio E. Porreca +1
Functional graphs (FGs) model the graph structures used to analyse the behaviour of functions from a discrete set to itself. In turn, such functions are used to study real complex…
Profiles of dynamical systems and their algebra
Caroline Gaze-Maillot, Antonio E. Porreca
The commutative semiring of finite, discrete-time dynamical systems was introduced in order to study their (de)composition from an algebraic point of view. However, ma…
The many roads to the simulation of reaction systems
Claudio Ferretti, Alberto Leporati, Luca Manzoni +1
Reaction systems are a computational model inspired by the bio-chemical reactions that happen inside biological cells. They have been and currently are studied for their many nice…
Complexity of the dynamics of reaction systems
Alberto Dennunzio, Enrico Formenti, Luca Manzoni +1
Reaction systems are discrete dynamical systems inspired by bio-chemical processes, whose dynamical behaviour is expressed by set-theoretic operations on finite sets. Reaction syst…
Characterizing PSPACE with shallow non-confluent P systems
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
In P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow…
On the dynamical behaviour of linear higher-order cellular automata and its decidability
Alberto Dennunzio, Enrico Formenti, Luca Manzoni +2
Higher-order cellular automata (HOCA) are a variant of cellular automata (CA) used in many applications (ranging, for instance, from the design of secret sharing schemes to data co…
Solving QSAT in sublinear depth
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
Among -complete problems, QSAT, or quantified SAT, is one of the most used to show that the class of problems solvable in polynomial time by families of a given va…
A Turing machine simulation by P systems without charges
Alberto Leporati, Luca Manzoni, Giancarlo Mauri +2
It is well known that the kind of P systems involved in the definition of the P conjecture is able to solve problems in the complexity class by leveraging the uniformi…