1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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'
...
|
