• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

LearnLib / learnlib / 21986866513

13 Feb 2026 12:28PM UTC coverage: 95.047% (-0.004%) from 95.051%
21986866513

Pull #159

github

web-flow
Merge 869f122fe into 8bc278716
Pull Request #159: Add `Resumable` support for remaining Lambda learners

72 of 74 new or added lines in 13 files covered. (97.3%)

14584 of 15344 relevant lines covered (95.05%)

1.74 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.4
/algorithms/active/lambda/src/main/java/de/learnlib/algorithm/lambda/lstar/AbstractLLambda.java
1
/* Copyright (C) 2013-2026 TU Dortmund University
2
 * This file is part of LearnLib <https://learnlib.de>.
3
 *
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
 * you may not use this file except in compliance with the License.
6
 * You may obtain a copy of the License at
7
 *
8
 *     http://www.apache.org/licenses/LICENSE-2.0
9
 *
10
 * Unless required by applicable law or agreed to in writing, software
11
 * distributed under the License is distributed on an "AS IS" BASIS,
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
 * See the License for the specific language governing permissions and
14
 * limitations under the License.
15
 */
16
package de.learnlib.algorithm.lambda.lstar;
17

18
import java.util.ArrayDeque;
19
import java.util.ArrayList;
20
import java.util.Collection;
21
import java.util.Deque;
22
import java.util.HashMap;
23
import java.util.HashSet;
24
import java.util.List;
25
import java.util.Map;
26
import java.util.Map.Entry;
27
import java.util.Objects;
28
import java.util.Set;
29

30
import de.learnlib.Resumable;
31
import de.learnlib.algorithm.LearningAlgorithm;
32
import de.learnlib.logging.Category;
33
import de.learnlib.oracle.MembershipOracle;
34
import de.learnlib.query.DefaultQuery;
35
import de.learnlib.util.MQUtil;
36
import net.automatalib.alphabet.Alphabet;
37
import net.automatalib.alphabet.SupportsGrowingAlphabet;
38
import net.automatalib.automaton.concept.FiniteRepresentation;
39
import net.automatalib.automaton.concept.SuffixOutput;
40
import net.automatalib.word.Word;
41
import org.slf4j.Logger;
42
import org.slf4j.LoggerFactory;
43

44
abstract class AbstractLLambda<M extends SuffixOutput<I, D>, I, D> implements LearningAlgorithm<M, I, D>,
45
                                                                              SupportsGrowingAlphabet<I>,
46
                                                                              Resumable<LLambdaState<I, D>>,
47
                                                                              FiniteRepresentation {
48

49
    private static final Logger LOGGER = LoggerFactory.getLogger(AbstractLLambda.class);
2 ✔
50

51
    final Alphabet<I> alphabet;
52
    final MembershipOracle<I, D> mqs;
53
    final MembershipOracle<I, D> ceqs;
54

55
    private final Set<Word<I>> shortPrefixes;
56
    private final Map<Word<I>, List<D>> rows;
57
    private final List<Word<I>> suffixes;
58

59
    AbstractLLambda(Alphabet<I> alphabet,
60
                    MembershipOracle<I, D> mqs,
61
                    MembershipOracle<I, D> ceqs,
62
                    List<Word<I>> initialSuffixes) {
2 ✔
63
        this.alphabet = alphabet;
2 ✔
64
        this.mqs = mqs;
2 ✔
65
        this.ceqs = ceqs;
2 ✔
66

67
        this.suffixes = new ArrayList<>(initialSuffixes);
2 ✔
68
        this.shortPrefixes = new HashSet<>();
2 ✔
69
        this.rows = new HashMap<>();
2 ✔
70
    }
2 ✔
71

72
    abstract int maxSearchIndex(int ceLength);
73

74
    abstract void automatonFromTable();
75

76
    abstract boolean symbolInconsistency(Word<I> u1, Word<I> u2, I a);
77

78
    protected abstract List<D> rowForState(Word<I> input);
79

80
    @Override
81
    public void startLearning() {
82
        initTable();
2 ✔
83
        learnLoop();
2 ✔
84
    }
2 ✔
85

86
    @Override
87
    public boolean refineHypothesis(DefaultQuery<I, D> counterexample) {
88
        final Deque<DefaultQuery<I, D>> witnesses = new ArrayDeque<>();
2 ✔
89
        witnesses.add(counterexample);
2 ✔
90
        boolean refined = false;
2 ✔
91

92
        while (!witnesses.isEmpty()) {
2 ✔
93
            final DefaultQuery<I, D> witness = witnesses.getFirst();
2 ✔
94

95
            if (witness.getOutput() == null) {
2 ✔
96
                witness.answer(ceqs.answerQuery(witness.getPrefix(), witness.getSuffix()));
2 ✔
97
            }
98

99
            final boolean valid = MQUtil.isCounterexample(witness, getHypothesisModel());
2 ✔
100

101
            if (valid) {
2 ✔
102
                analyzeCounterexample(witness, witnesses);
2 ✔
103
                learnLoop();
2 ✔
104
                refined = true;
2 ✔
105
            } else {
106
                witnesses.pop();
2 ✔
107
            }
108
        }
2 ✔
109

110
        assert size() == shortPrefixes.size();
2 ✔
111
        return refined;
2 ✔
112
    }
113

114
    private void initTable() {
115
        Word<I> epsilon = Word.epsilon();
2 ✔
116
        List<D> rowData = initRow(epsilon);
2 ✔
117
        rows.put(epsilon, rowData);
2 ✔
118
        addShortPrefix(epsilon);
2 ✔
119
    }
2 ✔
120

121
    private void analyzeCounterexample(DefaultQuery<I, D> counterexample, Deque<DefaultQuery<I, D>> witnesses) {
122
        M hyp = getHypothesisModel();
2 ✔
123
        Word<I> ceInput = counterexample.getInput();
2 ✔
124
        Word<I> ua = null;
2 ✔
125
        int upper = maxSearchIndex(ceInput.length());
2 ✔
126
        int lower = 0;
2 ✔
127
        while (upper - lower > 1) {
2 ✔
128
            int mid = (upper + lower) / 2;
2 ✔
129

130
            Word<I> prefix = ceInput.prefix(mid);
2 ✔
131
            Word<I> suffix = ceInput.suffix(ceInput.length() - mid);
2 ✔
132
            List<D> rowData = rowForState(prefix);
2 ✔
133
            boolean stillCe = false;
2 ✔
134
            for (Word<I> u : getShortPrefixes(rowData)) {
2 ✔
135
                D sysOut = ceqs.answerQuery(u, suffix);
2 ✔
136
                D hypOut = hyp.computeSuffixOutput(u, suffix);
2 ✔
137
                if (!Objects.equals(sysOut, hypOut)) {
2 ✔
138
                    ua = u.append(suffix.firstSymbol());
2 ✔
139
                    lower = mid;
2 ✔
140
                    stillCe = true;
2 ✔
141
                    break;
2 ✔
142
                }
143
            }
2 ✔
144
            if (stillCe) {
2 ✔
145
                continue;
2 ✔
146
            }
147
            upper = mid;
2 ✔
148
        }
2 ✔
149

150
        if (ua == null) {
2 ✔
151
            assert upper == 1;
2 ✔
152
            ua = ceInput.prefix(1);
2 ✔
153
        }
154

155
        // add witnesses
156
        int mid = (upper + lower) / 2;
2 ✔
157
        Word<I> sprime = ceInput.suffix(ceInput.length() - (mid + 1));
2 ✔
158
        List<D> rnext = getRow(ua);
2 ✔
159
        for (Word<I> uprime : getShortPrefixes(rnext)) {
2 ✔
160
            witnesses.push(new DefaultQuery<>(uprime, sprime));
2 ✔
161
        }
2 ✔
162
        witnesses.push(new DefaultQuery<>(ua, sprime));
2 ✔
163

164
        addShortPrefix(ua);
2 ✔
165
    }
2 ✔
166

167
    private void learnLoop() {
168
        while (findInconsistency() || findUnclosedness()) {
2 ✔
169
            completeObservations();
2 ✔
170
        }
171
        automatonFromTable();
2 ✔
172
    }
2 ✔
173

174
    private boolean findInconsistency() {
175
        List<Word<I>> shortAsList = new ArrayList<>(shortPrefixes);
2 ✔
176
        for (int left = 0; left < shortAsList.size() - 1; left++) {
2 ✔
177
            for (int right = left + 1; right < shortAsList.size(); right++) {
2 ✔
178
                if (findInconsistency(shortAsList.get(left), shortAsList.get(right))) {
2 ✔
179
                    return true;
2 ✔
180
                }
181
            }
182
        }
183
        return false;
2 ✔
184
    }
185

186
    private boolean findInconsistency(Word<I> u1, Word<I> u2) {
187
        List<D> rowData1 = rows.get(u1);
2 ✔
188
        List<D> rowData2 = rows.get(u2);
2 ✔
189
        if (!Objects.equals(rowData1, rowData2)) {
2 ✔
190
            return false;
2 ✔
191
        }
192
        for (I a : alphabet) {
2 ✔
193
            rowData1 = rows.get(u1.append(a));
2 ✔
194
            rowData2 = rows.get(u2.append(a));
2 ✔
195
            assert rowData1 != null && rowData2 != null;
2 ✔
196
            if (!rowData1.equals(rowData2)) {
2 ✔
197
                for (int i = 0; i < rowData1.size(); i++) {
2 ✔
198
                    if (!Objects.equals(rowData1.get(i), rowData2.get(i))) {
2 ✔
199
                        Word<I> newSuffx = suffixes.get(i).prepend(a);
2 ✔
200
                        suffixes.add(newSuffx);
2 ✔
201
                        return true;
2 ✔
202
                    }
203
                }
204
            }
205
            if (symbolInconsistency(u1, u2, a)) {
2 ✔
206
                return true;
2 ✔
207
            }
208
        }
2 ✔
209
        return false;
2 ✔
210
    }
211

212
    private List<Word<I>> getShortPrefixes(Word<I> prefix) {
213
        List<D> rowData = rows.get(prefix);
2 ✔
214
        assert rowData != null;
2 ✔
215
        return getShortPrefixes(rowData);
2 ✔
216
    }
217

218
    protected List<Word<I>> getShortPrefixes(List<D> rowData) {
219
        List<Word<I>> shortReps = new ArrayList<>();
2 ✔
220
        for (Entry<Word<I>, List<D>> e : rows.entrySet()) {
2 ✔
221
            if (shortPrefixes.contains(e.getKey()) && rowData.equals(e.getValue())) {
2 ✔
222
                shortReps.add(e.getKey());
2 ✔
223
            }
224
        }
2 ✔
225
        return shortReps;
2 ✔
226
    }
227

228
    Collection<Word<I>> getShortPrefixes() {
229
        return shortPrefixes;
2 ✔
230
    }
231

232
    List<D> getRow(Word<I> key) {
233
        List<D> row = rows.get(key);
2 ✔
234
        assert row != null;
2 ✔
235
        return row;
2 ✔
236
    }
237

238
    void addSuffix(Word<I> suffix) {
239
        this.suffixes.add(suffix);
2 ✔
240
    }
2 ✔
241

242
    private boolean findUnclosedness() {
243
        for (Word<I> prefix : rows.keySet()) {
2 ✔
244
            List<Word<I>> shortReps = getShortPrefixes(prefix);
2 ✔
245
            if (shortReps.isEmpty()) {
2 ✔
246
                addShortPrefix(prefix);
2 ✔
247
                return true;
2 ✔
248
            }
249
        }
2 ✔
250
        return false;
2 ✔
251
    }
252

253
    private void completeObservations() {
254
        for (Entry<Word<I>, List<D>> e : rows.entrySet()) {
2 ✔
255
            List<D> rowData = completeRow(e.getKey(), e.getValue());
2 ✔
256
            e.setValue(rowData);
2 ✔
257
        }
2 ✔
258
    }
2 ✔
259

260
    private List<D> initRow(Word<I> prefix) {
261
        List<D> rowData = new ArrayList<>(suffixes.size());
2 ✔
262
        for (Word<I> suffix : suffixes) {
2 ✔
263
            rowData.add(mqs.answerQuery(prefix, suffix));
2 ✔
264

265
        }
2 ✔
266
        return rowData;
2 ✔
267
    }
268

269
    private List<D> completeRow(Word<I> prefix, List<D> oldData) {
270
        if (suffixes.size() == oldData.size()) {
2 ✔
271
            return oldData;
2 ✔
272
        }
273

274
        List<D> rowData = new ArrayList<>(suffixes.size());
2 ✔
275
        rowData.addAll(oldData);
2 ✔
276
        for (int i = oldData.size(); i < suffixes.size(); i++) {
2 ✔
277
            rowData.add(mqs.answerQuery(prefix, suffixes.get(i)));
2 ✔
278
        }
279
        return rowData;
2 ✔
280
    }
281

282
    private void addShortPrefix(Word<I> shortPrefix) {
283
        assert !shortPrefixes.contains(shortPrefix) && rows.containsKey(shortPrefix);
2 ✔
284

285
        shortPrefixes.add(shortPrefix);
2 ✔
286
        for (I a : alphabet) {
2 ✔
287
            Word<I> newPrefix = shortPrefix.append(a);
2 ✔
288
            List<D> rowData = initRow(newPrefix);
2 ✔
289
            rows.put(newPrefix, rowData);
2 ✔
290
        }
2 ✔
291
    }
2 ✔
292

293
    @Override
294
    public void addAlphabetSymbol(I symbol) {
295
        if (!this.alphabet.containsSymbol(symbol)) {
2 ✔
296
            this.alphabet.asGrowingAlphabetOrThrowException().addSymbol(symbol);
2 ✔
297
        }
298

299
        if (!this.rows.isEmpty()) {
2 ✔
300
            for (Word<I> as : new ArrayList<>(this.rows.keySet())) {
2 ✔
301
                if (this.shortPrefixes.contains(as)) {
2 ✔
302
                    Word<I> lp = as.append(symbol);
2 ✔
303
                    this.rows.put(lp, initRow(lp));
2 ✔
304
                }
305
            }
2 ✔
306

307
            learnLoop();
2 ✔
308
        }
309
    }
2 ✔
310

311
    @Override
312
    public LLambdaState<I, D> suspend() {
313
        return new LLambdaState<>(alphabet, shortPrefixes, rows, suffixes);
2 ✔
314
    }
315

316
    @Override
317
    public void resume(LLambdaState<I, D> state) {
318
        this.shortPrefixes.clear();
2 ✔
319
        this.rows.clear();
2 ✔
320
        this.suffixes.clear();
2 ✔
321

322
        final Alphabet<I> oldAlphabet = state.getAlphabet();
2 ✔
323
        if (!this.alphabet.equals(oldAlphabet)) {
2 ✔
NEW
324
            LOGGER.warn(Category.DATASTRUCTURE,
×
325
                        "The current alphabet '{}' differs from the resumed alphabet '{}'. Future behavior may be inconsistent",
326
                        this.alphabet,
327
                        oldAlphabet);
328
        }
329

330
        this.shortPrefixes.addAll(state.getShortPrefixes());
2 ✔
331
        this.rows.putAll(state.getRows());
2 ✔
332
        this.suffixes.addAll(state.getSuffixes());
2 ✔
333
        automatonFromTable();
2 ✔
334
    }
2 ✔
335
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc