13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 hits per line

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

97.26

/util/src/main/java/net/automatalib/util/automaton/transducer/SubsequentialTransducers.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://automatalib.net>.
 *
 * 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 net.automatalib.util.automaton.transducer;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

import net.automatalib.automaton.transducer.MutableSubsequentialTransducer;
import net.automatalib.automaton.transducer.SubsequentialTransducer;
import net.automatalib.common.util.Pair;
import net.automatalib.common.util.mapping.Mapping;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.util.automaton.copy.AutomatonCopyMethod;
import net.automatalib.util.automaton.copy.AutomatonLowLevelCopy;
import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
import net.automatalib.word.Word;

/**
 * Utility methods of {@link SubsequentialTransducer}s.
 */
public final class SubsequentialTransducers {

    private SubsequentialTransducers() {
        // prevent initialization
    }

    /**
     * Constructs a new <i>onward</i> subsequential transducer for a given {@link SubsequentialTransducer SST}. In an
     * onward SST, for each state except the initial state, the longest common prefix over the state output and the
     * outputs of all outgoing transitions of a state is {@link Word#epsilon() epsilon}. This can be achieved by pushing
     * back the longest common prefix to the transition outputs of the incoming transitions of each state.
     *
     * @param sst
     *         the original SST
     * @param inputs
     *         the alphabet symbols to consider for this transformation
     * @param out
     *         the target automaton to write the onward form to
     * @param <S>
     *         state type (of the output SST)
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type (of the output SST)
     * @param <O>
     *         output symbol type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <S, I, T, O, A extends MutableSubsequentialTransducer<S, I, T, O>> A toOnwardSST(
            SubsequentialTransducer<?, I, ?, O> sst,
            Collection<? extends I> inputs,
            A out) {
        return toOnwardSST(sst, inputs, out, true);
    }

    /**
     * Constructs a new <i>onward</i> subsequential transducer for a given {@link SubsequentialTransducer SST}. In an
     * onward SST, for each state except the initial state, the longest common prefix over the state output and the
     * outputs of all outgoing transitions of a state is {@link Word#epsilon() epsilon}. This can be achieved by pushing
     * back the longest common prefix to the transition outputs of the incoming transitions of each state.
     *
     * @param sst
     *         the original SST
     * @param inputs
     *         the alphabet symbols to consider for this transformation
     * @param out
     *         the target automaton to write the onward form to
     * @param minimize
     *         a flag indicating whether the final result should be minimized
     * @param <S>
     *         state type (of the output SST)
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type (of the output SST)
     * @param <O>
     *         output symbol type
     * @param <A>
     *         automaton type
     *
     * @return {@code out}, for convenience
     */
    public static <S, I, T, O, A extends MutableSubsequentialTransducer<S, I, T, O>> A toOnwardSST(
            SubsequentialTransducer<?, I, ?, O> sst,
            Collection<? extends I> inputs,
            A out,
            boolean minimize) {

        assert out.size() == 0;
        AutomatonLowLevelCopy.copy(AutomatonCopyMethod.STATE_BY_STATE, sst, inputs, out);

        final Mapping<S, Set<Pair<S, I>>> incomingTransitions = getIncomingTransitions(out, inputs);
        final Deque<S> queue = new ArrayDeque<>(out.getStates());

        final S oldInit = out.getInitialState();

        if (oldInit != null && !incomingTransitions.get(oldInit).isEmpty()) {
            // copy initial state to prevent push-back of prefixes for the initial state.
            out.setInitial(oldInit, false);
            final S newInit = out.addInitialState(out.getStateProperty(oldInit));

            for (I i : inputs) {
                final T oldT = out.getTransition(oldInit, i);
                if (oldT != null) {
                    final S succ = out.getSuccessor(oldT);
                    out.addTransition(newInit, i, succ, out.getTransitionProperty(oldT));
                    incomingTransitions.get(succ).add(Pair.of(newInit, i));
                }
            }
        }

        while (!queue.isEmpty()) {
            final S s = queue.pop();
            if (Objects.equals(s, out.getInitialState())) {
                continue;
            }
            final Word<O> lcp = computeLCP(out, inputs, s);

            if (!lcp.isEmpty()) {
                final Word<O> oldStateProperty = out.getStateProperty(s);
                final Word<O> newStateProperty = oldStateProperty.subWord(lcp.length());

                out.setStateProperty(s, newStateProperty);

                for (I i : inputs) {
                    final T t = out.getTransition(s, i);
                    if (t != null) {
                        final Word<O> oldTransitionProperty = out.getTransitionProperty(t);
                        final Word<O> newTransitionProperty = oldTransitionProperty.subWord(lcp.length());

                        out.setTransitionProperty(t, newTransitionProperty);
                    }
                }

                for (Pair<S, I> trans : incomingTransitions.get(s)) {
                    final S src = trans.getFirst();
                    final T t = out.getTransition(src, trans.getSecond());
                    assert t != null;

                    final Word<O> oldTransitionProperty = out.getTransitionProperty(t);
                    final Word<O> newTransitionProperty = oldTransitionProperty.concat(lcp);

                    out.setTransitionProperty(t, newTransitionProperty);
                    if (!queue.contains(src)) {
                        queue.add(src);
                    }
                }
            }
        }

        return minimize ? HopcroftMinimizer.minimizeUniversalInvasive(out, inputs) : out;
    }

    /**
     * Checks whether a given {@link SubsequentialTransducer} is <i>onward</i>, i.e. if for each state (sans initial
     * state) the longest common prefix over its state property and the transition properties of its outgoing edges
     * equals {@link Word#epsilon() epsilon}.
     *
     * @param sst
     *         the SST to check
     * @param inputs
     *         the input symbols to consider for this check
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <O>
     *         output symbol type
     *
     * @return {@code true} if {@code sst} is onward, {@code false} otherwise
     */
    public static <S, I, O> boolean isOnwardSST(SubsequentialTransducer<S, I, ?, O> sst,
                                                Collection<? extends I> inputs) {

        for (S s : sst) {
            if (Objects.equals(s, sst.getInitialState())) {
                continue;
            }

            final Word<O> lcp = computeLCP(sst, inputs, s);
            if (!lcp.isEmpty()) {
                return false;
            }
        }

        return true;
    }

    private static <S, I, T> Mapping<S, Set<Pair<S, I>>> getIncomingTransitions(SubsequentialTransducer<S, I, T, ?> sst,
                                                                                Collection<? extends I> inputs) {

        final MutableMapping<S, Set<Pair<S, I>>> result = sst.createStaticStateMapping();

        for (S s : sst) {
            result.put(s, new HashSet<>());
        }

        for (S s : sst) {
            for (I i : inputs) {
                final T t = sst.getTransition(s, i);

                if (t != null) {
                    final S succ = sst.getSuccessor(t);
                    result.get(succ).add(Pair.of(s, i));
                }
            }
        }

        return result;
    }

    private static <S, I, T, O> Word<O> computeLCP(SubsequentialTransducer<S, I, T, O> sst,
                                                   Collection<? extends I> inputs,
                                                   S s) {

        Word<O> lcp = sst.getStateProperty(s);

        for (I i : inputs) {
            T t = sst.getTransition(s, i);
            if (t != null) {
                lcp = lcp.longestCommonPrefix(sst.getTransitionProperty(t));
            }
        }

        return lcp;
    }

}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of AutomataLib <https://automatalib.net>.
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 net.automatalib.util.automaton.transducer;
17
18	import java.util.ArrayDeque;
19	import java.util.Collection;
20	import java.util.Deque;
21	import java.util.HashSet;
22	import java.util.Objects;
23	import java.util.Set;
24
25	import net.automatalib.automaton.transducer.MutableSubsequentialTransducer;
26	import net.automatalib.automaton.transducer.SubsequentialTransducer;
27	import net.automatalib.common.util.Pair;
28	import net.automatalib.common.util.mapping.Mapping;
29	import net.automatalib.common.util.mapping.MutableMapping;
30	import net.automatalib.util.automaton.copy.AutomatonCopyMethod;
31	import net.automatalib.util.automaton.copy.AutomatonLowLevelCopy;
32	import net.automatalib.util.automaton.minimizer.HopcroftMinimizer;
33	import net.automatalib.word.Word;
34
35	/**
36	* Utility methods of {@link SubsequentialTransducer}s.
37	*/
38	public final class SubsequentialTransducers {	2✔
39
40	private SubsequentialTransducers() {
41	// prevent initialization
42	}
43
44	/**
45	* Constructs a new <i>onward</i> subsequential transducer for a given {@link SubsequentialTransducer SST}. In an
46	* onward SST, for each state except the initial state, the longest common prefix over the state output and the
47	* outputs of all outgoing transitions of a state is {@link Word#epsilon() epsilon}. This can be achieved by pushing
48	* back the longest common prefix to the transition outputs of the incoming transitions of each state.
49	*
50	* @param sst
51	* the original SST
52	* @param inputs
53	* the alphabet symbols to consider for this transformation
54	* @param out
55	* the target automaton to write the onward form to
56	* @param <S>
57	* state type (of the output SST)
58	* @param <I>
59	* input symbol type
60	* @param <T>
61	* transition type (of the output SST)
62	* @param <O>
63	* output symbol type
64	* @param <A>
65	* automaton type
66	*
67	* @return {@code out}, for convenience
68	*/
69	public static <S, I, T, O, A extends MutableSubsequentialTransducer<S, I, T, O>> A toOnwardSST(
70	SubsequentialTransducer<?, I, ?, O> sst,
71	Collection<? extends I> inputs,
72	A out) {
73	return toOnwardSST(sst, inputs, out, true);	×
74	}
75
76	/**
77	* Constructs a new <i>onward</i> subsequential transducer for a given {@link SubsequentialTransducer SST}. In an
78	* onward SST, for each state except the initial state, the longest common prefix over the state output and the
79	* outputs of all outgoing transitions of a state is {@link Word#epsilon() epsilon}. This can be achieved by pushing
80	* back the longest common prefix to the transition outputs of the incoming transitions of each state.
81	*
82	* @param sst
83	* the original SST
84	* @param inputs
85	* the alphabet symbols to consider for this transformation
86	* @param out
87	* the target automaton to write the onward form to
88	* @param minimize
89	* a flag indicating whether the final result should be minimized
90	* @param <S>
91	* state type (of the output SST)
92	* @param <I>
93	* input symbol type
94	* @param <T>
95	* transition type (of the output SST)
96	* @param <O>
97	* output symbol type
98	* @param <A>
99	* automaton type
100	*
101	* @return {@code out}, for convenience
102	*/
103	public static <S, I, T, O, A extends MutableSubsequentialTransducer<S, I, T, O>> A toOnwardSST(
104	SubsequentialTransducer<?, I, ?, O> sst,
105	Collection<? extends I> inputs,
106	A out,
107	boolean minimize) {
108
109	assert out.size() == 0;	2✔
110	AutomatonLowLevelCopy.copy(AutomatonCopyMethod.STATE_BY_STATE, sst, inputs, out);	2✔
111
112	final Mapping<S, Set<Pair<S, I>>> incomingTransitions = getIncomingTransitions(out, inputs);	2✔
113	final Deque<S> queue = new ArrayDeque<>(out.getStates());	2✔
114
115	final S oldInit = out.getInitialState();	2✔
116
117	if (oldInit != null && !incomingTransitions.get(oldInit).isEmpty()) {	2✔
118	// copy initial state to prevent push-back of prefixes for the initial state.
119	out.setInitial(oldInit, false);	2✔
120	final S newInit = out.addInitialState(out.getStateProperty(oldInit));	2✔
121
122	for (I i : inputs) {	2✔
123	final T oldT = out.getTransition(oldInit, i);	2✔
124	if (oldT != null) {	2✔
125	final S succ = out.getSuccessor(oldT);	2✔
126	out.addTransition(newInit, i, succ, out.getTransitionProperty(oldT));	2✔
127	incomingTransitions.get(succ).add(Pair.of(newInit, i));	2✔
128	}
129	}	2✔
130	}
131
132	while (!queue.isEmpty()) {	2✔
133	final S s = queue.pop();	2✔
134	if (Objects.equals(s, out.getInitialState())) {	2✔
135	continue;	2✔
136	}
137	final Word<O> lcp = computeLCP(out, inputs, s);	2✔
138
139	if (!lcp.isEmpty()) {	2✔
140	final Word<O> oldStateProperty = out.getStateProperty(s);	2✔
141	final Word<O> newStateProperty = oldStateProperty.subWord(lcp.length());	2✔
142
143	out.setStateProperty(s, newStateProperty);	2✔
144
145	for (I i : inputs) {	2✔
146	final T t = out.getTransition(s, i);	2✔
147	if (t != null) {	2✔
148	final Word<O> oldTransitionProperty = out.getTransitionProperty(t);	2✔
149	final Word<O> newTransitionProperty = oldTransitionProperty.subWord(lcp.length());	2✔
150
151	out.setTransitionProperty(t, newTransitionProperty);	2✔
152	}
153	}	2✔
154
155	for (Pair<S, I> trans : incomingTransitions.get(s)) {	2✔
156	final S src = trans.getFirst();	2✔
157	final T t = out.getTransition(src, trans.getSecond());	2✔
158	assert t != null;	2✔
159
160	final Word<O> oldTransitionProperty = out.getTransitionProperty(t);	2✔
161	final Word<O> newTransitionProperty = oldTransitionProperty.concat(lcp);	2✔
162
163	out.setTransitionProperty(t, newTransitionProperty);	2✔
164	if (!queue.contains(src)) {	2✔
165	queue.add(src);	2✔
166	}
167	}	2✔
168	}
169	}	2✔
170
171	return minimize ? HopcroftMinimizer.minimizeUniversalInvasive(out, inputs) : out;	2✔
172	}
173
174	/**
175	* Checks whether a given {@link SubsequentialTransducer} is <i>onward</i>, i.e. if for each state (sans initial
176	* state) the longest common prefix over its state property and the transition properties of its outgoing edges
177	* equals {@link Word#epsilon() epsilon}.
178	*
179	* @param sst
180	* the SST to check
181	* @param inputs
182	* the input symbols to consider for this check
183	* @param <S>
184	* state type
185	* @param <I>
186	* input symbol type
187	* @param <O>
188	* output symbol type
189	*
190	* @return {@code true} if {@code sst} is onward, {@code false} otherwise
191	*/
192	public static <S, I, O> boolean isOnwardSST(SubsequentialTransducer<S, I, ?, O> sst,
193	Collection<? extends I> inputs) {
194
195	for (S s : sst) {	2✔
196	if (Objects.equals(s, sst.getInitialState())) {	2✔
197	continue;	2✔
198	}
199
200	final Word<O> lcp = computeLCP(sst, inputs, s);	2✔
201	if (!lcp.isEmpty()) {	2✔
202	return false;	×
203	}
204	}	2✔
205
206	return true;	2✔
207	}
208
209	private static <S, I, T> Mapping<S, Set<Pair<S, I>>> getIncomingTransitions(SubsequentialTransducer<S, I, T, ?> sst,
210	Collection<? extends I> inputs) {
211
212	final MutableMapping<S, Set<Pair<S, I>>> result = sst.createStaticStateMapping();	2✔
213
214	for (S s : sst) {	2✔
215	result.put(s, new HashSet<>());	2✔
216	}	2✔
217
218	for (S s : sst) {	2✔
219	for (I i : inputs) {	2✔
220	final T t = sst.getTransition(s, i);	2✔
221
222	if (t != null) {	2✔
223	final S succ = sst.getSuccessor(t);	2✔
224	result.get(succ).add(Pair.of(s, i));	2✔
225	}
226	}	2✔
227	}	2✔
228
229	return result;	2✔
230	}
231
232	private static <S, I, T, O> Word<O> computeLCP(SubsequentialTransducer<S, I, T, O> sst,
233	Collection<? extends I> inputs,
234	S s) {
235
236	Word<O> lcp = sst.getStateProperty(s);	2✔
237
238	for (I i : inputs) {	2✔
239	T t = sst.getTransition(s, i);	2✔
240	if (t != null) {	2✔
241	lcp = lcp.longestCommonPrefix(sst.getTransitionProperty(t));	2✔
242	}
243	}	2✔
244
245	return lcp;	2✔
246	}
247
248	}

LearnLib / automatalib / 13138848026

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