From 7444e3d17fa4492845524a749c399023471c73f0 Mon Sep 17 00:00:00 2001 From: aristote Date: Sat, 10 Jan 2026 12:54:11 +0100 Subject: unpublished: add where to appear --- research/conferences.json | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/research/conferences.json b/research/conferences.json index f3eca80..7596289 100644 --- a/research/conferences.json +++ b/research/conferences.json @@ -3,6 +3,6 @@ {"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.\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.","accessed":{"date-parts":[["2025",7,29]]},"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)","DOI":"10.4230/LIPIcs.CALCO.2025.16","editor":[{"family":"Cîrstea","given":"Corina"},{"family":"Knapp","given":"Alexander"}],"event-place":"Dagstuhl, Germany","event-title":"Conference on Algebra and Coalgebra in Computer Science (CALCO)","ISBN":"978-3-95977-383-6","ISSN":"1868-8969","issued":{"date-parts":[["2025"]]},"language":"en","page":"16:1–16:12","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","publisher-place":"Dagstuhl, Germany","source":"Dagstuhl Research Online Publication Server","title":"Active Learning of Upward-Closed Sets of Words","type":"paper-conference","URL":"https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2025.16","volume":"342"}, {"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. \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.","accessed":{"date-parts":[["2025",4,28]]},"author":[{"family":"Aristote","given":"Quentin"},{"family":"Gool","given":"Sam","non-dropping-particle":"van"},{"family":"Petrişan","given":"Daniela"},{"family":"Shirmohammadi","given":"Mahsa"}],"citation-key":"aristoteLearningWeightedAutomata2025","container-title":"2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)","DOI":"10.1109/LICS65433.2025.00038","event-place":"New York, NY, USA","event-title":"Logics in Computer Science (LICS)","issued":{"date-parts":[["2025",6]]},"language":"en","page":"417–430","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://ieeexplore.ieee.org/document/11186332"}, {"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":{"date-parts":[["2025",2,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":{"date-parts":[["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"}, - {"id":"aristoteLearningBottomUpTree2026","author":[{"family":"Aristote","given":"Quentin"},{"family":"Petrisan","given":"Daniela"}],"citation-key":"aristoteLearningBottomUpTree2026","event-title":"Foundations of Software Science and Computation Structures (FoSSaCS)","issued":{"date-parts":[["2026",4]]},"language":"en","publisher":"to be published","title":"Learning Bottom-Up Tree Automata Valued in Monoidal Categories","type":"paper-conference"} + {"id":"aristoteLearningBottomUpTree2026","author":[{"family":"Aristote","given":"Quentin"},{"family":"Petrisan","given":"Daniela"}],"citation-key":"aristoteLearningBottomUpTree2026","event-title":"Foundations of Software Science and Computation Structures (FoSSaCS)","issued":{"date-parts":[["2026",4]]},"language":"en","publisher":"to appear at FoSSaCS 2026","title":"Learning Bottom-Up Tree Automata Valued in Monoidal Categories","type":"paper-conference"} ] -- cgit v1.2.3