Research

Groups:

• Director of GLyC - Logic, Language and Computability Research Group.
• Codirector of the Argentinian-French Laboratory SINFIN Université Paris-CNRS/Universidad de Buenos Aires-CONICET.
• Researcher of QuICC: Quantum Information, Computation, and Communication team.

Research interests:

• Theoretical computer science
• Computability theory
• Algorithmic randomness
• Kolmogorov complexity
• Algorithmic information theory
• Mathematical logic
• Model theory
• Modal logics
• Theory of databases
• Quantum information
• Cognition

Publications

• Diego Figueira, Santiago Figueira and Edwin Pin. PDL on Steroids: on Expressive Extensions of PDL with Intersection and Converse LICS (Logic in Computer Science), 2023.
• Pablo Tano, Sergio Abriola, Sergio Romano, and Santiago Figueira. A logical framework to study concept-learning biases in the presence of multiple explanations. Behavior Research Methods, 2021.
• Ignacio Perito, Guido Bellomo, Daniel Galicer, Santiago Figueira, Augusto J. Roncaglia and Ariel Bendersky. Characterization of non-signaling correlations from mutual information. Physical Review A, 103(6), 2021.
• Samuel Planton, Timo van Kerkoerle, Leïla Abbih and Maxime Maheu, Florent Meyniel, Mariano Sigman, Liping Wang, Santiago Figueira, Sergio Romano, and Stanislas Dehaene. A theory of memory for binary sequences: Evidence for a mental compression algorithm in humans. PLOS Computational Biology 17(1): e1008598, 2021.
• Diego Figueira, Santiago Figueira and Edwin Pin. Finite Controllability for Ontology-Mediated Query Answering of CRPQ. KR (Knowledge Representation and Reasoning), 2020.
• Ignacio Perito, Guido Bellomo, Daniel Galicer, Santiago Figueira, Augusto J. Roncaglia, and Ariel Bendersky. Impossibility of memory in hidden-signaling models for quantum correlations. Physical Review A 102, 052207, 2020.
• Pablo Tano, Sergio Romano, Mariano Sigman, Alejo Salles, and Santiago Figueira. Towards a more flexible language of thought: Bayesian grammar updates after each concept exposure. Physical Review E 101(042128), 2020.
• María Emilia Descotte, Diego Figueira and Santiago Figueira. Closure properties of synchronized relations. STACS (Symposium on Theoretical Aspects of Computer Science), 2019.
• Liping Wang, Marie Amalric, Wen Fang, Xinjian Jiang, Christophe Pallier, Santiago Figueira, Mariano Sigman, and Stanislas Dehaene. Representation of spatial sequences using nested rules in human prefrontal cortex. NeuroImage 186:245-255, 2019.
• Sergio Romano, Alejo Salles, Marie Amalric, Stanislas Dehaene, Mariano Sigman, and Santiago Figueira. Bayesian validation of grammar productions for the language of thought. Plos One 13(7):1-20, 2018.
• Ignacio H. López Grande, Gabriel Senno, Gonzalo de la Torre, Miguel A. Larotonda, Ariel Bendersky, Santiago Figueira, and Antonio Acín. Distinguishing computable mixtures of quantum states. Physical Review A 97:052306, 2018.
• Laurent Bienvenu, Santiago Figueira, Benoit Monin, and Alexander Shen. Algorithmic identification of probabilities is hard. Journal of Computer and System Sciences 95:98-108, 2018.
• Sergio Abriola, Pablo Barceló, Diego Figueira and Santiago Figueira. Bisimulations on Data Graphs. Journal of Artificial Intelligence Research 61:171-213, 2018.
• Sergio Abriola, María Emilia Descotte, Raul Fervari and Santiago Figueira. Axiomatizations for downward XPath on Data Trees. Journal of Computer and System Sciences 89:209-245, 2017.
• Marie Amalric, Liping Wang, Pierre Pica, Santiago Figueira, Mariano Sigman and Stanislas Dehaene. The language of geometry: Fast comprehension of geometrical primitives and rules in human adults and preschoolers. PLOS Computational Biology 13(1) e1005273, 2017.
• Sergio Abriola, Diego Figueira y Santiago Figueira. Logics of repeating values on data trees and branching counter systems. In FoSSaCS (International Conference on Foundations of Software Science and Computation Structures), volume 10203 of Lecture Notes in Computer Science, pages 196-212, 2017.
• Sergio Abriola, María Emilia Descotte and Santiago Figueira. Model Theory of XPath on Data Trees. Part II: Binary Bisimulation and Definability. Information and Computation. 255:195-223, 2017.
• Ariel Bendersky, Gabriel Senno, Gonzalo de la Torre, Santiago Figueira and Antonio Acín. Non-signaling deterministic models for non-local correlations have to be uncomputable. Physical Review Letters, 118, 130401, 2017.
• Gabriel Senno, Ariel Bendersky, and Santiago Figueira. Randomness and non-locality. Fluctuations and Noise Letters 15, 1640005, 2016.
• Ariel Bendersky, Gonzalo de la Torre, Gabriel Senno, Santiago Figueira and Antonio Acín. Algorithmic pseudorandomness in quantum setups. Physical Review Letters 116, 230402, 2016.
• Sergio Abriola, Pablo Barceló, Diego Figueira and Santiago Figueira. Bisimulations on Data Graphs. KR (Knowledge Representation and Reasoning), AAAI Press, 309-318, 2016.
• Sergio Abriola, Santiago Figueira and Gabriel Senno. Linearizing well-quasi orders and bounding the length of bad sequences. Theoretical Computer Science 603:3-22, 2015.
• Diego Figueira, Santiago Figueira and Carlos Areces. Model Theory of XPath on Data Trees. Part I: Bisimulation and Characterization. Journal of Artificial Intelligence Research 53:271-314, 2015.
• Javier Almarza and Santiago Figueira. Normality in non-integer bases and polynomial time randomness. Journal of Computer and System Sciences 81:1059-1087, 2015.
• Santiago Figueira and André Nies. Feasible analysis, randomness, and base invariance. Theory of Computing Systems 56(3): 439-464, 2015.
• Santiago Figueira, Denis Hirschfeldt, Joseph S. Miller, André Nies and Keng Meng Ng. Counting the changes of random Δ⁰₂ sets. Journal of Logic and Computation 25(4):1073-1089, 2015.
• Sergio Abriola, María Emilia Descotte and Santiago Figueira. Definability for Downward and Vertical XPath on Data Trees. In WoLLIC 2014 (Workshop of Logic, Languages, Information and Computation, volume 8652 of Lecture Notes in Computer Science, pages 20-35, 2014.
• Facundo Carreiro, Carlos Areces and Santiago Figueira. Characterization, Definability and Separation via Saturated Models. Theoretical Computer Science 537:72-86, 2014
• Carlos Areces, Diego Figueira and Santiago Figueira. Basic Model Theory of XPath on Data Trees. In ICDT'14, ACM Press, 50-60, 2014.
• Santiago Figueira, Daniel Gorín and Rafael Grimson. Independence friendly logic with classical negation via flattening is a second-order logic with weak dependencies. Journal of Computer and System Sciences 80(6):1102-1118, 2014
• Sergio Romano, Mariano Sigman, and Santiago Figueira. LT²C²: A language of thought with Turing-computable Kolmogorov complexity. Papers in Physics, vol. 5, art. 050001, 2013.
• Sergio Abriola, Santiago Figueira and Gabriel Senno. Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders. In WoLLIC 2012 (Workshop of Logic, Languages, Information and Computation, volume 7456 of Lecture Notes in Computer Science, pages 110-126, 2012.
• Carlos Areces, Santiago Figueira and Sergio Mera. Completeness results for memory logics. Annals of Pure and Applied Logic, 163(7):961-972, 2012.
• Carlos Areces, Diego Figueira, Santiago Figueira and Sergio Mera. The Expressive Power of Memory Logics. The Review of Symbolic Logic 4(2), 290-318, 2011
• Carlos Areces, Santiago Figueira and Daniel Gorín. Using Logic in the Generation of Referring Expressions. In LACL 2011 (Logical Aspects of Computational Linguistics), volume 6736 of Lecture Notes in Artificial Intelligence, pages 17-32, 2011.
• Diego Figueira, Santiago Figueira, Sylvain Schmitz and Philippe Schnoebelen. Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma. LICS (Logic in Computer Science), 269-278, 2011.
• Carlos Areces, Facundo Carreiro, Santiago Figueira and Sergio Mera. Basic Model Theory for Memory Logics. In WoLLIC 2011 (Workshop of Logic, Languages, Information and Computation, volume 6642 of Lecture Notes in Computer Science, pages 20-34, 2011.
• Santiago Figueira, Daniel Gorín and Rafael Grimson. On the Expressive Power of IF-Logic with Classical Negation. In WoLLIC 2011 (Workshop of Logic, Languages, Information and Computation), volume 6642 of Lecture Notes in Computer Science, pages 135-145, 2011.
• Santiago Figueira and Daniel Gorín. On the size of shortest modal descriptions. Advances in Modal Logic 8:114-132, 2010.
• Santiago Figueira, Denis Hirschfeldt, Joseph S. Miller, Keng Meng Ng and André Nies. Counting the Changes of Random Δ⁰₂ Sets. In CiE 2010 (Computability in Europe), volume 6158 of Lecture Notes in Computer Science, pages 162-171, 2010.
• Santiago Figueira, Daniel Gorín and Rafael Grimson. On the formal semantics of IF-like logics. Journal of Computer and System Sciences, 76(5):333-436, 2010.
• Santiago Figueira, Joseph S. Miller and André Nies. Indifferent sets. Journal of Logic and Computation, 19(2):425-443, 2009.
• Carlos Areces, Santiago Figueira and Sergio Mera. Completeness results for Memory Logics. In LFCS 2009 (Symposium on Logical Foundations of Computer Science), volume 5407 of Lecture Notes in Computer Science, pages 16-30, 2009.
• Carlos Areces, Diego Figueira, Santiago Figueira and Sergio Mera. Expressive power and decidability for memory logics. In WoLLIC 2008 (Workshop of Logic, Languages, Information and Computation), volume 5110 of Lecture Notes in Computer Science, pages 56-68, 2008.
• Santiago Figueira, Daniel Gorín and Rafael Grimson. On the formal semantics of IF-like logics. In WoLLIC 2008 (Workshop of Logic, Languages, Information and Computation), volume 5110 of Lecture Notes in Computer Science, pages 164-178, 2008.
• Benjamín René Callejas Bedregal and Santiago Figueira. On the computing power of fuzzy Turing machines. Fuzzy Sets and Systems, 159(9):1072-1083, 2008.
• Santiago Figueira, André Nies and Frank Stephan. Lowness properties and approximations of the jump. Annals of Pure and Applied Logic, 152(1-3):51-66, 2008.
• Verónica Becher, Santiago Figueira and Rafael Picchi. Turing's unpublished algorithm for normal numbers. Theoretical Computer Science, 377(1-3):126-138, 2007.
• Santiago Figueira, Frank Stephan and Guohua Wu. Randomness and universal machines. Journal of Complexity, 22(6):738-751, 2006.
• Verónica Becher, Santiago Figueira, Serge Grigorieff and Joseph S. Miller. Randomness and halting probabilities. The Journal of Symbolic Logic, 71(4):1411-1430, 2006.
• Benjamín René Callejas Bedregal and Santiago Figueira. Classical computability and fuzzy Turing machines. In LATIN 2006 (Theoretical Informatics: 7th Latin American Symposium), volume 3887 of Lecture Notes in Computer Science, pages 154-165, 2006.
• Santiago Figueira, André Nies and Frank Stephan. Lowness properties and approximations of the jump. In WoLLIC 2005 (Workshop of Logic, Languages Information and Computation), volume 143 of Electronic Notes in Computer Science, pages 45-57, 2006.
• Verónica Becher, Santiago Figueira, André Nies and Silvana Picchi. Program size complexity for possibly infinite computations. Notre Dame Journal of Formal Logic, 46(1):51-64, 2005.
• Verónica Becher and Santiago Figueira. Kolmogorov complexity for possibly infinite computations. Journal of Logic, Language and Information, 14(2):133-148, 2005.
• Verónica Becher and Santiago Figueira. An example of a computable absolutely normal number. Theoretical Computer Science, 270:947-958, 2002.

PhD thesis

• Aspects of Randomness, University of Buenos Aires, 2006.

Supervision

• Current PhD students
  • Edwin Pin Baque (cosupervised by Diego Figueira). Languages for graph databases.
  • Gabriel Goren. Bisimulations and automata.
• Postdoc and CONICET Assistant Researcher
  • Sergio Abriola. CONICET Assistant Researcher, from 2018.
  • Guido Bellomo. CONICET Assistant Researcher, from 2020.
• Former PhD students
  • Sergio Romano (cosupervised by Mariano Sigman). Técnicas y modelos del lenguaje del pensamiento para el aprendizaje automático a partir de cuerpos de datos ralos. 2021.
  • Gabriel Senno (supervised by Ariel Bendersky). A computer-theoretical outlook on foundations of quantum information. 2017.
  • Sergio Abriola. Model theory, proof theory, and computational aspects of logics for reasoning on data trees. 2017.
• Former postdocs and CONICET Assistant Researcher
  • Sergio Abriola. CONICET Postdoc, 2017-1018.
  • María Emilia Descotte. CONICET Postdoc, 2015-2017.
  • Guido Bellomo. CONICET Postdoc, 2017-2020.
  • Ariel Bendersky. CONICET Assistant Researcher, 2016-2018.

Lecture notes (in Spanish)

• Logic and Computability. Department of Computer Science, 2020. Slides and Videos.
• Computability Theory. Department of Computer Science, 2021. Slides and Videos.

Links

• Argentinian-French Laboratory SINFIN
• Lógica, Interacción y Sistemas Inteligentes (LIIS)
• My brother! Diego Figueira