I
- input symbol typeD
- output domain typepublic final class GenericObservationTable<I,D> extends Object implements MutableObservationTable<I,D>, Serializable
An observation table (OT) is the central data structure used by Angluin's L* algorithm, as described in the paper "Learning Regular Sets from Queries and Counterexamples".
An observation table is a two-dimensional table, with rows indexed by prefixes, and columns indexed by suffixes. For
a prefix u
and a suffix v
, the respective cell contains the result of the membership query
(u, v)
.
The set of prefixes (row labels) is divided into two disjoint sets: short and long prefixes. Each long prefix is a one-letter extension of a short prefix; conversely, every time a prefix is added to the set of short prefixes, all possible one-letter extensions are added to the set of long prefixes.
In order to derive a well-defined hypothesis from an observation table, it must satisfy two properties: closedness and consistency.
u
there exists
a short prefix u'
such that the row contents for both prefixes are equal. u
and u'
with identical row contents, it
holds that for every input symbol a
the rows indexed by ua
and u'a
also have
identical contents. NO_DISTINGUISHING_SUFFIX
Constructor and Description |
---|
GenericObservationTable(net.automatalib.words.Alphabet<I> alphabet)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
List<List<Row<I>>> |
addAlphabetSymbol(I symbol,
MembershipOracle<I,D> oracle) |
List<List<Row<I>>> |
addShortPrefixes(List<? extends net.automatalib.words.Word<I>> shortPrefixes,
MembershipOracle<I,D> oracle) |
List<List<Row<I>>> |
addSuffix(net.automatalib.words.Word<I> suffix,
MembershipOracle<I,D> oracle)
Adds a suffix to the list of distinguishing suffixes.
|
List<List<Row<I>>> |
addSuffixes(Collection<? extends net.automatalib.words.Word<I>> newSuffixes,
MembershipOracle<I,D> oracle)
Adds suffixes to the list of distinguishing suffixes.
|
D |
cellContents(Row<I> row,
int columnId) |
net.automatalib.words.Alphabet<I> |
getInputAlphabet()
Retrieves the input alphabet used in this observation table.
|
Collection<Row<I>> |
getLongPrefixRows() |
de.learnlib.datastructure.observationtable.RowImpl<I> |
getRow(int rowId) |
List<Row<I>> |
getShortPrefixRows() |
List<net.automatalib.words.Word<I>> |
getSuffixes()
Retrieves all suffixes in the table.
|
List<List<Row<I>>> |
initialize(List<net.automatalib.words.Word<I>> initialShortPrefixes,
List<net.automatalib.words.Word<I>> initialSuffixes,
MembershipOracle<I,D> oracle)
Initializes an observation table using a specified set of suffixes.
|
boolean |
isAccessSequence(net.automatalib.words.Word<I> word) |
boolean |
isInitialConsistencyCheckRequired() |
boolean |
isInitialized()
Checks whether this observation table has been initialized yet (i.e., contains any rows).
|
int |
numberOfDistinctRows()
Returns the number of distinct (regarding row values) rows in this observation table.
|
int |
numberOfRows()
Returns the total number of rows in this observation table.
|
List<D> |
rowContents(Row<I> row) |
void |
setInputAlphabet(net.automatalib.words.Alphabet<I> alphabet)
This is an internal method used for de-serializing.
|
List<List<Row<I>>> |
toShortPrefixes(List<Row<I>> lpRows,
MembershipOracle<I,D> oracle)
Moves the specified rows to the set of short prefix rows.
|
net.automatalib.words.Word<I> |
transformAccessSequence(net.automatalib.words.Word<I> word) |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
findDistinguishingSuffix, findDistinguishingSuffix, findDistinguishingSuffixIndex, findDistinguishingSuffixIndex, findInconsistency, findUnclosedRow, getAllPrefixes, getAllRows, getLongPrefixes, getRow, getRowSuccessor, getShortPrefixes, getSuffix, isClosed, isConsistent, numberOfLongPrefixRows, numberOfShortPrefixRows, numberOfSuffixes
longestASPrefix
public GenericObservationTable(net.automatalib.words.Alphabet<I> alphabet)
alphabet
- the learning alphabet.public List<List<Row<I>>> initialize(List<net.automatalib.words.Word<I>> initialShortPrefixes, List<net.automatalib.words.Word<I>> initialSuffixes, MembershipOracle<I,D> oracle)
MutableObservationTable
initialize
in interface MutableObservationTable<I,D>
initialSuffixes
- the set of initial column labels.oracle
- the MembershipOracle
to use for performing queriespublic int numberOfDistinctRows()
ObservationTable
numberOfDistinctRows
in interface ObservationTable<I,D>
Row.getRowContentId()
public List<List<Row<I>>> addSuffix(net.automatalib.words.Word<I> suffix, MembershipOracle<I,D> oracle)
MutableObservationTable
addSufixes(Collections.singletonList(suffix), oracle)
addSuffix
in interface MutableObservationTable<I,D>
suffix
- the suffix to addoracle
- the membership oraclepublic List<List<Row<I>>> addSuffixes(Collection<? extends net.automatalib.words.Word<I>> newSuffixes, MembershipOracle<I,D> oracle)
MutableObservationTable
addSuffixes
in interface MutableObservationTable<I,D>
newSuffixes
- the suffixes to addoracle
- the membership oraclepublic boolean isInitialConsistencyCheckRequired()
isInitialConsistencyCheckRequired
in interface MutableObservationTable<I,D>
public List<List<Row<I>>> addShortPrefixes(List<? extends net.automatalib.words.Word<I>> shortPrefixes, MembershipOracle<I,D> oracle)
addShortPrefixes
in interface MutableObservationTable<I,D>
public List<List<Row<I>>> toShortPrefixes(List<Row<I>> lpRows, MembershipOracle<I,D> oracle)
MutableObservationTable
toShortPrefixes
in interface MutableObservationTable<I,D>
lpRows
- the rows to move to the set of short prefix rowsoracle
- the membership oraclepublic D cellContents(Row<I> row, int columnId)
cellContents
in interface ObservationTable<I,D>
public List<D> rowContents(Row<I> row)
rowContents
in interface ObservationTable<I,D>
public de.learnlib.datastructure.observationtable.RowImpl<I> getRow(int rowId)
getRow
in interface ObservationTable<I,D>
public int numberOfRows()
ObservationTable
numberOfRows
in interface ObservationTable<I,D>
Row.getRowId()
public List<net.automatalib.words.Word<I>> getSuffixes()
ObservationTable
getSuffixes
in interface ObservationTable<I,D>
public boolean isInitialized()
MutableObservationTable
isInitialized
in interface MutableObservationTable<I,D>
public net.automatalib.words.Alphabet<I> getInputAlphabet()
ObservationTable
getInputAlphabet
in interface ObservationTable<I,D>
public void setInputAlphabet(net.automatalib.words.Alphabet<I> alphabet)
alphabet
- the input alphabet corresponding to the previously serialized one.public net.automatalib.words.Word<I> transformAccessSequence(net.automatalib.words.Word<I> word)
transformAccessSequence
in interface AccessSequenceTransformer<I>
public boolean isAccessSequence(net.automatalib.words.Word<I> word)
isAccessSequence
in interface AccessSequenceTransformer<I>
public List<List<Row<I>>> addAlphabetSymbol(I symbol, MembershipOracle<I,D> oracle)
addAlphabetSymbol
in interface MutableObservationTable<I,D>
@Nonnull public List<Row<I>> getShortPrefixRows()
getShortPrefixRows
in interface ObservationTable<I,D>
@Nonnull public Collection<Row<I>> getLongPrefixRows()
getLongPrefixRows
in interface ObservationTable<I,D>
Copyright © 2018. All rights reserved.