6673301747

Committed 27 Oct 2023 11:46PM UTC coverage: 91.986% (-1.3%) from 93.327%

Build # 6673301747

Build Type

push

github

Committed by

mtf90

Commit Message

merge the release and sign-artifacts profiles

Run Details

10984 of 11941 relevant lines covered (91.99%)

1.72 hits per line

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

98.39

/algorithms/active/aaar/src/main/java/de/learnlib/algorithm/aaar/AbstractAAARLearner.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.learnlib.de/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package de.learnlib.algorithm.aaar;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;

import de.learnlib.algorithm.aaar.abstraction.AbstractAbstractionTree;
import de.learnlib.api.algorithm.LearnerConstructor;
import de.learnlib.api.algorithm.LearningAlgorithm;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.DefaultQuery;
import net.automatalib.SupportsGrowingAlphabet;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.GrowingAlphabet;
import net.automatalib.alphabet.impl.GrowingMapAlphabet;
import net.automatalib.automaton.MutableDeterministic;
import net.automatalib.automaton.UniversalDeterministicAutomaton;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;

/**
 * Base implementation of the learner presented in "Automata Learning with Automated Alphabet Abstraction Refinement" by
 * Howar et al.
 * <p>
 * This implementation is a {@link LearningAlgorithm} for abstract models but operates on concrete systems with concrete
 * input symbols. Therefore, the learner receives concrete counterexamples which are transformed into abstract ones
 * (using the simultaneously inferred {@link AbstractAbstractionTree abstraction tree}) whose symbols are then mapped to
 * their concrete representatives again, prior to actual refinement. Since this concept is agnostic to the actual
 * learning process, this learner can be parameterized with an arbitrary (concrete) learning algorithm for the acutal
 * inference.
 * <p>
 * There exist several accessor for different views on the current hypothesis, e.g., the actual hypothesis of the
 * internal learner, an abstracted hypothesis, and a translating hypothesis which automatically performs the previously
 * mentioned translation steps for offering a model that is able to handle previously unobserved (concrete) input
 * symbols.
 *
 * @param <L>
 *         learner type
 * @param <AM>
 *         abstract model type
 * @param <CM>
 *         concrete model type
 * @param <AI>
 *         abstract input symbol type
 * @param <CI>
 *         concrete input symbol type
 * @param <D>
 *         output domain type
 */
public abstract class AbstractAAARLearner<L extends LearningAlgorithm<CM, CI, D> & SupportsGrowingAlphabet<CI>, AM, CM, AI, CI, D>
        implements LearningAlgorithm<AM, CI, D> {

    private final L learner;
    private final MembershipOracle<CI, D> oracle;

    private final GrowingAlphabet<CI> rep;
    private final GrowingAlphabet<AI> abs;

    public AbstractAAARLearner(LearnerConstructor<L, CI, D> learnerConstructor, MembershipOracle<CI, D> o) {
        this.oracle = o;
        this.rep = new GrowingMapAlphabet<>();
        this.abs = new GrowingMapAlphabet<>();

        this.learner = learnerConstructor.constructLearner(rep, oracle);
    }

    @Override
    public void startLearning() {
        for (AI ai : getInitialAbstracts()) {
            this.abs.addSymbol(ai);
        }
        for (CI ci : getInitialRepresentatives()) {
            this.rep.addSymbol(ci);
            this.learner.addAlphabetSymbol(ci);
        }
        learner.startLearning();
    }

    @Override
    public boolean refineHypothesis(DefaultQuery<CI, D> query) {

        final Word<CI> input = query.getInput();
        final WordBuilder<CI> wb = new WordBuilder<>(input.size());

        Word<CI> prefix = Word.epsilon();

        for (int i = 0; i < input.size(); i++) {
            final CI cur = input.getSymbol(i);
            // lift & lower
            final AbstractAbstractionTree<AI, CI, D> tree = getTreeForRepresentative(cur);
            final AI a = tree.getAbstractSymbol(cur);
            final CI r = tree.getRepresentative(a);

            final Word<CI> suffix = input.suffix(input.size() - i - 1);

            final Word<CI> testOld = prefix.append(r).concat(suffix);
            final Word<CI> testNew = prefix.append(cur).concat(suffix);

            final D outOld = oracle.answerQuery(testOld);
            final D outNew = oracle.answerQuery(testNew);

            if (!Objects.equals(outOld, outNew)) { // add new abstraction
                final AI newA = tree.splitLeaf(r, cur, prefix, suffix, outOld);
                abs.addSymbol(newA);
                rep.addSymbol(cur);
                learner.addAlphabetSymbol(cur);
                return true;
            } else {
                prefix = prefix.append(r);
                wb.append(r);
            }
        }

        final int prefixLen = query.getPrefix().length();
        final DefaultQuery<CI, D> concreteCE =
                new DefaultQuery<>(wb.toWord(0, prefixLen), wb.toWord(prefixLen, wb.size()), query.getOutput());

        return learner.refineHypothesis(concreteCE);
    }

    /**
     * Returns the (abstract) alphabet of the current (abstract) hypothesis model (cf. {@link #getHypothesisModel()}).
     *
     * @return the (abstract) alphabet of the current (abstract) hypothesis model
     */
    public Alphabet<AI> getAbstractAlphabet() {
        return this.abs;
    }

    /**
     * Returns the (concrete) alphabet of the current (concrete) internal hypothesis model (cf.
     * {@link #getLearnerHypothesisModel()}).
     *
     * @return the (concrete) alphabet of the current (concrete) internal hypothesis model
     */
    public abstract Alphabet<CI> getLearnerAlphabet();

    /**
     * Returns the (concrete) hypothesis model form the provided internal learner.
     *
     * @return the (concrete) hypothesis model form the provided internal learner
     */
    public CM getLearnerHypothesisModel() {
        return learner.getHypothesisModel();
    }

    /**
     * Returns a model of the current internal hypothesis model (cf. {@link #getLearnerHypothesisModel()}) that
     * automatically transforms (concrete) input symbols to abstract ones and uses their representatives to actually
     * perform transitions. This allows the returned model to handle (concrete) input symbols that have not yet been
     * added to the hypothesis by previous abstraction refinements. Note that this model requires the
     * {@link MembershipOracle} passed to the constructor of this learner to still function in order to determine the
     * abstract input symbols.
     *
     * @return the (concrete) hypothesis model that automatically transforms input symbols
     */
    public abstract CM getTranslatingHypothesisModel();

    /**
     * Returns the created instance of the provided internal learner.
     *
     * @return the created instance of the provided internal learner
     */
    public L getLearner() {
        return this.learner;
    }

    protected <S1, S2, SP, TP> void copyAbstract(UniversalDeterministicAutomaton<S1, CI, ?, SP, TP> src,
                                                 MutableDeterministic<S2, AI, ?, SP, TP> tgt) {
        // states
        final Map<S2, S1> states = new HashMap<>();
        final Map<S1, S2> statesRev = new HashMap<>();

        for (S1 s : src.getStates()) {
            final SP sp = src.getStateProperty(s);
            final S2 n = tgt.addState(sp);
            tgt.setInitial(n, Objects.equals(s, src.getInitialState()));

            states.put(n, s);
            statesRev.put(s, n);
        }

        // transitions
        for (Entry<S2, S1> e : states.entrySet()) {
            for (CI r : rep) {
                final AbstractAbstractionTree<AI, CI, D> tree = getTreeForRepresentative(r);
                final AI a = tree.getAbstractSymbol(r);
                tgt.setTransition(e.getKey(),
                                  a,
                                  statesRev.get(src.getSuccessor(e.getValue(), r)),
                                  src.getTransitionProperty(e.getValue(), r));
            }
        }
    }

    protected abstract AbstractAbstractionTree<AI, CI, D> getTreeForRepresentative(CI ci);

    protected abstract Collection<AI> getInitialAbstracts();

    protected abstract Collection<CI> getInitialRepresentatives();
}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of LearnLib, http://www.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.aaar;
17
18	import java.util.Collection;
19	import java.util.HashMap;
20	import java.util.Map;
21	import java.util.Map.Entry;
22	import java.util.Objects;
23
24	import de.learnlib.algorithm.aaar.abstraction.AbstractAbstractionTree;
25	import de.learnlib.api.algorithm.LearnerConstructor;
26	import de.learnlib.api.algorithm.LearningAlgorithm;
27	import de.learnlib.api.oracle.MembershipOracle;
28	import de.learnlib.api.query.DefaultQuery;
29	import net.automatalib.SupportsGrowingAlphabet;
30	import net.automatalib.alphabet.Alphabet;
31	import net.automatalib.alphabet.GrowingAlphabet;
32	import net.automatalib.alphabet.impl.GrowingMapAlphabet;
33	import net.automatalib.automaton.MutableDeterministic;
34	import net.automatalib.automaton.UniversalDeterministicAutomaton;
35	import net.automatalib.word.Word;
36	import net.automatalib.word.WordBuilder;
37
38	/**
39	* Base implementation of the learner presented in "Automata Learning with Automated Alphabet Abstraction Refinement" by
40	* Howar et al.
41	* <p>
42	* This implementation is a {@link LearningAlgorithm} for abstract models but operates on concrete systems with concrete
43	* input symbols. Therefore, the learner receives concrete counterexamples which are transformed into abstract ones
44	* (using the simultaneously inferred {@link AbstractAbstractionTree abstraction tree}) whose symbols are then mapped to
45	* their concrete representatives again, prior to actual refinement. Since this concept is agnostic to the actual
46	* learning process, this learner can be parameterized with an arbitrary (concrete) learning algorithm for the acutal
47	* inference.
48	* <p>
49	* There exist several accessor for different views on the current hypothesis, e.g., the actual hypothesis of the
50	* internal learner, an abstracted hypothesis, and a translating hypothesis which automatically performs the previously
51	* mentioned translation steps for offering a model that is able to handle previously unobserved (concrete) input
52	* symbols.
53	*
54	* @param <L>
55	* learner type
56	* @param <AM>
57	* abstract model type
58	* @param <CM>
59	* concrete model type
60	* @param <AI>
61	* abstract input symbol type
62	* @param <CI>
63	* concrete input symbol type
64	* @param <D>
65	* output domain type
66	*/
67	public abstract class AbstractAAARLearner<L extends LearningAlgorithm<CM, CI, D> & SupportsGrowingAlphabet<CI>, AM, CM, AI, CI, D>
68	implements LearningAlgorithm<AM, CI, D> {
69
70	private final L learner;
71	private final MembershipOracle<CI, D> oracle;
72
73	private final GrowingAlphabet<CI> rep;
74	private final GrowingAlphabet<AI> abs;
75
76	public AbstractAAARLearner(LearnerConstructor<L, CI, D> learnerConstructor, MembershipOracle<CI, D> o) {	2✔
77	this.oracle = o;	2✔
78	this.rep = new GrowingMapAlphabet<>();	2✔
79	this.abs = new GrowingMapAlphabet<>();	2✔
80
81	this.learner = learnerConstructor.constructLearner(rep, oracle);	2✔
82	}	2✔
83
84	@Override
85	public void startLearning() {
86	for (AI ai : getInitialAbstracts()) {	2✔
87	this.abs.addSymbol(ai);	2✔
88	}	2✔
89	for (CI ci : getInitialRepresentatives()) {	2✔
90	this.rep.addSymbol(ci);	2✔
91	this.learner.addAlphabetSymbol(ci);	2✔
92	}	2✔
93	learner.startLearning();	2✔
94	}	2✔
95
96	@Override
97	public boolean refineHypothesis(DefaultQuery<CI, D> query) {
98
99	final Word<CI> input = query.getInput();	2✔
100	final WordBuilder<CI> wb = new WordBuilder<>(input.size());	2✔
101
102	Word<CI> prefix = Word.epsilon();	2✔
103
104	for (int i = 0; i < input.size(); i++) {	2✔
105	final CI cur = input.getSymbol(i);	2✔
106	// lift & lower
107	final AbstractAbstractionTree<AI, CI, D> tree = getTreeForRepresentative(cur);	2✔
108	final AI a = tree.getAbstractSymbol(cur);	2✔
109	final CI r = tree.getRepresentative(a);	2✔
110
111	final Word<CI> suffix = input.suffix(input.size() - i - 1);	2✔
112
113	final Word<CI> testOld = prefix.append(r).concat(suffix);	2✔
114	final Word<CI> testNew = prefix.append(cur).concat(suffix);	2✔
115
116	final D outOld = oracle.answerQuery(testOld);	2✔
117	final D outNew = oracle.answerQuery(testNew);	2✔
118
119	if (!Objects.equals(outOld, outNew)) { // add new abstraction	2✔
120	final AI newA = tree.splitLeaf(r, cur, prefix, suffix, outOld);	2✔
121	abs.addSymbol(newA);	2✔
122	rep.addSymbol(cur);	2✔
123	learner.addAlphabetSymbol(cur);	2✔
124	return true;	2✔
125	} else {
126	prefix = prefix.append(r);	2✔
127	wb.append(r);	2✔
128	}
129	}
130
131	final int prefixLen = query.getPrefix().length();	2✔
132	final DefaultQuery<CI, D> concreteCE =	2✔
133	new DefaultQuery<>(wb.toWord(0, prefixLen), wb.toWord(prefixLen, wb.size()), query.getOutput());	2✔
134
135	return learner.refineHypothesis(concreteCE);	2✔
136	}
137
138	/**
139	* Returns the (abstract) alphabet of the current (abstract) hypothesis model (cf. {@link #getHypothesisModel()}).
140	*
141	* @return the (abstract) alphabet of the current (abstract) hypothesis model
142	*/
143	public Alphabet<AI> getAbstractAlphabet() {
144	return this.abs;	2✔
145	}
146
147	/**
148	* Returns the (concrete) alphabet of the current (concrete) internal hypothesis model (cf.
149	* {@link #getLearnerHypothesisModel()}).
150	*
151	* @return the (concrete) alphabet of the current (concrete) internal hypothesis model
152	*/
153	public abstract Alphabet<CI> getLearnerAlphabet();
154
155	/**
156	* Returns the (concrete) hypothesis model form the provided internal learner.
157	*
158	* @return the (concrete) hypothesis model form the provided internal learner
159	*/
160	public CM getLearnerHypothesisModel() {
161	return learner.getHypothesisModel();	2✔
162	}
163
164	/**
165	* Returns a model of the current internal hypothesis model (cf. {@link #getLearnerHypothesisModel()}) that
166	* automatically transforms (concrete) input symbols to abstract ones and uses their representatives to actually
167	* perform transitions. This allows the returned model to handle (concrete) input symbols that have not yet been
168	* added to the hypothesis by previous abstraction refinements. Note that this model requires the
169	* {@link MembershipOracle} passed to the constructor of this learner to still function in order to determine the
170	* abstract input symbols.
171	*
172	* @return the (concrete) hypothesis model that automatically transforms input symbols
173	*/
174	public abstract CM getTranslatingHypothesisModel();
175
176	/**
177	* Returns the created instance of the provided internal learner.
178	*
179	* @return the created instance of the provided internal learner
180	*/
181	public L getLearner() {
182	return this.learner;	×
183	}
184
185	protected <S1, S2, SP, TP> void copyAbstract(UniversalDeterministicAutomaton<S1, CI, ?, SP, TP> src,
186	MutableDeterministic<S2, AI, ?, SP, TP> tgt) {
187	// states
188	final Map<S2, S1> states = new HashMap<>();	2✔
189	final Map<S1, S2> statesRev = new HashMap<>();	2✔
190
191	for (S1 s : src.getStates()) {	2✔
192	final SP sp = src.getStateProperty(s);	2✔
193	final S2 n = tgt.addState(sp);	2✔
194	tgt.setInitial(n, Objects.equals(s, src.getInitialState()));	2✔
195
196	states.put(n, s);	2✔
197	statesRev.put(s, n);	2✔
198	}	2✔
199
200	// transitions
201	for (Entry<S2, S1> e : states.entrySet()) {	2✔
202	for (CI r : rep) {	2✔
203	final AbstractAbstractionTree<AI, CI, D> tree = getTreeForRepresentative(r);	2✔
204	final AI a = tree.getAbstractSymbol(r);	2✔
205	tgt.setTransition(e.getKey(),	2✔
206	a,
207	statesRev.get(src.getSuccessor(e.getValue(), r)),	2✔
208	src.getTransitionProperty(e.getValue(), r));	2✔
209	}	2✔
210	}	2✔
211	}	2✔
212
213	protected abstract AbstractAbstractionTree<AI, CI, D> getTreeForRepresentative(CI ci);
214
215	protected abstract Collection<AI> getInitialAbstracts();
216
217	protected abstract Collection<CI> getInitialRepresentatives();
218	}

LearnLib / learnlib / 6673301747

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

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