#include <Determinize.h>

Static Public Member Functions
template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, StateType >	determinize (const automaton::DFA< SymbolType, StateType > &automaton)

template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, ext::set< StateType > >	determinize (const automaton::NFA< SymbolType, StateType > &nfa)

template<class SymbolType , class StateType >
static automaton::DFA< SymbolType, ext::set< StateType > >	determinize (const automaton::MultiInitialStateNFA< SymbolType, StateType > &nfa)

template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, StateType >	determinize (const automaton::DFTA< SymbolType, StateType > &automaton)

template<class SymbolType , class StateType >
static automaton::DFTA< SymbolType, ext::set< StateType > >	determinize (const automaton::NFTA< SymbolType, StateType > &nfta)

template<class SymbolType , class StateType >
static automaton::UnorderedDFTA< SymbolType, StateType >	determinize (const automaton::UnorderedDFTA< SymbolType, StateType > &automaton)

template<class SymbolType , class StateType >
static automaton::UnorderedDFTA< SymbolType, ext::set< StateType > >	determinize (const automaton::UnorderedNFTA< SymbolType, StateType > &nfta)

template<class InputSymbolType , class PushdownSymbolType , class StateType >
static automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, StateType >	determinize (const automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, StateType > &automaton)

template<class InputSymbolType , class PushdownSymbolType , class StateType >
static automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, ext::set< StateType > >	determinize (const automaton::InputDrivenNPDA< InputSymbolType, PushdownSymbolType, StateType > &npda)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::VisiblyPushdownDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >	determinize (const automaton::VisiblyPushdownDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::VisiblyPushdownDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< StateType, StateType > >, InputSymbolType >, ext::set< ext::pair< StateType, StateType > > >	determinize (const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &npda)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >	determinize (const automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< StateType, StateType > >, common::symbol_or_epsilon< InputSymbolType > >, ext::set< ext::pair< StateType, StateType > > >	determinize (const automaton::RealTimeHeightDeterministicNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &npda)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >	determinize (const automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType >	determinize (const automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton)

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >
static automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< ext::variant< StateType, std::string >, ext::variant< StateType, std::string > > >, common::symbol_or_epsilon< InputSymbolType > >, ext::set< ext::pair< ext::variant< StateType, std::string >, ext::variant< StateType, std::string > > > >	determinize (const automaton::NPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton)

template<class SymbolType , class StateType >
static automaton::OneTapeDTM< SymbolType, StateType >	determinize (const automaton::OneTapeDTM< SymbolType, StateType > &automaton)

template<class SymbolType , class StateType >
static automaton::ArcFactoredDeterministicZAutomaton< SymbolType, ext::set< StateType > >	determinize (const automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType > &automaton)

Detailed Description

Class implementing various algorithms for determinization of various kinds of automata.

Member Function Documentation

◆ determinize() [1/18]

template<class SymbolType , class StateType >

automaton::ArcFactoredDeterministicZAutomaton< SymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::ArcFactoredNondeterministicZAutomaton< SymbolType, StateType > & automaton )

static

Here is the call graph for this function:

◆ determinize() [2/18]

template<class SymbolType , class StateType >

automaton::DFA< SymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::DFA< SymbolType, StateType > & automaton )

static

Determinization of deterministic finite automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

dfa	deterministic finite automaton

Returns: deterministic finite automaton equivalent to dfa

Here is the caller graph for this function:

◆ determinize() [3/18]

template<class SymbolType , class StateType >

automaton::DFTA< SymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::DFTA< SymbolType, StateType > & automaton )

static

Determinization of deterministic finite tree automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
RankType	Type for the rank (arity) in ranked alphabet.
StateType	Type for the states.

Parameters

dfta	deterministic finite tree automaton

Returns: deterministic finite tree automaton equivalent to dfta

◆ determinize() [4/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::DPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & automaton )

static

Determinization of deterministic pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

dpda	deterministic pushdown automaton

Returns: deterministic pushdown automaton equivalent to dpda

◆ determinize() [5/18]

template<class InputSymbolType , class PushdownSymbolType , class StateType >

automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, StateType > & automaton )

static

Determinization of deterministic input-driven pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

dpda	deterministic input-driven pushdown automaton

Returns: deterministic input-driven pushdown automaton equivalent to dpda

◆ determinize() [6/18]

template<class InputSymbolType , class PushdownSymbolType , class StateType >

automaton::InputDrivenDPDA< InputSymbolType, PushdownSymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::InputDrivenNPDA< InputSymbolType, PushdownSymbolType, StateType > & npda )

static

Implementation of determinization for input-driven pushdown automata.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

npda	nondeterministic input-driven pushdown automaton

Returns: deterministic input-driven pushdown automaton equivalent to npda

Here is the call graph for this function:

◆ determinize() [7/18]

template<class SymbolType , class StateType >

automaton::DFA< SymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::MultiInitialStateNFA< SymbolType, StateType > & nfa )

static

Implementation of subset determinization for nondeterministic finite automata with multiple initial states.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

nfa	nondeterministic finite automaton with multiple initial states

Returns: deterministic finite automaton equivalent to nfa

Here is the call graph for this function:

◆ determinize() [8/18]

template<class SymbolType , class StateType >

automaton::DFA< SymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::NFA< SymbolType, StateType > & nfa )

static

Implementation of subset determinization for nondeterministic finite automata.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

nfa	nondeterministic finite automaton

Returns: deterministic finite automaton equivalent to nfa

Here is the call graph for this function:

◆ determinize() [9/18]

template<class SymbolType , class StateType >

automaton::DFTA< SymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::NFTA< SymbolType, StateType > & nfta )

static

Implementation of subset determinization for nondeterministic finite tree automata.

Template Parameters

SymbolType	Type for the input symbols.
RankType	Type for the rank (arity) in ranked alphabet.
StateType	Type for the states.

Parameters

nfta	nondeterministic finite tree automaton

Returns: deterministic finite tree automaton equivalent to nfta

Here is the call graph for this function:

◆ determinize() [10/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< ext::variant< StateType, std::string >, ext::variant< StateType, std::string > > >, common::symbol_or_epsilon< InputSymbolType > >, ext::set< ext::pair< ext::variant< StateType, std::string >, ext::variant< StateType, std::string > > > > automaton::determinize::Determinize::determinize ( const automaton::NPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & automaton )

static

Determinization of nondeterministic pushdown automata is implemented as a cast of such automaton to RhPDA.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

npda	nondeterministic pushdown automaton

Returns: nondeterministic pushdown automaton equivalent to npda

Here is the call graph for this function:

◆ determinize() [11/18]

template<class SymbolType , class StateType >

automaton::OneTapeDTM< SymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::OneTapeDTM< SymbolType, StateType > & automaton )

static

Determinization of deterministic pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
StateType	Type for the states.

Parameters

dtm	deterministic one-tape turing machine

Returns: deterministic one-tape turing machine equivalent to dtm

◆ determinize() [12/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & automaton )

static

Determinization of deterministic real-time height-deterministic pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

dpda	deterministic real-time height-deterministic pushdown automaton

Returns: deterministic pushdown automaton equivalent to dpda

◆ determinize() [13/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::RealTimeHeightDeterministicDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< StateType, StateType > >, common::symbol_or_epsilon< InputSymbolType > >, ext::set< ext::pair< StateType, StateType > > > automaton::determinize::Determinize::determinize ( const automaton::RealTimeHeightDeterministicNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & npda )

static

Determinization of nondeterministic real-time height-deterministic pushdown automata.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

npda	nondeterministic real-time height-deterministic pushdown automaton

Returns: deterministic pushdown automaton equivalent to npda

Here is the call graph for this function:

◆ determinize() [14/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & automaton )

static

Determinization of deterministic single pop pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

dpda	nondeterministic finite automaton with multiple initial states

Returns: deterministic single pop deterministic pushdown automaton equivalent do dpda

◆ determinize() [15/18]

template<class SymbolType , class StateType >

automaton::UnorderedDFTA< SymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::UnorderedDFTA< SymbolType, StateType > & automaton )

static

Determinization of deterministic finite tree automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
RankType	Type for the rank (arity) in ranked alphabet.
StateType	Type for the states.

Parameters

dfta	deterministic finite tree automaton

Returns: deterministic finite tree automaton equivalent to dfta

◆ determinize() [16/18]

template<class SymbolType , class StateType >

automaton::UnorderedDFTA< SymbolType, ext::set< StateType > > automaton::determinize::Determinize::determinize ( const automaton::UnorderedNFTA< SymbolType, StateType > & nfta )

static

Implementation of subset determinization for nondeterministic finite tree automata.

Template Parameters

SymbolType	Type for the input symbols.
RankType	Type for the rank (arity) in ranked alphabet.
StateType	Type for the states.

Parameters

nfta	nondeterministic finite tree automaton

Returns: deterministic finite tree automaton equivalent to nfta

Here is the call graph for this function:

◆ determinize() [17/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::VisiblyPushdownDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > automaton::determinize::Determinize::determinize ( const automaton::VisiblyPushdownDPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & automaton )

static

Determinization of deterministic visibly pushdown automata. Implemented as a no-op.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

dpda	deterministic visibly pushdown automaton

Returns: deterministic pushdown automaton equivalent to dpda

◆ determinize() [18/18]

template<class InputSymbolType , class PushdownStoreSymbolType , class StateType >

automaton::VisiblyPushdownDPDA< InputSymbolType, ext::pair< ext::set< ext::pair< StateType, StateType > >, InputSymbolType >, ext::set< ext::pair< StateType, StateType > > > automaton::determinize::Determinize::determinize ( const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > & npda )

static

Determinization of nondeterministic visibly pushdown automata.

Template Parameters

SymbolType	Type for the input symbols.
PushdownSymbolType	Type for the pushdown store symbols.
StateType	Type for the states.

Parameters

npda	nondeterministic visibly pushdown automaton

Returns: deterministic pushdown automaton equivalent to npda

Here is the call graph for this function:

The documentation for this class was generated from the following files:

alib2algo/src/automaton/determinize/Determinize.h
alib2algo/src/automaton/determinize/DeterminizeIDPDAPart.hxx
alib2algo/src/automaton/determinize/DeterminizeNFAPart.hxx
alib2algo/src/automaton/determinize/DeterminizeNFTAPart.hxx
alib2algo/src/automaton/determinize/DeterminizeRHDPDAPart.hxx
alib2algo/src/automaton/determinize/DeterminizeVPAPart.hxx
alib2algo/src/automaton/determinize/DeterminizeZAutomataPart.hxx

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ determinize() [1/18]

◆ determinize() [2/18]

◆ determinize() [3/18]

◆ determinize() [4/18]

◆ determinize() [5/18]

◆ determinize() [6/18]

◆ determinize() [7/18]

◆ determinize() [8/18]

◆ determinize() [9/18]

◆ determinize() [10/18]

◆ determinize() [11/18]

◆ determinize() [12/18]

◆ determinize() [13/18]

◆ determinize() [14/18]

◆ determinize() [15/18]

◆ determinize() [16/18]

◆ determinize() [17/18]

◆ determinize() [18/18]