Computations of congruences on monoids. Deterministic hierarchies. More...

#include <stdbool.h>
#include <stdlib.h>
#include "type_dlist.h"
#include "sep_group.h"
#include "nfa.h"
#include "nfa_intersec.h"
#include "monoid.h"
#include "monoid_ideals.h"
#include "monoid_props.h"

Functions
void	compute_leastcong (morphism , ufind )
	Computation of the least congruence that contains a given partition.

ufind *	iden_green_mono (morphism *, green_relation)
	Computes the least congruence containing one of the four Green relations.

ufind *	iden_green_subsemi (subsemi *, green_relation)
	Computes the least congruence which identifies all elements equivalent for a given Green relation inside the subsemigroup given as input.

ufind *	iden_green_orbmono (orbits *, green_relation)
	Computes the least congruence which identifies all elements equivalent for a given Green relation inside the orbits given as input.

ufind *	iden_bpolmod_mono (morphism *)
	Returns the least congruence satisfying the BPol(MOD) equation.

ufind *	iden_bpolamt_mono (morphism *)
	Returns the least congruence satisfying the BPol(AMT) equation.

ufind *	iden_blockg_mono (morphism *)
	Returns the least congruence satisfying the BPol(GR) equation (Block group).

ufind *	iden_knast_mono (orbits *)
	Returns the least congruence satisfying the BPol(DD) equation (Knast).

ufind *	iden_qknast_mono (orbits , subsemi )
	Returns the least congruence satisfying the BPol(MOD⁺) equation (Knast on the MOD-Kernel).

ufind *	iden_bpolamtp_mono (orbits *)
	Returns the least congruence satisfying the BPol(AMT⁺) equation.

ufind *	iden_bpolgrp_mono (orbits *)
	Returns the least congruence satisfying the BPol(GR⁺) equation.

ufind *	iden_mpolc_mono (morphism , parti )
	Returns the equivalence obtained by identifying the elements which should be equal according to the MPol(C)-equation. Takes the canonical C-congruence as input.

ufind *	iden_lpolc_mono (morphism , parti )
	Returns the equivalence obtained by identifying the elements which should be equal according to the LPol(C)-equation. Takes the canonical C-congruence as input.

ufind *	iden_rpolc_mono (morphism , parti )
	Returns the equivalence obtained by identifying the elements which should be equal according to the RPol(C)-equation. Takes the canonical C-congruence as input.

void	hdet_lrpol_level (morphism , ufind , FILE , short , short *)
	Computes the levels of a syntactic morphism in the LPol(C) and the RPol(C)-hierarchies: RPol(C),LPol(C) = 1, RPol₂(C),LPol₂(C) = 2...

Detailed Description

Computations of congruences on monoids. Deterministic hierarchies.

Function Documentation

◆ compute_leastcong()

void compute_leastcong	(	morphism *	M,
		ufind *	uf )

Computation of the least congruence that contains a given partition.

Remarks: The partition is given a a union-find partition which is made into the congruence by the function.

Parameters

M	The morphism.
uf	The union-find partition.

◆ hdet_lrpol_level()

void hdet_lrpol_level	(	morphism *	M,
		ufind *	C,
		FILE *	out,
		short *	minf,
		short *	minp )

Computes the levels of a syntactic morphism in the LPol(C) and the RPol(C)-hierarchies: RPol(C),LPol(C) = 1, RPol₂(C),LPol₂(C) = 2...

Remarks: Details of the computation can be displayed on an input stream. It should be set to NULL if no details are desired.

Attention: The levels are returned using pointers

Parameters

M	The morphism.
C	The canonical C-congruence.
out	The stream.
minf	Pointer used to return the level in the LPol hierarchy.
minp	Pointer used to return the level in the RPol hierarchy.

◆ iden_blockg_mono()

ufind * iden_blockg_mono ( morphism * M )

Returns the least congruence satisfying the BPol(GR) equation (Block group).

Returns: The congruence given as a union-find partition.

Parameters

M	The morphism.

◆ iden_bpolamt_mono()

ufind * iden_bpolamt_mono ( morphism * M )

Returns the least congruence satisfying the BPol(AMT) equation.

Returns: The congruence given as a union-find partition.

Parameters

M	The morphism.

◆ iden_bpolamtp_mono()

ufind * iden_bpolamtp_mono ( orbits * L )

Returns the least congruence satisfying the BPol(AMT⁺) equation.

Returns: The congruence given as a union-find partition.

Parameters

L	The AMT⁺-orbits.

◆ iden_bpolgrp_mono()

ufind * iden_bpolgrp_mono ( orbits * L )

Returns the least congruence satisfying the BPol(GR⁺) equation.

Returns: The congruence given as a union-find partition.

Parameters

L	The GR⁺-orbits.

◆ iden_bpolmod_mono()

ufind * iden_bpolmod_mono ( morphism * M )

Returns the least congruence satisfying the BPol(MOD) equation.

Returns: The congruence given as a union-find partition.

Parameters

M	The morphism.

◆ iden_green_mono()

ufind * iden_green_mono	(	morphism *	M,
		green_relation	grel )

Computes the least congruence containing one of the four Green relations.

Returns: The congruence given as a union-find partition.

Parameters

M	The morphism.
grel	The Green relation.

◆ iden_green_orbmono()

ufind * iden_green_orbmono	(	orbits *	L,
		green_relation	grel )

Computes the least congruence which identifies all elements equivalent for a given Green relation inside the orbits given as input.

Returns: The congruence given as a union-find partition.

Parameters

L	The orbits.
grel	The relation to be identified.

◆ iden_green_subsemi()

ufind * iden_green_subsemi	(	subsemi *	S,
		green_relation	grel )

Computes the least congruence which identifies all elements equivalent for a given Green relation inside the subsemigroup given as input.

Returns: The congruence given as a union-find partition.

Parameters

S	The subsemigroup.
grel	The relation to be identified.

◆ iden_knast_mono()

ufind * iden_knast_mono ( orbits * L )

Returns the least congruence satisfying the BPol(DD) equation (Knast).

Returns: The congruence given as a union-find partition.

Parameters

L	The DD-orbits.

◆ iden_lpolc_mono()

ufind * iden_lpolc_mono	(	morphism *	M,
		parti *	C )

Returns the equivalence obtained by identifying the elements which should be equal according to the LPol(C)-equation. Takes the canonical C-congruence as input.

Remarks: Should be combined with the function "compute_leastcong" to compute the canonical LPol(C)-congruence of the morphism.

Returns: The equivalence given as a union-find partition.

Parameters

M	The morphism.
C	The canonical C-congruence.

◆ iden_mpolc_mono()

ufind * iden_mpolc_mono	(	morphism *	M,
		parti *	C )

Returns the equivalence obtained by identifying the elements which should be equal according to the MPol(C)-equation. Takes the canonical C-congruence as input.

Remarks: Should be combined with the function "compute_leastcong" to compute the canonical MPol(C)-congruence of the morphism.

Returns: The equivalence given as a union-find partition.

Parameters

M	The morphism.
C	The canonical C-congruence.

◆ iden_qknast_mono()

ufind * iden_qknast_mono	(	orbits *	L,
		subsemi *	mker )

Returns the least congruence satisfying the BPol(MOD⁺) equation (Knast on the MOD-Kernel).

Returns: The congruence given as a union-find partition.

Parameters

L	The MOD⁺-orbits
mker	The MOD-kernel.

◆ iden_rpolc_mono()

ufind * iden_rpolc_mono	(	morphism *	M,
		parti *	C )

Returns the equivalence obtained by identifying the elements which should be equal according to the RPol(C)-equation. Takes the canonical C-congruence as input.

Remarks: Should be combined with the function "compute_leastcong" to compute the canonical RPol(C)-congruence of the morphism.

Returns: The equivalence given as a union-find partition.

Parameters

M	The morphism.
C	The canonical C-congruence.

Functions

Detailed Description

Function Documentation

◆ compute_leastcong()

◆ hdet_lrpol_level()

◆ iden_blockg_mono()

◆ iden_bpolamt_mono()

◆ iden_bpolamtp_mono()

◆ iden_bpolgrp_mono()

◆ iden_bpolmod_mono()

◆ iden_green_mono()

◆ iden_green_orbmono()

◆ iden_green_subsemi()

◆ iden_knast_mono()

◆ iden_lpolc_mono()

◆ iden_mpolc_mono()

◆ iden_qknast_mono()

◆ iden_rpolc_mono()