de.learnlib.algorithms.lstargeneric.table

Class ObservationTable<I,D>

java.lang.Object

de.learnlib.algorithms.lstargeneric.table.ObservationTable<I,D>

Type Parameters:

I - input symbol type

D - output domain type

All Implemented Interfaces:

AccessSequenceTransformer<I>

public final class ObservationTable<I,D>
extends Object
implements AccessSequenceTransformer<I>

Observation table class.

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.

• An observation table is closed iff for each long prefix u there exists a short prefix u' such that the row contents for both prefixes are equal.
• An observation table is consistent iff for every two short prefixes 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.

Author:

Malte Isberner

Constructor Summary

Constructors

Constructor and Description
ObservationTable(Alphabet<I> alphabet) Constructor.

Method Summary

Modifier and Type	Method and Description
List<List<Row<I>>>	addShortPrefixes(List<? extends Word<I>> shortPrefixes, MembershipOracle<I,D> oracle)
List<List<Row<I>>>	addSuffix(Word<I> suffix, MembershipOracle<I,D> oracle) Adds a suffix to the list of distinguishing suffixes.
List<List<Row<I>>>	addSuffixes(Collection<? extends Word<I>> newSuffixes, MembershipOracle<I,D> oracle) Adds suffixes to the list of distinguishing suffixes.
ObservationTable<I,D>	asStandardTable()
protected static <I,D> void	buildQueries(List<DefaultQuery<I,D>> queryList, List<Word<I>> prefixes, List<? extends Word<I>> suffixes)
protected static <I,D> void	buildQueries(List<DefaultQuery<I,D>> queryList, Word<I> prefix, List<? extends Word<I>> suffixes)
protected static <I,D> void	buildRowQueries(List<DefaultQuery<I,D>> queryList, List<Row<I>> rows, List<? extends Word<I>> suffixes)
D	cellContents(Row<I> row, int columnId)
protected Row<I>	createLpRow(Word<I> prefix)
protected Row<I>	createSpRow(Word<I> prefix)
protected static <I,D> void	fetchResults(Iterator<DefaultQuery<I,D>> queryIt, List<D> output, int numSuffixes) Fetches the given number of query responses and adds them to the specified output list.
Inconsistency<I,D>	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>> initialShortPrefixes, List<Word<I>> initialSuffixes, MembershipOracle<I,D> oracle) Initializes an observation table using a specified set of suffixes.
boolean	isAccessSequence(Word<I> word)
boolean	isInitialConsistencyCheckRequired()
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<D> rowContents, boolean makeCanonical)
List<D>	rowContents(Row<I> row)
List<List<Row<I>>>	toShortPrefixes(List<Row<I>> lpRows, MembershipOracle<I,D> oracle) Moves the specified rows to the set of short prefix rows.
Word<I>	transformAccessSequence(Word<I> word)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ObservationTable

public ObservationTable(Alphabet<I> alphabet)

Constructor.

Parameters:

alphabet - the learning alphabet.

Method Detail

initialize

public List<List<Row<I>>> initialize(List<Word<I>> initialShortPrefixes,
                                     List<Word<I>> initialSuffixes,
                                     MembershipOracle<I,D> oracle)

Initializes an observation table using a specified set of suffixes.

Parameters:

initialSuffixes - the set of initial column labels.

oracle - the MembershipOracle to use for performing queries

Returns:

a list of equivalence classes of unclosed rows

addSuffix

public List<List<Row<I>>> addSuffix(Word<I> suffix,
                                    MembershipOracle<I,D> oracle)

Adds a suffix to the list of distinguishing suffixes. This is a convenience method that can be used as shorthand for addSufixes(Collections.singletonList(suffix), oracle)

Parameters:

suffix - the suffix to add

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

addSuffixes

public List<List<Row<I>>> addSuffixes(Collection<? extends Word<I>> newSuffixes,
                                      MembershipOracle<I,D> oracle)

Adds suffixes to the list of distinguishing suffixes.

Parameters:

newSuffixes - the suffixes to add

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

isInitialConsistencyCheckRequired

public boolean isInitialConsistencyCheckRequired()

toShortPrefixes

public List<List<Row<I>>> toShortPrefixes(List<Row<I>> lpRows,
                                          MembershipOracle<I,D> oracle)

Moves the specified rows to the set of short prefix rows. If some of the specified rows already are short prefix rows, they are ignored (unless they do not have any contents, in which case they are completed).

Parameters:

lpRows - the rows to move to the set of short prefix rows

oracle - the membership oracle

Returns:

a list of equivalence classes of unclosed rows

getRowSuccessor

public Row<I> getRowSuccessor(Row<I> row,
                              I sym)

addShortPrefixes

public List<List<Row<I>>> addShortPrefixes(List<? extends Word<I>> shortPrefixes,
                                           MembershipOracle<I,D> oracle)

findInconsistency

public Inconsistency<I,D> findInconsistency()

makeShort

protected boolean makeShort(Row<I> row)

createLpRow

protected Row<I> createLpRow(Word<I> prefix)

createSpRow

protected Row<I> createSpRow(Word<I> prefix)

rowContents

public List<D> rowContents(Row<I> row)

cellContents

public D cellContents(Row<I> row,
                      int columnId)

getRow

public Row<I> getRow(int rowId)

numDistinctRows

public int numDistinctRows()

getShortPrefixRows

public List<Row<I>> getShortPrefixRows()

numShortPrefixRows

public int numShortPrefixRows()

numLongPrefixRows

public int numLongPrefixRows()

numTotalRows

public int numTotalRows()

numSuffixes

public int numSuffixes()

getSuffixes

public List<Word<I>> getSuffixes()

processContents

protected boolean processContents(Row<I> row,
                                  List<D> rowContents,
                                  boolean makeCanonical)

buildQueries

protected static <I,D> void buildQueries(List<DefaultQuery<I,D>> queryList,
                                         List<Word<I>> prefixes,
                                         List<? extends Word<I>> suffixes)

buildRowQueries

protected static <I,D> void buildRowQueries(List<DefaultQuery<I,D>> queryList,
                                            List<Row<I>> rows,
                                            List<? extends Word<I>> suffixes)

buildQueries

protected static <I,D> void buildQueries(List<DefaultQuery<I,D>> queryList,
                                         Word<I> prefix,
                                         List<? extends Word<I>> suffixes)

fetchResults

protected static <I,D> void fetchResults(Iterator<DefaultQuery<I,D>> queryIt,
                                         List<D> output,
                                         int numSuffixes)

Fetches the given number of query responses and adds them to the specified output list. Also, the query iterator is advanced accordingly.

Parameters:

queryIt - the query iterator

output - the output list to write to

numSuffixes - the number of suffixes (queries)

isInitialized

public boolean isInitialized()

Checks whether this observation table has been initialized yet (i.e., contains any rows).

Returns:

true iff the table has been initialized

getInputAlphabet

public Alphabet<I> getInputAlphabet()

Retrieves the input alphabet used in this observation table.

Returns:

the input alphabet

transformAccessSequence

public Word<I> transformAccessSequence(Word<I> word)

Specified by:

transformAccessSequence in interface AccessSequenceTransformer<I>

isAccessSequence

public boolean isAccessSequence(Word<I> word)

Specified by:

isAccessSequence in interface AccessSequenceTransformer<I>

asStandardTable

public ObservationTable<I,D> asStandardTable()