I
- input symbol classO
- output classpublic final class ObservationTable<I,O> extends Object implements AccessSequenceTransformer<I>
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.
Constructor and Description |
---|
ObservationTable(Alphabet<I> alphabet)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
List<List<Row<I>>> |
addShortPrefixes(List<Word<I>> shortPrefixes,
MembershipOracle<I,O> oracle) |
List<List<Row<I>>> |
addSuffix(Word<I> suffix,
MembershipOracle<I,O> oracle)
Adds a suffix to the list of distinguishing suffixes.
|
List<List<Row<I>>> |
addSuffixes(List<Word<I>> newSuffixes,
MembershipOracle<I,O> oracle)
Adds suffixes to the list of distinguishing suffixes.
|
protected static <I,O> void |
buildQueries(List<DefaultQuery<I,O>> queryList,
List<Word<I>> prefixes,
List<Word<I>> suffixes) |
protected static <I,O> void |
buildQueries(List<DefaultQuery<I,O>> queryList,
Word<I> prefix,
List<Word<I>> suffixes) |
protected static <I,O> void |
buildRowQueries(List<DefaultQuery<I,O>> queryList,
List<Row<I>> rows,
List<Word<I>> suffixes) |
O |
cellContents(Row<I> row,
int columnId) |
protected Row<I> |
createLpRow(Word<I> prefix) |
protected Row<I> |
createSpRow(Word<I> prefix) |
protected static <I,O> void |
fetchResults(Iterator<DefaultQuery<I,O>> queryIt,
List<O> output,
int numSuffixes)
Fetches the given number of query responses and adds them to the specified output list.
|
Inconsistency<I,O> |
findInconsistency() |
Alphabet<I> |
getInputAlphabet()
Retrieves the input alphabet used in this observation table.
|
Row<I> |
getRow(int rowId) |
Row<I> |
getRowSuccessor(Row<I> row,
I sym) |
List<Row<I>> |
getShortPrefixRows() |
List<Word<I>> |
getSuffixes() |
List<List<Row<I>>> |
initialize(List<Word<I>> initialSuffixes,
MembershipOracle<I,O> oracle)
Initializes an observation table using a specified set of suffixes.
|
boolean |
isAccessSequence(Word<I> word) |
boolean |
isInitialized()
Checks whether this observation table has been initialized yet (i.e., contains any rows).
|
protected boolean |
makeShort(Row<I> row) |
int |
numDistinctRows() |
int |
numLongPrefixRows() |
int |
numShortPrefixRows() |
int |
numSuffixes() |
int |
numTotalRows() |
protected boolean |
processContents(Row<I> row,
List<O> rowContents,
boolean makeCanonical) |
List<O> |
rowContents(Row<I> row) |
List<List<Row<I>>> |
toShortPrefixes(List<Row<I>> lpRows,
MembershipOracle<I,O> oracle)
Moves the specified rows to the set of short prefix rows.
|
Word<I> |
transformAccessSequence(Word<I> word) |
public ObservationTable(Alphabet<I> alphabet)
alphabet
- the learning alphabet.public List<List<Row<I>>> initialize(List<Word<I>> initialSuffixes, MembershipOracle<I,O> oracle)
initialSuffixes
- the set of initial column labels.oracle
- the MembershipOracle
to use for performing queriespublic List<List<Row<I>>> addSuffix(Word<I> suffix, MembershipOracle<I,O> oracle)
addSufixes(Collections.singletonList(suffix), oracle)
suffix
- the suffix to addoracle
- the membership oraclepublic List<List<Row<I>>> addSuffixes(List<Word<I>> newSuffixes, MembershipOracle<I,O> oracle)
newSuffixes
- the suffixes to addoracle
- the membership oraclepublic List<List<Row<I>>> toShortPrefixes(List<Row<I>> lpRows, MembershipOracle<I,O> oracle)
lpRows
- the rows to move to the set of short prefix rowsoracle
- the membership oraclepublic List<List<Row<I>>> addShortPrefixes(List<Word<I>> shortPrefixes, MembershipOracle<I,O> oracle)
public Inconsistency<I,O> findInconsistency()
protected Row<I> createLpRow(Word<I> prefix)
protected Row<I> createSpRow(Word<I> prefix)
public List<O> rowContents(Row<I> row)
public O cellContents(Row<I> row, int columnId)
public int numDistinctRows()
public List<Row<I>> getShortPrefixRows()
public int numShortPrefixRows()
public int numLongPrefixRows()
public int numTotalRows()
public int numSuffixes()
public List<Word<I>> getSuffixes()
protected boolean processContents(Row<I> row, List<O> rowContents, boolean makeCanonical)
protected static <I,O> void buildQueries(List<DefaultQuery<I,O>> queryList, List<Word<I>> prefixes, List<Word<I>> suffixes)
protected static <I,O> void buildRowQueries(List<DefaultQuery<I,O>> queryList, List<Row<I>> rows, List<Word<I>> suffixes)
protected static <I,O> void buildQueries(List<DefaultQuery<I,O>> queryList, Word<I> prefix, List<Word<I>> suffixes)
protected static <I,O> void fetchResults(Iterator<DefaultQuery<I,O>> queryIt, List<O> output, int numSuffixes)
queryIt
- the query iteratoroutput
- the output list to write tonumSuffixes
- the number of suffixes (queries)public boolean isInitialized()
public Alphabet<I> getInputAlphabet()
public Word<I> transformAccessSequence(Word<I> word)
transformAccessSequence
in interface AccessSequenceTransformer<I>
public boolean isAccessSequence(Word<I> word)
isAccessSequence
in interface AccessSequenceTransformer<I>
Copyright © 2014. All Rights Reserved.