VLDB 2026 Research / reviewers in the wild / expert
Niccolò Castronuovo
dblp:176/8893
· DBLP profile ↗
2ranked-venue papers
1as first author
1since 2021 · last 2026
0000-0002-1054-0161ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 2 · 1 first-author · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | A divide and conquer algorithm for deciding group cellular automata dynamicsabstractWe prove that many dynamical properties of group cellular automata (GCA) can be decided by decomposing them into a set of much simpler GCA, provided those properties are decidable for such simpler GCA. Specifically, we provide a novel algorithmic technique that decomposes the GCA under investigation into a finite number of GCA, some defined on abelian groups, while others, if any, on products of simple non-abelian isomorphic groups. Importantly, the groups resulting from the decomposition depend only on the original group and are therefore completely independent of both the automaton and the considered property. Consequently, they do not inherit any aspect of the complexity of the automaton under investigation. We study the inheritance of the dynamical properties in the original GCA versus the same properties in the GCA obtained through decomposition. The latter turn out to be significantly easier to analyze than in the original GCA. Then, we show that injectivity, surjectivity, and equicontinuity/sensitivity to initial conditions can be decided by testing them in the smaller GCA produced by the decomposition. Moreover, we prove that the topological entropy of a GCA can be computed, provided one knows how to compute it for GCA defined on products of simple non-abelian isomorphic groups – for which we explicitly prove how to compute it in the surjective case – and on abelian groups. Finally, we prove that no strongly transitive, and therefore no positively expansive, GCA defined on non-abelian groups exist. Niccolò Castronuovo, Alberto Dennunzio, Luciano Margara |
J. Comput. Syst. Sci. | 1 |
| 2016 | Some permutations on Dyck words
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, Robert Cori |
Theor. Comput. Sci. | 3 |