diff options
Diffstat (limited to 'publications/conferences.yaml')
| -rw-r--r-- | publications/conferences.yaml | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/publications/conferences.yaml b/publications/conferences.yaml new file mode 100644 index 0000000..055d028 --- /dev/null +++ b/publications/conferences.yaml @@ -0,0 +1,177 @@ +--- +references: +- id: aristoteActiveLearningDeterministic2024 + 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. + accessed: + - year: 2024 + month: 2 + day: 7 + author: + - family: Aristote + given: Quentin + citation-key: aristoteActiveLearningDeterministic2024 + collection-title: Leibniz International Proceedings in Informatics (LIPIcs) + container-title: 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) + DOI: 10.4230/LIPIcs.CSL.2024.11 + event-place: Dagstuhl, Germany + event-title: Computer Science Logic (CSL) + ISBN: 978-3-95977-310-2 + ISSN: 1868-8969 + issued: + - year: 2024 + language: en + note: Helena Rasiowa award for the Best Student Paper + page: 11:1-11:20 + publisher: Schloss-Dagstuhl - Leibniz Zentrum für Informatik + publisher-place: Dagstuhl, Germany + title: >- + Active Learning of Deterministic Transducers with Outputs in Arbitrary + Monoids + type: paper-conference + URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.11 + volume: '288' + +- id: aristoteActiveLearningUpwardclosed2025 + 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. + accessed: + - year: 2025 + month: 5 + day: 6 + author: + - family: Aristote + given: Quentin + citation-key: aristoteActiveLearningUpwardclosed2025 + collection-title: Leibniz International Proceedings in Informatics (LIPIcs) + container-title: 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025) + event-place: Dagstuhl, Germany + event-title: Conference on Algebra and Coalgebra in Computer Science (CALCO) + issued: + - year: 2025 + language: en + publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik + publisher-place: Dagstuhl, Germany + title: Active learning of upward-closed sets of words + type: paper-conference + URL: https://hal.science/hal-05051620 + +- id: aristoteLearningWeightedAutomata2025 + 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. + accessed: + - year: 2025 + month: 4 + day: 28 + author: + - family: Aristote + given: Quentin + - family: Gool + given: Sam + dropping-particle: van + - family: Petrişan + given: Daniela + - family: Shirmohammadi + given: Mahsa + citation-key: aristoteLearningWeightedAutomata2025 + container-title: >- + LICS '25: Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in + Computer Science + event-place: New York, NY, USA + event-title: Logics in Computer Science (LICS) + issued: + - year: 2025 + language: en + publisher: The Association for Computing Machinery + publisher-place: New York, NY, USA + title: Learning Weighted Automata over Number Rings, Concretely and Categorically + type: paper-conference + URL: https://hal.science/hal-05040143 + +- id: aristoteMonotoneWeakDistributive2025 + 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. + accessed: + - year: 2025 + month: 2 + day: 25 + author: + - family: Aristote + given: Quentin + citation-key: aristoteMonotoneWeakDistributive2025 + collection-title: Leibniz International Proceedings in Informatics (LIPIcs) + container-title: >- + 42nd International Symposium on Theoretical Aspects of Computer Science + (STACS 2025) + DOI: 10.4230/LIPIcs.STACS.2025.10 + editor: + - family: Beyersdorff + given: Olaf + - family: Pilipczuk + given: Michał + - family: Pimentel + given: Elaine + - family: Thắng + given: Nguyễn Kim + event-place: Dagstuhl, Germany + event-title: Symposium on Theoretical Aspects of Computer Science (STACS) + ISBN: 978-3-95977-365-2 + ISSN: 1868-8969 + issued: + - year: 2025 + language: en + page: 10:1–10:20 + publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik + publisher-place: Dagstuhl, Germany + title: >- + Monotone Weak Distributive Laws over the Lifted Powerset Monad in Categories + of Algebras + type: paper-conference + URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.10 + volume: '327' +... |