--- references: - id: aristoteActiveLearningDeterministic2024a 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. We use the categorical framework for minimization and learning of Colcombet, Petrişan and Stabile to recover the notion of minimal transducer recognizing a language, and give necessary and sufficient conditions on the output monoid for this minimal transducer to exist and be unique (up to isomorphism). The categorical framework then provides an abstract algorithm for learning it using membership and equivalence queries, and we discuss practical aspects of this algorithm’s implementation. author: - family: Aristote given: Quentin citation-key: aristoteActiveLearningDeterministic2024a event-place: Naples, Italy event-title: 32nd EACSL Annual Conference on Computer Science Logic 2024 (CSL 2024) genre: conference issued: - year: 2024 month: 2 day: 22 language: en note: >- slides: https://gitlab.math.univ-paris-diderot.fr/-/project/840/uploads/441b176a634e9ed8b569d75dc18bf98a/monoidal-transducer-learning.pdf publisher-place: Naples, Italy title: >- Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids type: speech URL: https://www.irif.fr/seminaires/automates/index - 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: - year: 2024 month: 3 day: 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: - year: 2024 month: 6 day: 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. Along 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: - year: 2025 month: 6 day: 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: aristoteAutomataWeightedCommutative2023 author: - family: Aristote given: Quentin citation-key: aristoteAutomataWeightedCommutative2023 event-place: Paris, France event-title: ASV day (IRIF) genre: seminar issued: - year: 2023 month: 12 day: 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: aristoteLearningWeightedAutomata2025a abstract: >- We study automata weighted over number rings, that is, rings of integers in an algebraic number field. We 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. We 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. Finally, 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: - year: 2025 month: 3 day: 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. As 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: - year: 2025 month: 3 day: 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. As 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: - year: 2025 month: 6 day: 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/ - id: aristoteMonotoneWeakDistributive2024a abstract: >- Noticing the similarity between the monotone weak distributive laws combining two layers of nondeterminisms in sets and in compact Hausdorff spaces, we study whether the latter law can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras: we then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases. author: - family: Aristote given: Quentin citation-key: aristoteMonotoneWeakDistributive2024a event-place: Leiden, The Netherlands event-title: 109th Peripatetic Seminar on Sheaves and Logic (PSSL 109) genre: conference issued: - year: 2024 month: 11 day: 15 language: en note: >- slides: https://dutchcats.github.io/PSSL-2024/slides_PSSL24/Aristote-PSSL109.pdf publisher-place: Leiden, The Netherlands title: >- Monotone weak distributive laws over the lifted powerset monad in categories of algebras type: speech URL: https://dutchcats.github.io/PSSL-2024/ - id: aristoteMonotoneWeakDistributive2025a abstract: >- In both the category of sets and the category of compact Hausdorff spaces, there is a monotone weak distributive law that combines two layers of non-determinism. Noticing the similarity between these two laws, we study whether the latter can be obtained automatically as a weak lifting of the former. This holds partially, but does not generalize to other categories of algebras. We then characterize when exactly monotone weak distributive laws over powerset monads in categories of algebras exist, on the one hand exhibiting a law combining probabilities and non-determinism in compact Hausdorff spaces and showing on the other hand that such laws do not exist in a lot of other cases. author: - family: Aristote given: Quentin citation-key: aristoteMonotoneWeakDistributive2025a event-place: Jena, Germany event-title: >- 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) genre: conference issued: - year: 2025 month: 3 day: 5 language: en note: >- slides: https://stacs2025.gitlab.io/slides/monotone-weak-distributive-laws-over-the-lifted-powerset-monad-in-categories-of-algebras.pdf publisher-place: Jena, Germany title: >- Monotone weak distributive laws over the lifted powerset monad in categories of algebras type: speech URL: https://stacs2025.de/ - id: aristoteMonotoneWeakDistributive2025b abstract: >- Within the study of the semantics of programming languages, computational effects may be modelled with monads, and weak distributive laws between monads are then a tool to combine two such effects. In both the category of sets and the category of compact Hausdorff spaces, there is a monotone weak distributive law that combines two layers of non-determinism. Noticing the similarity between these two laws, we study whether the latter can be obtained automatically as some sort of lifting of the former. More specifically, we show how a framework for constructing monotone weak distributive laws in regular categories lifts to categories of algebras, giving a full characterization for the existence of monotone weak distributive laws therein. We then exhibit such a law, combining probabilities and non-determinism, in compact Hausdorff spaces; but we also show how such laws do not exist in a lot of other cases. author: - family: Aristote given: Quentin citation-key: aristoteMonotoneWeakDistributive2025b event-place: Marseille, France event-title: LSC Seminar (LiS) genre: seminar issued: - year: 2025 month: 3 day: 27 language: en note: >- slides: https://gitlab.math.univ-paris-diderot.fr/-/project/1062/uploads/02cd7ed45cdac419f5cf315fdde2200a/monotone-wdl-algebras.pdf publisher-place: Marseille, France title: >- Monotone weak distributive laws over the lifted powerset monad in categories of algebras type: speech URL: https://lsc.lis-lab.fr/lsc-seminar/ - id: aristoteMonotoneWeakDistributive2025c abstract: >- When studying the semantics of programming languages, monads are a tool to model computational effects. Given two monads modelling two effects, a natural question is whether one can build a composed monad modelling the combination of these two effects. There is a generic way to do this when there exists a monotone weak distributive law between the two monads. Monotone weak distributive laws are a recently-developed mathematical tool, and the first part of the talk will focus on introducing them and giving several examples. The second part of the talk will then focus on the main result from [1], which gives a full characterization for the existence of monotone weak distributive laws in certain categories of algebras. [1] https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.10 author: - family: Aristote given: Quentin citation-key: aristoteMonotoneWeakDistributive2025c event-place: Palaiseau, France event-title: Theoretical Cosynus Seminar (LIX) genre: seminar issued: - year: 2025 month: 4 day: 8 language: en publisher-place: Palaiseau, France title: Monotone weak distributive laws in categories of algebras type: speech URL: https://www.lix.polytechnique.fr/proofs-algorithms/tcs/ - id: aristoteMulticategoricalFrameworkMinimization2024 abstract: >- Joint work with Daniela Petrişan. This paper provides a unifying category-theoretic framework for minimization and learning algorithms for bottom-up tree automata with effects. Our aim is two-fold: encompass existing algorithms for various forms of tree automata – deterministic bottom-up tree automata, residual finite tree automata, tree automata weighted over a field – and instantiate the abstract framework in order to obtain new results – tree automata weighted over prinicipal ideal domains (PIDs). author: - family: Aristote given: Quentin citation-key: aristoteMulticategoricalFrameworkMinimization2024 event-place: Bordeaux, France event-title: Highlights of Logic, Games and Automata (Highlights 2024) genre: conference issued: - year: 2024 month: 9 day: 18 language: en note: >- slides: https://gitlab.math.univ-paris-diderot.fr/-/project/1003/uploads/c415dcc8a1e22c5d91cb91cfd8d6d55f/minimal-tree-automata.pdf publisher-place: Bordeaux, France title: >- Multicategorical framework for minimization and learning of bottom-up tree automata with effects type: speech URL: https://highlights-conference.org/2024/ - id: aristoteOpenPowerObjectsCategories2025 author: - family: Aristote given: Quentin citation-key: aristoteOpenPowerObjectsCategories2025 event-place: Brno, Czech Republic event-title: International Category Theory Conference (CT 2025) genre: conference issued: - year: 2025 month: 7 day: 18 language: en note: >- slides: https://gitlab.math.univ-paris-diderot.fr/-/project/1062/uploads/620105dfc6c8ec7fef78737368585a25/open-powerobjects-algebras.pdf abstract: https://conference.math.muni.cz/ct2025/data/uploads/abstracts/aristote.pdf publisher-place: Brno, Czech Republic title: Open Power-Objects in Categories of Algebras type: speech URL: https://conference.math.muni.cz/ct2025/ - id: aristoteWeakDistributiveLaws2024 author: - family: Aristote given: Quentin citation-key: aristoteWeakDistributiveLaws2024 event-place: Barcelona, Spain event-title: Topology, Algebra, and Categories in Logic (TACL 2024) genre: conference issued: - year: 2024 month: 7 day: 4 language: en note: >- slides: https://gitlab.math.univ-paris-diderot.fr/-/project/1057/uploads/a2a13506a3034d6713fa0786adbc9ebf/wdl-powerspaces-scs.pdf abstract: https://iiia.csic.es/tacl2024/abstracts/conference/contributed/TACL_2024_paper_118.pdf publisher-place: Barcelona, Spain title: Weak distributive laws between powerspaces over stably compact spaces type: speech URL: https://iiia.csic.es/tacl2024/ ...