Outputs (61)

Simple dynamics on graphs (2016)
Journal Article
Gadouleau, M., & Richard, A. (2016). Simple dynamics on graphs. Theoretical Computer Science, 628, 62-77. https://doi.org/10.1016/j.tcs.2016.03.013

Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f:An→An with G as in... Read More about Simple dynamics on graphs.

Ranks of finite semigroups of one-dimensional cellular automata (2016)
Journal Article
Castillo-Ramirez, A., & Gadouleau, M. (2016). Ranks of finite semigroups of one-dimensional cellular automata. Semigroup Forum, 93(2), 347-362. https://doi.org/10.1007/s00233-016-9783-z

Since first introduced by John von Neumann, the notion of cellular automaton has grown into a key concept in computer science, physics and theoretical biology. In its classical setting, a cellular automaton is a transformation of the set of all confi... Read More about Ranks of finite semigroups of one-dimensional cellular automata.

Fixed points of Boolean networks, guessing graphs, and coding theory (2015)
Journal Article
Gadouleau, M., Richard, A., & Riis, S. (2015). Fixed points of Boolean networks, guessing graphs, and coding theory. SIAM Journal on Discrete Mathematics, 29(4), 2312-2335. https://doi.org/10.1137/140988358

n this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed... Read More about Fixed points of Boolean networks, guessing graphs, and coding theory.

New Constructions and Bounds for Winkler's Hat Game (2015)
Journal Article
Gadouleau, M., & Georgiou, N. (2015). New Constructions and Bounds for Winkler's Hat Game. SIAM Journal on Discrete Mathematics, 29(2), 823-834. https://doi.org/10.1137/130944680

Hat problems have recently become a popular topic in combinatorics and discrete mathematics. These have been shown to be strongly related to coding theory, network coding, and auctions. We consider the following version of the hat game, introduced by... Read More about New Constructions and Bounds for Winkler's Hat Game.

Computing in Matrix Groups Without Memory (2014)
Journal Article
Cameron, P., Fairbairn, B., & Gadouleau, M. (2014). Computing in Matrix Groups Without Memory. Chicago journal of theoretical computer science, 2014(8), 1-16. https://doi.org/10.4086/cjtcs.2014.008

Memoryless computation is a novel means of computing any function of a set of registers by updating one register at a time while using no memory. We aim to emulate how computations are performed on modern cores, since they typically involve updates o... Read More about Computing in Matrix Groups Without Memory.

Computing in Permutation Groups Without Memory (2014)
Journal Article
Cameron, P., Fairbairn, B., & Gadouleau, M. (2014). Computing in Permutation Groups Without Memory. Chicago journal of theoretical computer science, 2014(7), 1-20. https://doi.org/10.4086/cjtcs.2014.007

Memoryless computation is a modern technique to compute any function of a set of registers by updating one register at a time while using no memory. Its aim is to emulate how computations are performed in modern cores, since they typically involve up... Read More about Computing in Permutation Groups Without Memory.

Memoryless computation: New results, constructions, and extensions (2014)
Journal Article
Gadouleau, M., & Riis, S. (2015). Memoryless computation: New results, constructions, and extensions. Theoretical Computer Science, 562, 129-145. https://doi.org/10.1016/j.tcs.2014.09.040

In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs a... Read More about Memoryless computation: New results, constructions, and extensions.

Entropy of Closure Operators and Network Coding Solvability (2014)
Journal Article
Gadouleau, M. (2014). Entropy of Closure Operators and Network Coding Solvability. Entropy, 16(9), 5122-5143. https://doi.org/10.3390/e16095122

The entropy of a closure operator has been recently proposed for the study ofnetwork coding and secret sharing. In this paper, we study closure operators in relation to their entropy. We first introduce four different kinds of rank functions for a gi... Read More about Entropy of Closure Operators and Network Coding Solvability.

Closure Solvability for Network Coding and Secret Sharing (2013)
Journal Article
Gadouleau, M. (2013). Closure Solvability for Network Coding and Secret Sharing. IEEE Transactions on Information Theory, 59(12), 7858-7869. https://doi.org/10.1109/tit.2013.2282293

Network coding is a new technique to transmit data through a network by letting the intermediate nodes combine the packets they receive. Given a network, the network coding solvability problem decides whether all the packets requested by the destinat... Read More about Closure Solvability for Network Coding and Secret Sharing.

Combinatorial Representations (2013)
Journal Article
Cameron, P. J., Gadouleau, M., & Riis, S. (2013). Combinatorial Representations. Journal of Combinatorial Theory, Series A, 120(3), 671-682. https://doi.org/10.1016/j.jcta.2012.12.002

This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any... Read More about Combinatorial Representations.