public final class BasicOperations
extends java.lang.Object
Modifier and Type | Method and Description |
---|---|
static void |
addEpsilons(Automaton a,
java.util.Set<StatePair> pairs,
org.processmining.framework.plugin.ProMCanceller canceller)
Adds epsilon transitions to the given automaton.
|
static void |
addEpsilons2(Automaton a,
java.util.Collection<StatePair> pairs,
org.processmining.framework.plugin.ProMCanceller canceller)
Try a different strategy: keep copying traces until everything
stabilises.
|
static Automaton |
complement(Automaton a,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns a (deterministic) automaton that accepts the complement of the
language of the given automaton.
|
static Automaton |
concatenate(Automaton a1,
Automaton a2,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the concatenation of the languages of
the given automata.
|
static Automaton |
concatenate(java.util.List<Automaton> l,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the concatenation of the languages of
the given automata.
|
static void |
determinize(Automaton a,
org.processmining.framework.plugin.ProMCanceller canceller)
Determinizes the given automaton.
|
static java.lang.String |
getShortestExample(Automaton a,
boolean accepted)
Returns a shortest accepted/rejected string.
|
static void |
incorporateTrace(Automaton a,
short[] trace,
org.processmining.framework.plugin.ProMCanceller canceller)
Incorporate a trace by walking over the automaton and adding a new branch
as necessary.
|
static org.processmining.plugins.InductiveMiner.Pair<Automaton,java.util.Set<StatePair>> |
intersection(Automaton a1,
Automaton a2,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the intersection of the languages of
the given automata.
|
static boolean |
isEmpty(Automaton a)
Returns true if the given automaton accepts no strings.
|
static boolean |
isEmptyString(Automaton a)
Returns true if the given automaton accepts the empty string and nothing
else.
|
static boolean |
isTotal(Automaton a)
Returns true if the given automaton accepts all strings.
|
static Automaton |
minus(Automaton a1,
Automaton a2,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns a (deterministic) automaton that accepts the intersection of the
language of
a1 and the complement of the language of
a2 . |
static Automaton |
optional(Automaton a,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the union of the empty string and the
language of the given automaton.
|
static Automaton |
repeat(Automaton a,
int min,
int max,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts between
min and
max (including both) concatenated repetitions of the
language of the given automaton. |
static Automaton |
repeat(Automaton a,
int min,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts
min or more concatenated
repetitions of the language of the given automaton. |
static Automaton |
repeat(Automaton a,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the Kleene star (zero or more
concatenated repetitions) of the language of the given automaton.
|
static boolean |
run(Automaton a,
short[] s) |
static boolean |
run(Automaton a,
java.lang.String s)
Returns true if the given string is accepted by the automaton.
|
static boolean |
subsetOf(Automaton a1,
Automaton a2,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns true if the language of
a1 is a subset of the
language of a2 . |
static Automaton |
union(Automaton a1,
Automaton a2,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the union of the languages of the given
automata.
|
static Automaton |
union(java.util.Collection<Automaton> l,
org.processmining.framework.plugin.ProMCanceller canceller)
Returns an automaton that accepts the union of the languages of the given
automata.
|
public static Automaton concatenate(Automaton a1, Automaton a2, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states.
canceller
- public static Automaton concatenate(java.util.List<Automaton> l, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in total number of states.
canceller
- public static Automaton optional(Automaton a, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states.
canceller
- public static Automaton repeat(Automaton a, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states.
canceller
- public static Automaton repeat(Automaton a, int min, org.processmining.framework.plugin.ProMCanceller canceller)
min
or more concatenated
repetitions of the language of the given automaton.
Complexity: linear in number of states and in min
.
canceller
- public static Automaton repeat(Automaton a, int min, int max, org.processmining.framework.plugin.ProMCanceller canceller)
min
and
max
(including both) concatenated repetitions of the
language of the given automaton.
Complexity: linear in number of states and in min
and
max
.
canceller
- public static Automaton complement(Automaton a, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states (if already deterministic).
canceller
- public static Automaton minus(Automaton a1, Automaton a2, org.processmining.framework.plugin.ProMCanceller canceller)
a1
and the complement of the language of
a2
. As a side-effect, the automata may be determinized, if
not already deterministic.
Complexity: quadratic in number of states (if already deterministic).
public static org.processmining.plugins.InductiveMiner.Pair<Automaton,java.util.Set<StatePair>> intersection(Automaton a1, Automaton a2, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: quadratic in number of states.
canceller
- public static boolean subsetOf(Automaton a1, Automaton a2, org.processmining.framework.plugin.ProMCanceller canceller)
a1
is a subset of the
language of a2
. As a side-effect, a2
is
determinized if not already marked as deterministic.
Complexity: quadratic in number of states.
canceller
- public static Automaton union(Automaton a1, Automaton a2, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states.
canceller
- public static void incorporateTrace(Automaton a, short[] trace, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in length of trace.
canceller
- public static Automaton union(java.util.Collection<Automaton> l, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: linear in number of states.
public static void determinize(Automaton a, org.processmining.framework.plugin.ProMCanceller canceller)
Complexity: exponential in number of states.
public static void addEpsilons2(Automaton a, java.util.Collection<StatePair> pairs, org.processmining.framework.plugin.ProMCanceller canceller)
a
- pairs
- public static void addEpsilons(Automaton a, java.util.Set<StatePair> pairs, org.processmining.framework.plugin.ProMCanceller canceller)
pairs
- collection of StatePair
objects representing pairs of
source/destination states where epsilon transitions should be
addedpublic static boolean isEmptyString(Automaton a)
public static boolean isEmpty(Automaton a)
public static boolean isTotal(Automaton a)
public static java.lang.String getShortestExample(Automaton a, boolean accepted)
accepted
- if true, look for accepted strings; otherwise, look for
rejected stringspublic static boolean run(Automaton a, java.lang.String s)
Complexity: linear in the length of the string.
Note: for full performance, use the RunAutomaton
class.
public static boolean run(Automaton a, short[] s)