The Joiner class

Class for taking joins of word graphs.

This class exists for its call operators which can be used to find the join of two word graphs with the same WordGraph.out_degree. This class implements the Hopcroft-Karp algorithm [HK71] for computing a finite state automata recognising the union of the languages accepted by two given automata. The input word graphs need not be complete, and the root nodes can also be specified.

Contents

`Joiner`	Class for taking joins of word graphs.
`Joiner.__call__`(…)	Overloaded function.
`Joiner.copy`(…)	Copy a `Joiner` object.
`Joiner.is_subrelation`(…)	Overloaded function.

Full API

class Joiner

__init__(self: Joiner) → None: Default constructor.

__call__(*args, **kwargs)

Overloaded function.

__call__(self: Joiner, xy: WordGraph, x: WordGraph, xroot: int, y: WordGraph, yroot: int) → None

Replace the contents of a word graph with the join of two given word graphs with respect to given root vertices.

This function replaces the contents of the word graph xy with the join of the word graphs x and y.

Parameters:

xy (WordGraph) – the word graph to store the result.
x (WordGraph) – the first word graph to join.
xroot (int) – the node to use as a root in x.
y (WordGraph) – the second word graph to join.
yroot (int) – the node to use as a root in y.

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if xroot isn’t a node in x;
LibsemigroupsError – if yroot isn’t a node in y;
LibsemigroupsError – if x.out_degree() != y.out_degree().

__call__(self: Joiner, xy: WordGraph, x: WordGraph, y: WordGraph) → None

Replace the contents of a word graph with the join of two given word graphs.

This function replaces the contents of the word graph xy with the join of the word graphs x and y.

Parameters:

xy (WordGraph) – the word graph to store the result.
x (WordGraph) – the first word graph to join.
y (WordGraph) – the second word graph to join.

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if x.out_degree() != y.out_degree().

__call__(self: Joiner, x: WordGraph, xroot: int, y: WordGraph, yroot: int) → WordGraph

Returns a word graph containing the join of two given word graphs with respect to given root vertices.

This function returns a word graph containing the join of the word graphs x and y.

Parameters:

x (WordGraph) – the first word graph to join.
xroot (int) – the node to use as a root in x.
y (WordGraph) – the second word graph to join.
yroot (int) – the node to use as a root in y.

Returns:

The join of x an y.

Return type:

WordGraph

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if xroot isn’t a node in x;
LibsemigroupsError – if yroot isn’t a node in y;
LibsemigroupsError – if x.out_degree() != y.out_degree().

__call__(self: Joiner, x: WordGraph, y: WordGraph) → WordGraph

Returns a word graph containing the join of two given word graphs.

This function returns a word graph containing the join of the word graphs x and y.

Parameters:

x (WordGraph) – the first word graph to join.
y (WordGraph) – the second word graph to join.

Returns:

The join of x and y.

Return type:

WordGraph

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if x.out_degree() != y.out_degree().

copy(self: Joiner) → Joiner

Copy a Joiner object.

Returns:: A copy.
Return type:: Joiner

is_subrelation(self: Joiner, x: WordGraph, xroot: int, y: WordGraph, yroot: int) → bool

Overloaded function.

is_subrelation(self: Joiner, x: WordGraph, y: WordGraph) → bool

Check if the language accepted by one word graph is contained in that defined by another word graph.

This function returns True if the language accepted by x with initial node 0 and accept state every node, is a subset of the corresponding language in y.

Parameters:

x (WordGraph) – the word graph whose language we are checking might be a subset.
y (WordGraph) – the word graph whose language we are checking might be a superset.

Returns:

Whether or not x is a subrelation of y.

Return type:

bool

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if x.out_degree() != y.out_degree().

is_subrelation(self: Joiner, x: WordGraph, xroot: int, y: WordGraph, yroot: int) → bool

Check if the language accepted by one word graph is contained in that defined by another word graph.

This function returns True if the language accepted by x with initial node xroot and accept state every node, is a subset of the corresponding language in y.

Parameters:

x (WordGraph) – the word graph whose language we are checking might be a subset.
xroot (int) – the node to use as the initial state in x.
y (WordGraph) – the word graph whose language we are checking might be a superset.
yroot (int) – the node to use as an initial state in y.

Returns:

Whether or not x is a subrelation of y.

Return type:

bool

Raises:

LibsemigroupsError – if x has no nodes;
LibsemigroupsError – if y has no nodes;
LibsemigroupsError – if xroot isn’t a node in x;
LibsemigroupsError – if yroot isn’t a node in y;
LibsemigroupsError – if x.out_degree() != y.out_degree().