Author name cluster

Julio Aracena

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2025 Journal Article

Dynamically equivalent disjunctive networks

Julio Aracena
Luis Cabrera-Crot
Adrien Richard
Lilian Salinas

The study of the dynamical behavior of Boolean networks with different update schedules has so far focused primarily on the possible dynamics and equivalent networks that can be obtained. However, few studies have been done about which networks can be obtained from another network with a non-parallel schedule. In this article, we define the problem of finding a Boolean network that is dynamically equivalent to another network. For the general case, it is shown that the problem is NP-Hard. However, if the problem is restricted to disjunctive Boolean networks, it can be solved in polynomial time.

Details DOI

I&C Journal 2020 Journal Article

Fixing monotone Boolean networks asynchronously

Julio Aracena
Maximilien Gadouleau
Adrien Richard
Lilian Salinas

The asynchronous automaton associated with a Boolean network f: { 0, 1 } n → { 0, 1 } n is considered in many applications. It is the finite deterministic automaton with set of states { 0, 1 } n, alphabet { 1, …, n }, where the action of letter i on a state x consists in switching the ith component if f i ( x ) ≠ x i or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f. In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix monotone networks. We prove that there exists a monotone network f with n components such that any word fixing f has length Ω ( n 2 ). Conversely, we construct a word of length O ( n 3 ) that fixes all monotone networks with n components. Secondly, we refine and extend our results to different classes of networks.

Details DOI

TCS Journal 2004 Journal Article

On limit cycles of monotone functions with symmetric connection graph

Julio Aracena
Jacques Demongeot
Eric Goles

We study the length of the limit cycles of discrete monotone functions with symmetric connection graph. We construct a family of monotone functions such that the limit cycles are of maximum possible length, which is exponential in the number of variables. Furthermore, we prove for the class of monotone functions with more than two states and connection graph equal to a caterpillar that the length of the limit cycles is at most two. Finally, we give some exclusion results in arbitrary trees.

Details DOI

TCS Journal 2003 Journal Article

Complexity of perceptron recognition for a class of geometric patterns

Julio Aracena
Eric Goles

In this paper, we study the recognition complexity of discrete geometric figures (rectangles, squares, circles, ellipses) on a retina by diameter-limited and order-restricted perceptrons. We construct a diameter-limited recognition perceptron for the family of rectangles, beginning with local configurations, which is different from the one shown by Minsky et al. (Perceptrons: An Introduction to Computational Geometry, extended edition, MIT Press, Cambridge, MA, 1988). In addition, we demonstrate the nonexistence of diameter-limited recognition perceptrons for squares, circles and ellipses. Finally, for squares and ellipses we construct an order-restricted perceptron with constant coefficients, using an original technique which decomposes the characterization of the figures into local and global features.

Details DOI