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

LearnLib / learnlib / 31619759710

12 Aug 2026 04:27PM UTC coverage: 95.488% (+1.1%) from 94.368%
31619759710

push

github

mtf90
use new version scheme

15533 of 16267 relevant lines covered (95.49%)

1.72 hits per line

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

99.41
/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.HashSet;
23
import java.util.LinkedHashMap;
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.AccessSequenceTransformer;
31
import de.learnlib.LearnerStateTracker;
32
import de.learnlib.Resumable;
33
import de.learnlib.datastructure.observationtable.OTLearner;
34
import de.learnlib.datastructure.observationtable.ObservationTable;
35
import de.learnlib.logging.Category;
36
import de.learnlib.oracle.MembershipOracle;
37
import de.learnlib.query.DefaultQuery;
38
import de.learnlib.util.MQUtil;
39
import net.automatalib.alphabet.Alphabet;
40
import net.automatalib.alphabet.SupportsGrowingAlphabet;
41
import net.automatalib.automaton.concept.FiniteRepresentation;
42
import net.automatalib.automaton.concept.SuffixOutput;
43
import net.automatalib.word.Word;
44
import org.slf4j.Logger;
45
import org.slf4j.LoggerFactory;
46

47
abstract class AbstractLLambda<M extends SuffixOutput<I, D>, I, D> implements OTLearner<M, I, D>,
48
                                                                              AccessSequenceTransformer<I>,
49
                                                                              SupportsGrowingAlphabet<I>,
50
                                                                              Resumable<LLambdaState<I, D>>,
51
                                                                              FiniteRepresentation,
52
                                                                              LearnerStateTracker {
53

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

56
    final Alphabet<I> alphabet;
57
    final MembershipOracle<I, D> mqs;
58
    final MembershipOracle<I, D> ceqs;
59

60
    private final Set<Word<I>> shortPrefixes;
61
    private final Map<Word<I>, List<D>> rows;
62
    private final List<Word<I>> suffixes;
63

64
    AbstractLLambda(Alphabet<I> alphabet,
65
                    MembershipOracle<I, D> mqs,
66
                    MembershipOracle<I, D> ceqs,
67
                    List<Word<I>> initialSuffixes) {
2✔
68
        this.alphabet = alphabet;
2✔
69
        this.mqs = mqs;
2✔
70
        this.ceqs = ceqs;
2✔
71

72
        this.suffixes = new ArrayList<>(initialSuffixes);
2✔
73
        this.shortPrefixes = new HashSet<>();
2✔
74
        this.rows = new LinkedHashMap<>();
2✔
75
    }
2✔
76

77
    abstract int maxSearchIndex(int ceLength);
78

79
    abstract void automatonFromTable();
80

81
    abstract boolean symbolInconsistency(Word<I> u1, Word<I> u2, I a);
82

83
    protected abstract List<D> rowForState(Word<I> input);
84

85
    @Override
86
    public void startLearning() {
87
        requireLearningProcessNotStarted();
2✔
88
        initTable();
2✔
89
        learnLoop();
2✔
90
    }
2✔
91

92
    @Override
93
    public boolean refineHypothesis(DefaultQuery<I, D> counterexample) {
94
        requireLearningProcessStarted();
2✔
95

96
        final Deque<DefaultQuery<I, D>> witnesses = new ArrayDeque<>();
2✔
97
        witnesses.add(counterexample);
2✔
98
        boolean refined = false;
2✔
99

100
        while (!witnesses.isEmpty()) {
2✔
101
            final DefaultQuery<I, D> witness = witnesses.getFirst();
2✔
102

103
            if (witness.getOutput() == null) {
2✔
104
                witness.answer(ceqs.answerQuery(witness.getPrefix(), witness.getSuffix()));
2✔
105
            }
106

107
            final boolean valid = MQUtil.isCounterexample(witness, getHypothesisModel());
2✔
108

109
            if (valid) {
2✔
110
                analyzeCounterexample(witness, witnesses);
2✔
111
                learnLoop();
2✔
112
                refined = true;
2✔
113
            } else {
114
                witnesses.pop();
2✔
115
            }
116
        }
2✔
117

118
        assert size() == shortPrefixes.size();
2✔
119
        return refined;
2✔
120
    }
121

122
    @Override
123
    public boolean hasLearningProcessStarted() {
124
        return !rows.isEmpty();
2✔
125
    }
126

127
    private void initTable() {
128
        Word<I> epsilon = Word.epsilon();
2✔
129
        List<D> rowData = initRow(epsilon);
2✔
130
        rows.put(epsilon, rowData);
2✔
131
        addShortPrefix(epsilon);
2✔
132
    }
2✔
133

134
    private void analyzeCounterexample(DefaultQuery<I, D> counterexample, Deque<DefaultQuery<I, D>> witnesses) {
135
        M hyp = getHypothesisModel();
2✔
136
        Word<I> ceInput = counterexample.getInput();
2✔
137
        Word<I> ua = null;
2✔
138
        int upper = maxSearchIndex(ceInput.length());
2✔
139
        int lower = 0;
2✔
140
        while (upper - lower > 1) {
2✔
141
            int mid = (upper + lower) / 2;
2✔
142

143
            Word<I> prefix = ceInput.prefix(mid);
2✔
144
            Word<I> suffix = ceInput.suffix(ceInput.length() - mid);
2✔
145
            List<D> rowData = rowForState(prefix);
2✔
146
            boolean stillCe = false;
2✔
147
            for (Word<I> u : getShortPrefixes(rowData)) {
2✔
148
                D sysOut = ceqs.answerQuery(u, suffix);
2✔
149
                D hypOut = hyp.computeSuffixOutput(u, suffix);
2✔
150
                if (!Objects.equals(sysOut, hypOut)) {
2✔
151
                    ua = u.append(suffix.firstSymbol());
2✔
152
                    lower = mid;
2✔
153
                    stillCe = true;
2✔
154
                    break;
2✔
155
                }
156
            }
2✔
157
            if (stillCe) {
2✔
158
                continue;
2✔
159
            }
160
            upper = mid;
2✔
161
        }
2✔
162

163
        if (ua == null) {
2✔
164
            assert upper == 1;
2✔
165
            ua = ceInput.prefix(1);
2✔
166
        }
167

168
        // add witnesses
169
        int mid = (upper + lower) / 2;
2✔
170
        Word<I> sprime = ceInput.suffix(ceInput.length() - (mid + 1));
2✔
171
        List<D> rnext = getRow(ua);
2✔
172
        for (Word<I> uprime : getShortPrefixes(rnext)) {
2✔
173
            witnesses.push(new DefaultQuery<>(uprime, sprime));
2✔
174
        }
2✔
175
        witnesses.push(new DefaultQuery<>(ua, sprime));
2✔
176

177
        addShortPrefix(ua);
2✔
178
    }
2✔
179

180
    private void learnLoop() {
181
        while (findInconsistency() || findUnclosedness()) {
2✔
182
            completeObservations();
2✔
183
        }
184
        automatonFromTable();
2✔
185
    }
2✔
186

187
    private boolean findInconsistency() {
188
        List<Word<I>> shortAsList = new ArrayList<>(shortPrefixes);
2✔
189
        for (int left = 0; left < shortAsList.size() - 1; left++) {
2✔
190
            for (int right = left + 1; right < shortAsList.size(); right++) {
2✔
191
                if (findInconsistency(shortAsList.get(left), shortAsList.get(right))) {
2✔
192
                    return true;
2✔
193
                }
194
            }
195
        }
196
        return false;
2✔
197
    }
198

199
    private boolean findInconsistency(Word<I> u1, Word<I> u2) {
200
        List<D> rowData1 = rows.get(u1);
2✔
201
        List<D> rowData2 = rows.get(u2);
2✔
202
        if (!Objects.equals(rowData1, rowData2)) {
2✔
203
            return false;
2✔
204
        }
205
        for (I a : alphabet) {
2✔
206
            rowData1 = rows.get(u1.append(a));
2✔
207
            rowData2 = rows.get(u2.append(a));
2✔
208
            assert rowData1 != null && rowData2 != null;
2✔
209
            if (!rowData1.equals(rowData2)) {
2✔
210
                for (int i = 0; i < rowData1.size(); i++) {
2✔
211
                    if (!Objects.equals(rowData1.get(i), rowData2.get(i))) {
2✔
212
                        Word<I> newSuffx = suffixes.get(i).prepend(a);
2✔
213
                        suffixes.add(newSuffx);
2✔
214
                        return true;
2✔
215
                    }
216
                }
217
            }
218
            if (symbolInconsistency(u1, u2, a)) {
2✔
219
                return true;
2✔
220
            }
221
        }
2✔
222
        return false;
2✔
223
    }
224

225
    private List<Word<I>> getShortPrefixes(Word<I> prefix) {
226
        List<D> rowData = rows.get(prefix);
2✔
227
        assert rowData != null;
2✔
228
        return getShortPrefixes(rowData);
2✔
229
    }
230

231
    protected List<Word<I>> getShortPrefixes(List<D> rowData) {
232
        List<Word<I>> shortReps = new ArrayList<>();
2✔
233
        for (Entry<Word<I>, List<D>> e : rows.entrySet()) {
2✔
234
            if (shortPrefixes.contains(e.getKey()) && rowData.equals(e.getValue())) {
2✔
235
                shortReps.add(e.getKey());
2✔
236
            }
237
        }
2✔
238
        return shortReps;
2✔
239
    }
240

241
    Collection<Word<I>> getShortPrefixes() {
242
        return shortPrefixes;
2✔
243
    }
244

245
    List<D> getRow(Word<I> key) {
246
        List<D> row = rows.get(key);
2✔
247
        assert row != null;
2✔
248
        return row;
2✔
249
    }
250

251
    void addSuffix(Word<I> suffix) {
252
        this.suffixes.add(suffix);
2✔
253
    }
2✔
254

255
    private boolean findUnclosedness() {
256
        for (Word<I> prefix : rows.keySet()) {
2✔
257
            List<Word<I>> shortReps = getShortPrefixes(prefix);
2✔
258
            if (shortReps.isEmpty()) {
2✔
259
                addShortPrefix(prefix);
2✔
260
                return true;
2✔
261
            }
262
        }
2✔
263
        return false;
2✔
264
    }
265

266
    private void completeObservations() {
267
        for (Entry<Word<I>, List<D>> e : rows.entrySet()) {
2✔
268
            List<D> rowData = completeRow(e.getKey(), e.getValue());
2✔
269
            e.setValue(rowData);
2✔
270
        }
2✔
271
    }
2✔
272

273
    private List<D> initRow(Word<I> prefix) {
274
        List<D> rowData = new ArrayList<>(suffixes.size());
2✔
275
        for (Word<I> suffix : suffixes) {
2✔
276
            rowData.add(mqs.answerQuery(prefix, suffix));
2✔
277

278
        }
2✔
279
        return rowData;
2✔
280
    }
281

282
    private List<D> completeRow(Word<I> prefix, List<D> oldData) {
283
        if (suffixes.size() == oldData.size()) {
2✔
284
            return oldData;
2✔
285
        }
286

287
        List<D> rowData = new ArrayList<>(suffixes.size());
2✔
288
        rowData.addAll(oldData);
2✔
289
        for (int i = oldData.size(); i < suffixes.size(); i++) {
2✔
290
            rowData.add(mqs.answerQuery(prefix, suffixes.get(i)));
2✔
291
        }
292
        return rowData;
2✔
293
    }
294

295
    private void addShortPrefix(Word<I> shortPrefix) {
296
        assert !shortPrefixes.contains(shortPrefix) && rows.containsKey(shortPrefix);
2✔
297

298
        shortPrefixes.add(shortPrefix);
2✔
299
        for (I a : alphabet) {
2✔
300
            Word<I> newPrefix = shortPrefix.append(a);
2✔
301
            List<D> rowData = initRow(newPrefix);
2✔
302
            rows.put(newPrefix, rowData);
2✔
303
        }
2✔
304
    }
2✔
305

306
    @Override
307
    public void addAlphabetSymbol(I symbol) {
308
        if (!this.alphabet.containsSymbol(symbol)) {
2✔
309
            this.alphabet.asGrowingAlphabetOrThrowException().addSymbol(symbol);
2✔
310
        }
311

312
        if (!this.rows.isEmpty()) {
2✔
313
            for (Word<I> as : new ArrayList<>(this.rows.keySet())) {
2✔
314
                if (this.shortPrefixes.contains(as)) {
2✔
315
                    Word<I> lp = as.append(symbol);
2✔
316
                    this.rows.put(lp, initRow(lp));
2✔
317
                }
318
            }
2✔
319

320
            learnLoop();
2✔
321
        }
322
    }
2✔
323

324
    @Override
325
    public ObservationTable<I, D> getObservationTable() {
326
        return new OTView<>(alphabet, shortPrefixes, rows, suffixes, this);
2✔
327
    }
328

329
    @Override
330
    public LLambdaState<I, D> suspend() {
331
        return new LLambdaState<>(alphabet, shortPrefixes, rows, suffixes);
2✔
332
    }
333

334
    @Override
335
    public void resume(LLambdaState<I, D> state) {
336
        this.shortPrefixes.clear();
2✔
337
        this.rows.clear();
2✔
338
        this.suffixes.clear();
2✔
339

340
        final Alphabet<I> oldAlphabet = state.getAlphabet();
2✔
341
        if (!this.alphabet.equals(oldAlphabet)) {
2✔
342
            LOGGER.warn(Category.DATASTRUCTURE,
×
343
                        "The current alphabet '{}' differs from the resumed alphabet '{}'. Future behavior may be inconsistent",
344
                        this.alphabet,
345
                        oldAlphabet);
346
        }
347

348
        this.shortPrefixes.addAll(state.getShortPrefixes());
2✔
349
        this.rows.putAll(state.getRows());
2✔
350
        this.suffixes.addAll(state.getSuffixes());
2✔
351
        automatonFromTable();
2✔
352
    }
2✔
353
}
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