6 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…
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 (…
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…
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…