Skip to main content

Research Repository

Advanced Search

Dr Maximilien Gadouleau's Outputs (37)

Graphs with minimum degree-entropy (2024)
Journal Article
Dong, Y., Gadouleau, M., Wan, P., & Zhang, S. (2024). Graphs with minimum degree-entropy. Information Sciences, 671, 120629. https://doi.org/10.1016/j.ins.2024.120629

We continue studying extremal values of the degree-entropy, which is an information-theoretic measure defined as the Shannon entropy based on the information functional involving vertex degrees. For a graph with a given number of vertices and edges a... Read More about Graphs with minimum degree-entropy.

Factorisation in the semiring of finite dynamical systems (2024)
Journal Article
Naquin, É., & Gadouleau, M. (2024). Factorisation in the semiring of finite dynamical systems. Theoretical Computer Science, 998, Article 114509. https://doi.org/10.1016/j.tcs.2024.114509

Finite dynamical systems (FDSs) are commonly used to model systems with a finite number of states that evolve deterministically and at discrete time steps. Considered up to isomorphism, those correspond to functional graphs. As such, FDSs have a sum... Read More about Factorisation in the semiring of finite dynamical systems.

The MacWilliams Identity for the Skew Rank Metric (2023)
Journal Article
Friedlander, I., Bouganis, A., & Gadouleau, M. (2023). The MacWilliams Identity for the Skew Rank Metric. Advances in Mathematics of Communications, https://doi.org/10.3934/amc.2023045

The weight distribution of an error correcting code is a crucial statistic in determining its performance. One key tool for relating the weight of a code to that of it's dual is the MacWilliams Identity, first developed for the Hamming metric. This i... Read More about The MacWilliams Identity for the Skew Rank Metric.

Graphs with minimum fractional domatic number (2023)
Journal Article
Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly th... Read More about Graphs with minimum fractional domatic number.

Bent functions in the partial spread class generated by linear recurring sequences (2022)
Journal Article
Gadouleau, M., Mariot, L., & Picek, S. (2023). Bent functions in the partial spread class generated by linear recurring sequences. Designs, Codes and Cryptography, 91(1), 63-82. https://doi.org/10.1007/s10623-022-01097-1

We present a construction of partial spread bent functions using subspaces generated by linear recurring sequences (LRS). We first show that the kernels of the linear mappings defined by two LRS have a trivial intersection if and only if their feedba... Read More about Bent functions in the partial spread class generated by linear recurring sequences.

Expansive automata networks (2020)
Journal Article
Bridoux, F., Gadouleau, M., & Theyssier, G. (2020). Expansive automata networks. Theoretical Computer Science, 843, 25-44. https://doi.org/10.1016/j.tcs.2020.06.019

An Automata Network is a map where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its... Read More about Expansive automata networks.

Fixing monotone Boolean networks asynchronously (2020)
Journal Article
Aracena, J., Gadouleau, M., Richard, A., & Salinas, L. (2020). Fixing monotone Boolean networks asynchronously. Information and Computation, 274, Article 104540. https://doi.org/10.1016/j.ic.2020.104540

The asynchronous automaton associated with a Boolean network f : f0; 1gn ! f0; 1gn is considered in many applications. It is the nite deterministic automaton with set of states f0; 1gn, alphabet f1; : : : ; ng, where the action of letter i on a state... Read More about Fixing monotone Boolean networks asynchronously.

Elementary, finite and linear vN-regular cellular automata (2020)
Journal Article
Castillo-Ramirez, A., & Gadouleau, M. (2020). Elementary, finite and linear vN-regular cellular automata. Information and Computation, 274, Article 104533. https://doi.org/10.1016/j.ic.2020.104533

Let G be a group and A a set. A cellular automaton (CA) over AG is von Neumann regular (vN-regular) if there exists a CA over AG such that = , and in such case, is called a weak generalised inverse of . In this paper, we investigate vN-regularity of... Read More about Elementary, finite and linear vN-regular cellular automata.

Complete Simulation of Automata Networks (2019)
Journal Article
Bridoux, F., Castillo-Ramirez, A., & Gadouleau, M. (2020). Complete Simulation of Automata Networks. Journal of Computer and System Sciences, 109, 1-21. https://doi.org/10.1016/j.jcss.2019.12.001

Consider a finite set A and . We study complete simulation of transformations of , also known as automata networks. For , a transformation of is n-complete of size m if it may simulate every transformation of by updating one register at a time. Using... Read More about Complete Simulation of Automata Networks.

On the stability and instability of finite dynamical systems with prescribed interaction graphs (2019)
Journal Article
Gadouleau, M. (2019). On the stability and instability of finite dynamical systems with prescribed interaction graphs. Electronic Journal of Combinatorics, 26(3), Article P3.32

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability... Read More about On the stability and instability of finite dynamical systems with prescribed interaction graphs.

Max-flow min-cut theorems on dispersion and entropy measures for communication networks (2019)
Journal Article
Riis, S., & Gadouleau, M. (2019). Max-flow min-cut theorems on dispersion and entropy measures for communication networks. Information and Computation, 267, 49-73. https://doi.org/10.1016/j.ic.2019.03.004

The paper presents four distinct new ideas and results for communication networks: 1) We show that relay-networks (i.e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, vague... Read More about Max-flow min-cut theorems on dispersion and entropy measures for communication networks.

On the Rank and Periodic Rank of Finite Dynamical Systems (2018)
Journal Article
Gadouleau, M. (2018). On the Rank and Periodic Rank of Finite Dynamical Systems. Electronic Journal of Combinatorics, 25(3), Article #P3.48

A finite dynamical system is a function f:An→An where A is a finite alphabet, used to model a network of interacting entities. The main feature of a finite dynamical system is its interaction graph, which indicates which local functions depend on whi... Read More about On the Rank and Periodic Rank of Finite Dynamical Systems.

Finite Dynamical Systems, Hat Games, and Coding Theory (2018)
Journal Article
Gadouleau, M. (2018). Finite Dynamical Systems, Hat Games, and Coding Theory. SIAM Journal on Discrete Mathematics, 32(3), 1922-1945. https://doi.org/10.1137/15m1044758

The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this... Read More about Finite Dynamical Systems, Hat Games, and Coding Theory.

On the possible values of the entropy of undirected graphs (2017)
Journal Article
Gadouleau, M. (2018). On the possible values of the entropy of undirected graphs. Journal of Graph Theory, 88(2), 302-311. https://doi.org/10.1002/jgt.22213

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contain... Read More about On the possible values of the entropy of undirected graphs.

Chains of subsemigroups (2017)
Journal Article
Cameron, P. J., Gadouleau, M., Mitchell, J. D., & Peresse, Y. (2017). Chains of subsemigroups. Israel Journal of Mathematics, 220(1), 479-508. https://doi.org/10.1007/s11856-017-1523-x

We investigate the maximum length of a chain of subsemigroups in various classes of semigroups, such as the full transformation semigroups, the general linear semigroups, and the semigroups of order-preserving transformations of finite chains. In som... Read More about Chains of subsemigroups.

Lengths of words in transformation semigroups generated by digraphs (2016)
Journal Article
Cameron, P. J., Castillo-Ramirez, A., Gadouleau, M., & Mitchell, J. D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics, 45(1), 149-170. https://doi.org/10.1007/s10801-016-0703-9

Given a simple digraph D on n vertices (with n≥2n≥2 ), there is a natural construction of a semigroup of transformations ⟨D⟩⟨D⟩ . For any edge (a, b) of D, let a→ba→b be the idempotent of rank n−1n−1 mapping a to b and fixing all vertices other than... Read More about Lengths of words in transformation semigroups generated by digraphs.

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability (2016)
Journal Article
Gadouleau, M., Richard, A., & Fanchon, E. (2016). Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability. IEEE Transactions on Information Theory, 62(5), 2504-2519. https://doi.org/10.1109/tit.2016.2544344

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destination... Read More about Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability.

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 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.

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.

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.

Remoteness of permutation codes (2012)
Journal Article
Cameron, P. J., & Gadouleau, M. (2012). Remoteness of permutation codes. European Journal of Combinatorics, 33(6), 1273-1285. https://doi.org/10.1016/j.ejc.2012.03.027

In this paper, we introduce a new parameter of a code, referred to as the remoteness, which can be viewed as a dual to the covering radius. Indeed, the remoteness is the minimum radius needed for a single ball to cover all codewords. After giving som... Read More about Remoteness of permutation codes.

Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control (2012)
Journal Article
Chen, N., Yan, Z., Gadouleau, M., Wang, Y., & Suter, B. W. (2012). Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 20(2), 296-309. https://doi.org/10.1109/tvlsi.2010.2096239

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of networ... Read More about Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control.

Constant-Rank Codes and Their Connection to Constant-Dimension Codes (2010)
Journal Article
Gadouleau, M., & Yan, Z. (2010). Constant-Rank Codes and Their Connection to Constant-Dimension Codes. IEEE Transactions on Information Theory, 56(7), 3207-3216. https://doi.org/10.1109/tit.2010.2048447

Constant-dimension codes have recently received attention due to their significance to error control in noncoherent random linear network coding. What the maximal cardinality of any constant-dimension code with finite dimension and minimum distance i... Read More about Constant-Rank Codes and Their Connection to Constant-Dimension Codes.

MacWilliams Identity for Codes with the Rank Metric (2008)
Journal Article
Gadouleau, M., & Yan, Z. (2008). MacWilliams Identity for Codes with the Rank Metric. EURASIP Journal on Wireless Communications and Networking, 2008, Article 754021. https://doi.org/10.1155/2008/754021

The MacWilliams identity, which relates the weight distribution of a code to the weight distribution of its dual code, is useful in determining the weight distribution of codes. In this paper, we derive the MacWilliams identity for linear codes with... Read More about MacWilliams Identity for Codes with the Rank Metric.