Selected publications

Where available, a link to the paper and/or a preprint is provided.

Doctoral thesis

Articles in refereed journals

  1. Silvio Capobianco. (2025) Not just the Garden of Eden: Additional takes on cellular automata surjectivity. To appear on Theoretical Computer Science.
    Pre-publication: doi:10.1016/j.tcs.115217
  2. Silvio Capobianco. (2022) Fekete's lemma for componentwise subadditive functions of two or more real variables. Acta et Commentationes de Mathematica Universitatis Tartuensis 26(1), 45--62.
    Paper: doi:10.12697/ACUTM.2022.26.04
    Preprint: arXiv:1904.10507
  3. Silvio Capobianco and Pierre Guillon. Besicovitch pseudodistances with respect to non-Følner sequences. Complex Systems 30(2), 2021, pp. 133--158.
    Paper: doi:10.25088/ComplexSystems.30.2.133
    Preprint: hal.archives-ouvertes.fr/hal-02566187/
  4. Silvio Capobianco, Jarkko Kari, and Siamak Taati. (2017) Post-surjectivity and balancedness of cellular automata over groups. Discrete Mathematics and Theoretical Computer Science 19:3.
    Paper: dmtcs:3918
  5. Silvio Capobianco, Pierre Guillon, and Jarkko Kari. (2013) Surjective cellular automata far from the Garden of Eden. Discrete Mathematics and Theoretical Computer Science 15:3, 41--60.
    Paper: dmtcs:618
  6. Silvio Capobianco, Tommaso Toffoli. (2012) Conserved quantities in discrete dynamics: what can be recovered from Noether's theorem, how, and why? Natural Computing 11(4), 565--577.
    Paper: doi:10.1007/s11047-012-9336-7
  7. Silvio Capobianco. (2011) Generalized Besicovitch and Weyl spaces: Topology, patterns and sliding block codes. Theoretical Computer Science 412, 3822--3837.
    Paper: doi:10.1016/j.tcs.2011.02.020
  8. Silvio Capobianco, Tommaso Toffoli. (2010) Dissipative CA Computation Without Power Sources? Journal of Cellular Automata 5(3), 169--183.
    Paper: http://www.oldcitypublishing.com/JCA/JCAcontents/JCAv5n3contents.html
  9. Silvio Capobianco. (2009) On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems. Information and Computation 207(11), 1169--1180.
    Paper: doi:10.1016/j.ic.2009.02.006
  10. Silvio Capobianco. (2009) Surjunctivity for cellular automata in Besicovitch spaces. Journal of Cellular Automata 4(2), 89--98.
    Paper: http://www.oldcitypublishing.com/JCA/JCAcontents/JCAv4n2contents.html
    Preprint: arXiv:0705.0670v3 [math.DS]
  11. Silvio Capobianco. (2008) Multidimensional cellular automata and generalization of Fekete's lemma. Discrete Mathematics and Theoretical Computer Science 10:3, 95--104.
    Paper: dmtcs:442
  12. Luca Aceto, Silvio Capobianco, Anna Ingólfsdóttir, Bas Luttik. (2008) The equational theory of prebisimilarity over basic CCS with divergence. Information Processing Letters 108, 284--289.
    Paper: doi:10.1016/j.ipl.2008.05.019
  13. Tommaso Toffoli, Silvio Capobianco, Patrizia Mentrasti. (2008) When---and how---can a cellular automaton be rewritten as a lattice gas? Theoretical Computer Science 403, 71--88.
    Paper: doi:10.1016/j.tcs.2008.04.047
  14. Luca Aceto, Silvio Capobianco, Anna Ingólfsdóttir. (2008) On the Existence of a Finite Base for Complete Trace Equivalence over BPA with Interrupt. Bulletin of the EATCS 95, 220--240.
    Paper: (whole issue, 1.5 Mb) http://www.eatcs.org/images/bulletin/beatcs95.pdf
  15. Silvio Capobianco. (2006) Cellular automata over semi-direct product groups: reduction and invertibility results. International Journal of Algebra and Computation 16, 1071--1085.
  16. Tommaso Toffoli, Silvio Capobianco, Patrizia Mentrasti. (2004) How to turn a second-order cellular automaton into a lattice gas: a new inversion scheme. Theoretical Computer Science 325, 329--344.
    Paper: doi:10.1016/j.tcs.2004.06.012

Articles in refereed conferences

  1. Silvio Capobianco and Tarmo Uustalu. (2023) Additive cellular automata graded-monadically. In Santiago Escobar (ed.), PPDP '23: Proceedings of the 25th International Symposium on Principles and Practice of Declarative Programming. October 22-23, Cascais, Lisbon, Portugal, 13:1-13:9.
  2. Silvio Capobianco, Pierre Guillon, and Camille Noûs. (2020) A characterization of amenable groups with Besicovitch pseudodistances. In H. Zenil (Ed.) AUTOMATA 2020, Lecture Notes in Computer Science 12286, 99--110.
    doi:10.1007/978-3-030-61588-8_8
  3. Silvio Capobianco, Jarkko Kari, and Siamak Taati. (2016) An "almost dual" to Gottschalk's conjecture. In Matthew Cook and Turlough Neary (eds.), 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings. Lecture notes in Computer Science 9664, 77--89.
    Paper: doi:/10.1007/978-3-319-39300-1
  4. Silvio Capobianco, Jarkko Kari, and Siamak Taati. (2015) Post-surjectivity and balancedness of cellular automata over groups. In J. Kari et al., 21st International Workshop on Cellular Automata and Discrete Complex Systems, Exploratory Papers of AUTOMATA 2015, 31--38.
    Short paper: capobianco-kari-taati-automata2015-short.pdf
  5. Silvio Capobianco, Pierre Guillon, and Jarkko Kari. (2011) Garden-of-Eden-like theorems for amenable groups. In N. Fatès et al., Procs. of Automata 2011, November 21--23, 2011, 233--242.
    Short paper: capobianco-guillon-kari-automata2011-short.pdf
  6. Silvio Capobianco, Tommaso Toffoli. (2011) Can anything from Noether's theorem be salvaged for discrete dynamical systems? In C. Calude et al. (eds.), Procs. of UC2011 Unconventional Computation 2011 conference, Lecture Notes in Computer Science 6714, 77--88.
    Paper: doi:10.1007/978-3-642-21341-0_13
    Preprint: arXiv:1103.4785 [nlin.CG]
  7. Silvio Capobianco, Tarmo Uustalu. (2010) A Categorical Outlook on Cellular Automata. In Jarkko Kari (Ed.): Proceedings of the 2nd Symposium on Cellular Automata, JAC 2010, Turku, Finland, December 15-17, 2010. Pages 88--99.
    Paper: http://hal.archives-ouvertes.fr/hal-00542015/en/
  8. Silvio Capobianco. (2010) On Pattern Density and Sliding Block Code Behavior for the Besicovitch and Weyl Pseudo-distances. In Jan van Leeuwen et al. (Eds.): SOFSEM 2010, Lecture Notes in Computer Science 5901, 259--270.
    Paper: doi:10.1007/978-3-642-11266-9_22
  9. Silvio Capobianco. (2009) Some notes on Besicovitch and Weyl distances over higher-dimensional configurations. In Pedro P.B. de Oliveira & Jarkko Kari, editors. Proceedings of Automata 2009: 15th International Workshop on Cellular Automata and Discrete Complex Systems, Universidade Presbiteriana Mackenzie, São Paulo, SP, Brazil, 2009. Short papers section, pp. 300--308.
    Short paper: capobianco-automata2009-short.pdf
  10. Silvio Capobianco. (2008) Induced Subshifts and Cellular Automata. In C. Martín-Vide, F. Otto, and H. Fernau (eds.), "Languages and Automata Theory and Applications. Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers." Lecture Notes in Computer Science 5196, 160--171.
    Paper: doi:10.1007/978-3-540-88282-4_16

Conference abstracts

  1. Silvio Capobianco and Niccolò Veltri. (2015) An implementation in Agda of Sutner’s decision algorithms for injectivity and surjectivity of one-dimensional cellular automata. 27th Nordic Workshop on Programming Theory (NWPT 2015), 21-23 October 2015, Reykjavik University, Iceland, Abstracts.
  2. Silvio Capobianco. (2014) The Banach-Tarski paradox and the Garden-of-Eden theorem. FINEST MATH 2014: Fourth Finnish-Estonian Mathematics Colloquium & Finnish Mathematical Days 2014, Book of Abstracts, University of Helsinki, 9-10 January 2014.
Back to home page
Last update: 8 April 2025

Valid HTML 4.01 Transitional