research: talk: asv day 2025

1 files changed, 2 insertions, 1 deletions

diff --git a/research/talks.json b/research/talks.json
index a15f46c..bcd1930 100644
--- a/research/talks.json
+++ b/research/talks.json
@@ -3,8 +3,9 @@
   {"id":"aristoteActiveLearningDeterministic2024b","abstract":"We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. In a first part I'll explain how Vilar's algorithm for the active learning à la Angluin of (normal) transducers generalize to monoidal transducers. In a second part I'll then discuss how this is an instance of the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile: the active learning algorithm was obtained by instantiating monoidal transducers in this framework.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteActiveLearningDeterministic2024b","event-place":"Paris, France","event-title":"Séminaire Automates (IRIF)","genre":"seminar","issued":{"date-parts":[["2024",3,22]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/840/uploads/46406ee1029eeaa311f952e661cc742c/monoidal-transducer-learning.pdf","publisher-place":"Paris, France","title":"Active learning of deterministic transducers with outputs in arbitrary monoids","type":"speech","URL":"https://www.irif.fr/seminaires/automates/index"},
   {"id":"aristoteActiveLearningDeterministic2024c","abstract":"We study monoidal transducers, transition systems arising as deterministic automata whose transitions also produce outputs in an arbitrary monoid, for instance allowing outputs to commute or to cancel out. In a first part I'll explain how Vilar's algorithm for the active learning à la Angluin of (normal) transducers generalize to monoidal transducers. In a second part I'll then discuss how this is an instance of the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile: the active learning algorithm was obtained by instantiating monoidal transducers in this framework.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteActiveLearningDeterministic2024c","event-place":"Oxford, United Kingdom","event-title":"Verification seminar","genre":"seminar","issued":{"date-parts":[["2024",6,17]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/840/uploads/46406ee1029eeaa311f952e661cc742c/monoidal-transducer-learning.pdf","publisher-place":"Oxford, United Kingdom","title":"Active learning of deterministic transducers with outputs in arbitrary monoids","type":"speech","URL":"https://www.cs.ox.ac.uk/research/verification/"},
   {"id":"aristoteActiveLearningUpwardclosed2025a","abstract":"We give a new proof of a result from well quasi-order theory on the computability of bases for upwards-closed sets of words. This new proof is based on Angluin's L* algorithm, that learns an automaton from a minimally adequate teacher. This relates in particular two results from the 1980s: Angluin's L* algorithm, and a result from Valk and Jantzen on the computability of bases for upwards-closed sets of tuples of integers.\n\nAlong the way, we describe an algorithm for learning quasi-ordered automata from a minimally adequate teacher, and extend a generalization of Valk and Jantzen's result, encompassing both words and integers, to finitely generated monoids.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteActiveLearningUpwardclosed2025a","event-place":"Glasgow, Scotland","event-title":"11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)","genre":"conference","issued":{"date-parts":[["2025",6,17]]},"language":"en","note":"slides: https://coalg.org/calco-mfps-2025/slides/2-Tuesday/4-Session3/1-QuentinAristote.pdf","publisher-place":"Glasgow, Scotland","title":"Active learning of upward-closed sets of words","type":"speech","URL":"https://coalg.org/calco-mfps-2025/calco/"},
+  {"id":"aristoteActiveLearningUpwardclosed2025b","abstract":"We give a new proof of a result from well quasi-order theory on the computability of bases for upwards-closed sets of words. This new proof is based on Angluin's L* algorithm, that learns an automaton from a minimally adequate teacher. This relates in particular two results from the 1980s: Angluin's L* algorithm, and a result from Valk and Jantzen on the computability of bases for upwards-closed sets of tuples of integers.\n\nAlong the way, we describe an algorithm for learning quasi-ordered automata from a minimally adequate teacher, and extend a generalization of Valk and Jantzen's result, encompassing both words and integers, to finitely generated monoids.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteActiveLearningUpwardclosed2025b","event-place":"Paris, France","event-title":"ASV day 2025 (IRIF)","genre":"seminar","issued":{"date-parts":[["2025",11,28]]},"language":"en","note":"slides: https://coalg.org/calco-mfps-2025/slides/2-Tuesday/4-Session3/1-QuentinAristote.pdf","publisher-place":"Paris, France","title":"Active learning of upward-closed sets of words","type":"speech"},
   {"id":"aristoteApprentissageActifDautomates2025","abstract":"On étudie les automates pondérés dans un anneau de nombres, c'est-à-dire un anneau d'entiers dans un corps algébrique.\n\nOn montre que les anneaux de nombre sont ce qu'on appelle « presque fortement Fatou » : si un automate à n états pondéré dans un corps algébrique reconnaît une série à valeurs entières, alors il admet un automate équivalent à n+1 états pondéré dans l'anneau d'entiers correspondant.\n\nOn donne une procédure en temps polynomial pour calculer un tel automate à n+1 états pondéré par des entiers, et on montre que décider si cet automate est minimal parmi tous les automates équivalents pondérés avec des entiers est aussi difficile que le PIP, un problème sur lequel se basent certains protocoles cryptographiques et pour lequel le meilleur algorithme connu est en temps polynomial quantique.\n\nCette procédure fournit une réduction entre les problèmes d'apprentissage pour les automates pondérés dans un anneau de nombres et ceux pondérés dans un corps, et on montre qu'il s'agit d'un cas particulier d'une réduction plus générale entre les problèmes d'apprentissage pour les automates dans deux catégories liées par un foncteur avec de bonnes propriétés.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteApprentissageActifDautomates2025","event-place":"Rouen, France","event-title":"Séminaire d'informatique théorique (GR²IF, LITIS)","genre":"seminar","issued":{"date-parts":[["2025",10,23]]},"language":"fr","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/996/uploads/243a7b564a6dbed76ae619eadb670231/dedekind-weighted-automata.pdf","publisher-place":"Rouen, France","title":"Apprentissage actif d'automates pondérés dans un anneau de nombres","type":"speech","URL":"https://seminaire-info-theorique.univ-rouen.fr/"},
-  {"id":"aristoteAutomataWeightedCommutative2023","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteAutomataWeightedCommutative2023","event-place":"Paris, France","event-title":"ASV day (IRIF)","genre":"seminar","issued":{"date-parts":[["2023",12,6]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/996/uploads/48a134fb160ea880ea4676adbf1dc637/dedekind-weighted-automata.pdf","publisher-place":"Paris, France","title":"Automata weighted over commutative rings: notions of minimality and the case of Dedekind domains","type":"speech","URL":"https://www.irif.fr/poles/asv/journee_pole_2023"},
+  {"id":"aristoteAutomataWeightedCommutative2023","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteAutomataWeightedCommutative2023","event-place":"Paris, France","event-title":"ASV day (IRIF)","genre":"seminar","issued":{"date-parts":[["2023",12,6]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/996/uploads/48a134fb160ea880ea4676adbf1dc637/dedekind-weighted-automata.pdf","publisher-place":"Paris, France","title":"Automata weighted over commutative rings: notions of minimality and the case of Dedekind domains","type":"speech"},
   {"id":"aristoteLearningWeightedAutomata2025a","abstract":"We study automata weighted over number rings, that is, rings of integers in an algebraic number field.\n\nWe show that number rings are what we call \"almost strong Fatou\": if an n-state automaton weighted in a number field recognizes an integer-valued series, then it admits an equivalent n+1-state automaton weighted in the corresponding ring of integers.\n\nWe give a polynomial-time algorithm for computing such an n+1-state automaton, and show that removing any more states is at least as hard as solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.\n\nFinally, we will see how this procedure can be used to reduce active learning problems in number rings to active learning problems in fields. If time allows, I will also give a brief explanation of how this generalizes to a generic reduction procedure between active learning problems for automata valued in different categories.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteLearningWeightedAutomata2025a","event-place":"Marseille, France","event-title":"MoVe seminar (LiS)","genre":"seminar","issued":{"date-parts":[["2025",3,28]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/996/uploads/8b14ed9a7383f9776fc69aa03003890a/dedekind-weighted-automata.pdf","publisher-place":"Marseille, France","title":"Learning weighted automata over number rings, concretely (and categorically)","type":"speech","URL":"https://move.lis-lab.fr/seminars"},
   {"id":"aristoteLearningWeightedAutomata2025b","abstract":"We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. \n\nAs our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteLearningWeightedAutomata2025b","event-place":"Wadern, Germany","event-title":"Dagstuhl Seminar 25141: Categories for Automata and Language Theory","genre":"conference","issued":{"date-parts":[["2025",3,31]]},"language":"en","note":"slides: https://materials.dagstuhl.de/index.php?semnr=25141&fileId=17258","publisher-place":"Wadern, Germany","title":"Learning weighted automata over number rings, (concretely and) categorically","type":"speech","URL":"https://www.dagstuhl.de/25141"},
   {"id":"aristoteLearningWeightedAutomata2025c","abstract":"We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories.\n\nAs our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.","author":[{"family":"Aristote","given":"Quentin"}],"citation-key":"aristoteLearningWeightedAutomata2025c","event-place":"Singapore, Singapore","event-title":"Fortieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2025)","genre":"conference","issued":{"date-parts":[["2025",6,24]]},"language":"en","note":"slides: https://gitlab.math.univ-paris-diderot.fr/-/project/996/uploads/13561d884f911e1e27f5df625892bfb1/dedekind-weighted-automata.pdf","publisher-place":"Singapore, Singapore","title":"Learning weighted automata over number rings, concretely and categorically","type":"speech","URL":"https://lics.siglog.org/lics25/"},