The Meeter class

Class for taking meets of word graphs.

This class exists for its call operators which can be used to find the meet of two word graphs with the same WordGraph.out_degree. This class implements the same algorithm as that used for computing a finite state automata recognising the intersection 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

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

Full API

class Meeter

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

__call__(*args, **kwargs)

Overloaded function.

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

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

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

Parameters:

xy (WordGraph) – the word graph to store the result.
x (WordGraph) – the first word graph to meet.
xroot (int) – the node to use as a root in x.
y (WordGraph) – the second word graph to meet.
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: Meeter, xy: WordGraph, x: WordGraph, y: WordGraph) → None

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

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

Parameters:

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

Raises:

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

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

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

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

Parameters:

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

Returns:

The meet 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().

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

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

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

Parameters:

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

Returns:

The meet of x and 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().

copy(self: Meeter) → Meeter

Copy a Meeter object.

Returns:: A copy.
Return type:: Meeter

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

Overloaded function.

is_subrelation(self: Meeter, 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: Meeter, 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().