Tests of properties on morphisms. More...

#include <stdbool.h>
#include <stdlib.h>
#include "nfa.h"
#include "monoid.h"
#include "monoid_orbits.h"
#include "monoid_kernels.h"
#include "sep_group.h"

Enumerations
enum	green_relation { H_GREEN , L_GREEN , R_GREEN , J_GREEN }
	The four Green relations.

Functions
bool	is_trivial_monoid (morphism , uint )
	Tests if a monoid is trivial.

bool	is_trivial_semigroup (morphism , uint )
	Tests if a semigroup (image of A⁺) is trivial.

bool	is_trivial_subsemi (subsemi , uint )
	Tests if a subsemigroup is trivial.

bool	is_trivial_orbmono (orbits , uint )
	Tests if all orbits are trivial.

bool	is_group_mono (morphism , uint )
	Tests if a monoid is a group.

bool	is_group_semigroup (morphism , uint )
	Tests if a semigroup (image of A⁺) is a group.

bool	is_group_subsemi (subsemi , uint )
	Tests if a subsemigroup is a group.

bool	is_group_orbmono (orbits , uint )
	Tests if all orbits are groups.

bool	is_letterind_mono (morphism , uint )
	Tests if a morphism maps all letters to the same element.

bool	is_comm_mono (morphism , uint )
	Tests is a monoid is commutative.

bool	is_comm_subsemi (subsemi , uint )
	Tests is a subsemigroup is commutative.

bool	is_com_orbmono (orbits , uint )
	Tests if all orbits are commutative.

bool	is_comm_ltt_mono (orbits , uint )
	Tests if a morphism satisfies the specific commutativity equation of the class LTT.

bool	is_idem_mono (morphism , uint )
	Tests if a monoid is idempotent.

bool	is_idem_subsemi (subsemi , uint )
	Tests if a subsemigroup is idempotent.

bool	is_idem_orbmono (orbits , uint )
	Tests if all orbits are simultaneously commutative and idempotent.

parti *	grel_to_parti (green *G, green_relation P)

bool	is_gtrivial_mono (morphism , green_relation, uint )
	Tests if a monoid is P-trivial where P is one of the four Green relations (H,R,L,J).

bool	is_gtrivial_subsemi (subsemi , green_relation, uint )
	Tests if a subsemigroup is P-trivial where P is one of the four Green relations (H,R,L,J).

bool	is_gtrivial_orbmono (orbits , green_relation, uint )
	Tests if all orbits are P-trivial where P is one of the four Green relations (H,R,L,J).

bool	is_htrivial_generators (morphism , uint )
	Tests if the H-classes of 1 and all generators are trivial.

bool	is_da_mono (morphism , uint )
	Tests if a monoid is in DA.

bool	is_da_subsemi (subsemi , uint )
	Tests is a subsemigroup is in DA.

bool	is_da_orbmono (orbits , uint )
	Tests if all orbits are in DA.

bool	is_jsat_mono (morphism , uint )
	Tests if a morphism satisfies the equation 1 ≤ s.

bool	is_ejsat_mono (morphism , uint )
	Tests if a morphism satisfies the equation 1 ≤ e (for every idempotent e).

bool	is_jsat_subsemi (subsemi , uint, uint )
	Tests if a subsemigroup satisfies the equation 1 ≤ s.

bool	is_jsat_orbmono (orbits , uint )
	Tests if all orbits satisfy the equation 1 ≤ s.

bool	is_blockg_mono (morphism , uint )
	Tests if a monoid is a block group.

bool	is_bpolmod_mono (morphism , uint )
	Tests if a morphism satisfies the BPol(MOD) equation.

bool	is_bpolamt_mono (morphism , uint )
	Tests if a morphism satisfies the BPol(AMT) equation.

bool	is_knast_mono (orbits , uint )
	Tests if a morphism satisfies Knast's equation.

bool	is_knast_ker (orbits , subsemi , uint *)
	Tests if the G-kernel satisfies Knast's equation for a group vari G.

bool	is_bpolamtp_mono (orbits , uint )
	Tests if a morphism satisfies the BPol(AMT⁺) equation.

bool	is_bpolgrp_mono (orbits , uint )
	Tests if a morphism satisfies the BPol(GR⁺) equation.

bool	is_knast_at_mono (morphism M, uint cexa)
	Tests if a morphism satisfies the AT-variant of Knast's equation.

bool	is_upbp_mono (orbits , uint )
	Tests if a morphism satisfies the UPol(BPol(C)) equation for a given class C. The C-orbits are taken as input.

Variables
char	green_rel_array [4]

Detailed Description

Tests of properties on morphisms.

Tests of properties on automata.

Function Documentation

◆ is_blockg_mono()

bool is_blockg_mono	(	morphism *	M,
		uint *	c )

Tests if a monoid is a block group.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two idempotents that are either L- or R-equivalent.

Returns: A Boolean indicating whether the monoide is a block group.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_bpolamt_mono()

bool is_bpolamt_mono	(	morphism *	M,
		uint *	cexa )

Tests if a morphism satisfies the BPol(AMT) equation.

Remarks: Takes the AMT-kernel as input. We first check if it is J-trivial as this is faster.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t that do not satisfy the equation.

Returns: A Boolean indicating whether the morphisme satisfies the BPol(AMT) equation.

Parameters

M	The morphism.
cexa	Pointer on a uint array to return a counterexample.

◆ is_bpolamtp_mono()

bool is_bpolamtp_mono	(	orbits *	L,
		uint *	cexa )

Tests if a morphism satisfies the BPol(AMT⁺) equation.

Remarks: Takes the AMT⁺-orbits as input.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether the morphisme satisfies the BPol(AMT⁺) equation.

Parameters

L	The AMT⁺-orbits.
cexa	Pointer on a uint array to return a counterexample.

◆ is_bpolgrp_mono()

bool is_bpolgrp_mono	(	orbits *	L,
		uint *	cexa )

Tests if a morphism satisfies the BPol(GR⁺) equation.

Remarks: Takes the GR⁺-orbits as input.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether the morphisme satisfies the BPol(GR⁺) equation.

Parameters

L	The GR⁺-orbits.
cexa	Pointer on a uint array to return a counterexample.

◆ is_bpolmod_mono()

bool is_bpolmod_mono	(	morphism *	M,
		uint *	cexa )

Tests if a morphism satisfies the BPol(MOD) equation.

Remarks: Takes the MOD-kernel as input. We first check if it is J-trivial as this is faster.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t that do not satisfy the equation.

Returns: A Boolean indicating whether the morphisme satisfies the BPol(MOD) equation.

Parameters

M	The MOD-kernel.
cexa	Pointer on a uint array to return a counterexample.

◆ is_com_orbmono()

bool is_com_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits are commutative.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that do not commute plus the idempotent defining the orbit.

Returns: A Boolean indicating whether the orbits are commuatative.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_comm_ltt_mono()

bool is_comm_ltt_mono	(	orbits *	L,
		uint *	c )

Tests if a morphism satisfies the specific commutativity equation of the class LTT.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether the equation is satisfied.

Parameters

L	The DD-orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_comm_mono()

bool is_comm_mono	(	morphism *	M,
		uint *	c )

Tests is a monoid is commutative.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that do not commute.

Returns: A Boolean indicating whether the monoid is commutative.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_comm_subsemi()

bool is_comm_subsemi	(	subsemi *	S,
		uint *	c )

Tests is a subsemigroup is commutative.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that do not commute.

Returns: A Boolean indicating whether the subsemigroup is commutative.

Parameters

S	The subsemigroup.
c	Pointer on a uint array to return a counterexample.

◆ is_da_mono()

bool is_da_mono	(	morphism *	M,
		uint *	c )

Tests if a monoid is in DA.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: a regular element which is not idempotent.

Returns: A Boolean indicating whether the monoide is in DA.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_da_orbmono()

bool is_da_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits are in DA.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: a regular element which is not idempotent plus the idempotent defining the orbit.

Returns: A Boolean indicating whether all orbits are in DA.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_da_subsemi()

bool is_da_subsemi	(	subsemi *	S,
		uint *	c )

Tests is a subsemigroup is in DA.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: a regular element which is not idempotent.

Returns: A Boolean indicating whether the subsemigroupe is in DA.

Parameters

S	The subsemigroup.
c	Pointer on a uint array to return a counterexample.

◆ is_ejsat_mono()

bool is_ejsat_mono	(	morphism *	M,
		uint *	c )

Tests if a morphism satisfies the equation 1 ≤ e (for every idempotent e).

Remarks: The order must be computed before calling this function.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the idempotent e which fails the equation.

Returns: A Boolean indicating whether the morphisme satisfies the equation 1 ≤ e (for every idempotent e).

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_group_mono()

bool is_group_mono	(	morphism *	M,
		uint *	c )

Tests if a monoid is a group.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample (an element with no inverse).

Returns: A Boolean indicating whether the monoid is a group.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_group_orbmono()

bool is_group_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits are groups.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: an element with no inverse plus the idempotent defining the orbit.

Returns: A Boolean indicating whether all orbits are groups.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_group_semigroup()

bool is_group_semigroup	(	morphism *	M,
		uint *	c )

Tests if a semigroup (image of A⁺) is a group.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements in the semigroup which are not J-equivalent.

Returns: A Boolean indicating whether the syntactic semigroup is a group.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_group_subsemi()

bool is_group_subsemi	(	subsemi *	S,
		uint *	c )

Tests if a subsemigroup is a group.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: an element with no inverse.

Returns: A Boolean indicating whether the subsemigroup is a group.

Parameters

S	The subsemigroup.
c	Pointer on a uint array to return a counterexample.

◆ is_gtrivial_mono()

bool is_gtrivial_mono	(	morphism *	M,
		green_relation	P,
		uint *	c )

Tests if a monoid is P-trivial where P is one of the four Green relations (H,R,L,J).

If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that are P-equivalent (the first is idempotent).

Returns: A Boolean indicating whether the monoide is P-trivial.

Parameters

M	The morphism.
P	The relation to test (H,R,L or J).
c	Pointer on a uint array to return a counterexample.

◆ is_gtrivial_orbmono()

bool is_gtrivial_orbmono	(	orbits *	L,
		green_relation	P,
		uint *	c )

Tests if all orbits are P-trivial where P is one of the four Green relations (H,R,L,J).

If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that are P-equivalent (the first is idempotent) plus the idempotent defining the orbit.

Returns: A Boolean indicating whether all orbits are P-trivial.

Parameters

L	The orbits.
P	The relation to test (H,R,L or J).
c	Pointer on a uint array to return a counterexample.

◆ is_gtrivial_subsemi()

bool is_gtrivial_subsemi	(	subsemi *	S,
		green_relation	P,
		uint *	c )

Tests if a subsemigroup is P-trivial where P is one of the four Green relations (H,R,L,J).

If the test fails and the second parameter is not NULL, it will be set to a counterexample: two elements that are P-equivalent (the first is idempotent).

Returns: A Boolean indicating whether the subsemigroupe is P-trivial.

Parameters

S	Le subsemigroup.
P	The relation to test (H,R,L or J).
c	Pointer on a uint array to return a counterexample.

◆ is_htrivial_generators()

bool is_htrivial_generators	(	morphism *	M,
		uint *	c )

Tests if the H-classes of 1 and all generators are trivial.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample.

Returns: A Boolean indicating whether the H-classes of 1 and all generators are trivial.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_idem_mono()

bool is_idem_mono	(	morphism *	M,
		uint *	c )

Tests if a monoid is idempotent.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: an element that is not idempotent.

Returns: A Boolean indicating whether the monoid is idempotent.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_idem_orbmono()

bool is_idem_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits are simultaneously commutative and idempotent.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: an element that is not idempotent plus the idempotent defining the orbit.

Returns: A Boolean indicating whether the orbits are simultaneously commutative and idempotent.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_idem_subsemi()

bool is_idem_subsemi	(	subsemi *	S,
		uint *	c )

Tests if a subsemigroup is idempotent.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: an element that is not idempotent.

Returns: A Boolean indicating whether the subsemigroup is idempotent.

Parameters

S	The subsemigroup.
c	Pointer on a uint array to return a counterexample.

◆ is_jsat_mono()

bool is_jsat_mono	(	morphism *	M,
		uint *	c )

Tests if a morphism satisfies the equation 1 ≤ s.

Remarks: The order must be computed before calling this function.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the element s which fails the equation.

Returns: A Boolean indicating whether si the morphism satisfies the equation 1 ≤ s.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_jsat_orbmono()

bool is_jsat_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits satisfy the equation 1 ≤ s.

Remarks: The order must be computed before calling this function.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the element s which fails the equation plus the idempotent defining the orbit.

Returns: A Boolean indicating whether all orbits satisfy the equation 1 ≤ s.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_jsat_subsemi()

bool is_jsat_subsemi	(	subsemi *	S,
		uint	ind,
		uint *	c )

Tests if a subsemigroup satisfies the equation 1 ≤ s.

Remarks: The order must be computed before calling this function.; If the test fails and the third parameter is not NULL, it will be set to a counterexample: the element s which fails the equation.

Returns: A Boolean indicating whether the subsemigroup satisfies the equation 1 ≤ s.

Parameters

S	The subsemigroup.
ind	The index of the neutral element in the list of representative idempotents.
c	Pointer on a uint array to return a counterexample.

◆ is_knast_at_mono()

bool is_knast_at_mono	(	morphism *	M,
		uint *	cexa )

Tests if a morphism satisfies the AT-variant of Knast's equation.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether si the morphism satisfies the AT-variant of Knast's equation.

Parameters

M	The morphism.
cexa	Pointer on a uint array to return a counterexample.

◆ is_knast_ker()

bool is_knast_ker	(	orbits *	L,
		subsemi *	ker,
		uint *	cexa )

Tests if the G-kernel satisfies Knast's equation for a group vari G.

Remarks: Takes the G⁺-orbits as input.; If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether the MOD-kernel satisfies Knast's equation.

Parameters

L	The G⁺-orbits.
ker	The G-kernel.
cexa	Pointer on a uint array to return a counterexample.

◆ is_knast_mono()

bool is_knast_mono	(	orbits *	L,
		uint *	cexa )

Tests if a morphism satisfies Knast's equation.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements q,r,s,t,e,f that do not satisfy the equation.

Returns: A Boolean indicating whether the morphism satisfies Knast's equation.

Parameters

L	The DD-orbits of the morphism.
cexa	Pointer on a uint array to return a counterexample.

◆ is_letterind_mono()

bool is_letterind_mono	(	morphism *	M,
		uint *	c )

Tests if a morphism maps all letters to the same element.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: a letter which has a distinct image than the letter of index 0.

Returns: A Boolean indicating whether the morphism maps all letters to the same element.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_trivial_monoid()

bool is_trivial_monoid	(	morphism *	M,
		uint *	c )

Tests if a monoid is trivial.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two distinct elements in the monoid.

Returns: A Boolean indicating whether the monoid is trivial.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_trivial_orbmono()

bool is_trivial_orbmono	(	orbits *	L,
		uint *	c )

Tests if all orbits are trivial.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two distinct elements in an orbit plus the idempotent defining this orbit.

Returns: A Boolean indicating whether all orbits are trivial.

Parameters

L	The orbits.
c	Pointer on a uint array to return a counterexample.

◆ is_trivial_semigroup()

bool is_trivial_semigroup	(	morphism *	M,
		uint *	c )

Tests if a semigroup (image of A⁺) is trivial.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two distinct elements in the semigroup.

Returns: A Boolean indicating whether the syntactic semigroup is trivial.

Parameters

M	The morphism.
c	Pointer on a uint array to return a counterexample.

◆ is_trivial_subsemi()

bool is_trivial_subsemi	(	subsemi *	S,
		uint *	c )

Tests if a subsemigroup is trivial.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: two distinct elements in the subsemigroup.

Returns: A Boolean indicating whether the subsemigroup is trivial.

Parameters

S	The subsemigroup.
c	Pointer on a uint array to return a counterexample.

◆ is_upbp_mono()

bool is_upbp_mono	(	orbits *	L,
		uint *	cexa )

Tests if a morphism satisfies the UPol(BPol(C)) equation for a given class C. The C-orbits are taken as input.

Remarks: If the test fails and the second parameter is not NULL, it will be set to a counterexample: the elements s,t,e that do not satisfy the equation.

Returns: A Boolean indicating whether si the morphism satisfies the UPol(BPol(C)) equation.

Parameters

L	The C-orbits of the morphism.
cexa	Pointer on a uint array to return a counterexample.

Enumerations

Functions

Variables

Detailed Description

Function Documentation

◆ is_blockg_mono()

◆ is_bpolamt_mono()

◆ is_bpolamtp_mono()

◆ is_bpolgrp_mono()

◆ is_bpolmod_mono()

◆ is_com_orbmono()

◆ is_comm_ltt_mono()

◆ is_comm_mono()

◆ is_comm_subsemi()

◆ is_da_mono()

◆ is_da_orbmono()

◆ is_da_subsemi()

◆ is_ejsat_mono()

◆ is_group_mono()

◆ is_group_orbmono()

◆ is_group_semigroup()

◆ is_group_subsemi()

◆ is_gtrivial_mono()

◆ is_gtrivial_orbmono()

◆ is_gtrivial_subsemi()

◆ is_htrivial_generators()

◆ is_idem_mono()

◆ is_idem_orbmono()

◆ is_idem_subsemi()

◆ is_jsat_mono()

◆ is_jsat_orbmono()

◆ is_jsat_subsemi()

◆ is_knast_at_mono()

◆ is_knast_ker()

◆ is_knast_mono()

◆ is_letterind_mono()

◆ is_trivial_monoid()

◆ is_trivial_orbmono()

◆ is_trivial_semigroup()

◆ is_trivial_subsemi()

◆ is_upbp_mono()