monoid_ideals.h File Reference

Computations of ideals in monoids. More...

#include <stdbool.h>
#include "monoid.h"

Go to the source code of this file.

Functions
dequeue *	compute_r_ideal (morphism *, uint, bool *)
	Computation of the right ideal of an element.
dequeue *	compute_l_ideal (morphism *, uint, bool *)
	Computation of the left ideal of an element.
dequeue *	compute_j_ideal (morphism *, uint, bool *)
	Computation of the two-sided ideal of an element.
dequeue *	compute_r_ideal_alph (morphism *, uint, bool *, bool *)
	Computation of a given restricted right ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.
dequeue *	compute_l_ideal_alph (morphism *, uint, bool *, bool *)
	Computation of a given restricted left ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.
dequeue *	compute_j_ideal_alph (morphism *, uint, bool *, bool *)
	Computation of a given restricted left/right ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.
uint	get_rlink (morphism *, parti *, uint, uint, bool *alpha)
	Given an idempotent g and an element q such that g R q, compute an element s such that g = qr.
uint	get_llink (morphism *, parti *, uint, uint, bool *alpha)
	Given an idempotent h and an element t such that h R t, compute an element s such that h = st.

Detailed Description

Computations of ideals in monoids.

Function Documentation

compute_j_ideal()

dequeue * compute_j_ideal	(	morphism *	M,
		uint	s,
		bool *	rest )

Computation of the two-sided ideal of an element.

Remarks

The third parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The two-sided ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

compute_j_ideal_alph()

dequeue * compute_j_ideal_alph	(	morphism *	M,
		uint	s,
		bool *	alph,
		bool *	rest )

Computation of a given restricted left/right ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.

Remarks

The fourth parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The restricted left ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
alph	An array of Booleans indexed by the letters. Marks the letters inside the sub-alphabet
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

compute_l_ideal()

dequeue * compute_l_ideal	(	morphism *	M,
		uint	s,
		bool *	rest )

Computation of the left ideal of an element.

Remarks

The third parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The left ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

compute_l_ideal_alph()

dequeue * compute_l_ideal_alph	(	morphism *	M,
		uint	s,
		bool *	alph,
		bool *	rest )

Computation of a given restricted left ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.

Remarks

The fourth parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The restricted left ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
alph	An array of Booleans indexed by the letters. Marks the letters inside the sub-alphabet
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

compute_r_ideal()

dequeue * compute_r_ideal	(	morphism *	M,
		uint	s,
		bool *	rest )

Computation of the right ideal of an element.

Remarks

The third parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The right ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

compute_r_ideal_alph()

dequeue * compute_r_ideal_alph	(	morphism *	M,
		uint	s,
		bool *	alph,
		bool *	rest )

Computation of a given restricted right ideal of an element. The restriction is given by a sub-alphabet: the only available transitions are those labeled by a letter in this sub-alphabet.

Remarks

The fourth parameter is an array of Booleans indexed by the elements of the monoid. It restricts the elements in the returned list to those which are marked true by the array. When no restriction is needed a NULL pointer should be given as input.

Returns

The restricted right ideal sorted in increasing order.

Parameters

M	The morphism.
s	The element
alph	An array of Booleans indexed by the letters. Marks the letters inside the sub-alphabet
rest	An array of Booleans indexed by the elements. Can be used to restrict the output.

get_llink()

uint get_llink	(	morphism *	M,
		parti *	L,
		uint	h,
		uint	t,
		bool *	alpha )

Given an idempotent h and an element t such that h R t, compute an element s such that h = st.

Returns

The element s.

Parameters

M	The morphism.
L	The L-classes.
h	Idempotent.
t	Start element.
alpha	An array of Booleans indexed by the letters: search a ling over this alphabet (NULL if not used).

get_rlink()

uint get_rlink	(	morphism *	M,
		parti *	R,
		uint	g,
		uint	r,
		bool *	alpha )

Given an idempotent g and an element q such that g R q, compute an element s such that g = qr.

Returns

The element r.

Parameters

M	The morphism.
R	The R-classes.
g	Idempotent.
r	Start element.
alpha	An array of Booleans indexed by the letters: search a ling over this alphabet (NULL if not used).