Implementation of morphisms into finite monoids. More...

#include "graphs.h"
#include "nfa.h"
#include "tools.h"
#include "type_abr.h"
#include "type_basic.h"
#include "type_binheap.h"
#include "type_dequeue.h"
#include "type_dequeue_gen.h"
#include "graphs_tarjan.h"
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

Classes
struct	green
	Type used to represent the Green relations of a finite monoid. More...

struct	morphism
	The type used to represent a morphism into a finite monoid. More...

Macros
#define	max(a, b)

#define	min(a, b)

#define	ONE 0
	In every monoid, the neutral element is at index 0.

Functions
void	delete_green (green *)
	Release of the Green relations.

void	delete_morphism (morphism *)
	Release of a morphism.

letter *	mor_duplicate_alpha (const morphism *)
	Copy the alphabet of a morphism.

uint	mor_letter_index (const morphism *, letter)
	Retrieves the index of a letter in the alphabet of a morphism.

uint	mor_regular_jclass (const morphism *, uint)
	Given as input a regular element, retrieves the index of the.

void	mor_compute_leftcayley (morphism *)
	Computation of the left Cayley graph of a morphism.

uint *	green_sorted_jclass (green *, uint)
	Computes an array containing all elements in a given J-class sorted according to the indices of their R-class (first) and L-classes (second).

void	h_green_compute (green *)
	Computation of the relation H from J, L and R (which must be already computed).

void	gr_green_compute (uint , uint, green )
	Computation of informations on regular elements and groups (the Green relations themselves must be already computed).

void	mor_compute_rep (morphism *)
	Computation of list of representative idempotents for the morphism.

void	mor_compute_green (morphism *)
	Allocates and computes the Green relations of a morphism.

void	mor_compute_min_regular_jcl (morphism *)
	Computation of the number of strict J-classes.

morphism *	dfa_to_morphism (dfa , bool, int , uint **)
	Computation of the transition morphism associated to a complete DFA.

uint	dfa_to_morphism_size (dfa *A)
	Computes the size of the morphism associated to a complete DFA without storing the actual morphism.

dfa *	morphism_to_dfa (morphism *)
	Computation of a complete DFA from the right Cayley graph of a morphism.

dfa *	left_morphism_to_dfa (morphism *)
	Computation of a complete DFA from the left Cayley graph of a morphism.

void	mor_compute_mult (morphism *)
	Computation of the multiplication table of a morphism.

lgraph *	mor_rmirror (morphism *)
	Computation of the mirror of the right Cayley graph.

lgraph *	mor_lmirror (morphism *)
	Computation of the mirror of the left Cayley graph.

dequeue **	mor_compute_order (morphism *)
	Computation of the syntactic order table of a morphism.

dequeue *	mor_name (morphism *, uint)
	Return the name of an element (product of generators) in a dequeue.

uint	mor_mult (morphism *, uint, uint)
	Multiplication of two elements.

uint	mor_mult_gen (morphism *, uint,...)
	Multiplication of an arbitrary number of elements.

uint	mor_omega (morphism *, uint)
	Computes the omega power of an element.

bool	mor_num_idem (morphism , uint, uint )
	Computes the index of an idempotent element.

bool	mor_neutral_letter (morphism , FILE )
	Tests if there exists a letter mapped to the neutral element.

bool	mor_nonempty_neutral (morphism *)
	Tests if there exists a nonempty antecedent of the neutral element in a morphism.

bool	mor_all_regular (morphism *)
	Tests if all elements in a morphism are regular.

uint	mor_compute_image (morphism , word )
	Computes the image of a word.

dgraph *	mor_extract_rcl (morphism *M, uint rcl)
	Returns the graph of a single R-class.

Detailed Description

Implementation of morphisms into finite monoids.

Contains the definition of the types "green" and "morphism". The type "green" is used to represent the Green relations of a finite monoid. The type "morphism" is used to represent a morphism into a finite monoid (it includes the Green relations of this monoid). Includes the functions used to create new morphisms and their Green relations from a complete DFA as well as the function manipulating morphisms.

Macro Definition Documentation

◆ max

#define max	(		a,
			b )

Value:

(((a) > (b)) ? (a) : (b))

◆ min

#define min	(		a,
			b )

Value:

(((a) < (b)) ? (a) : (b))

Function Documentation

◆ delete_green()

void delete_green ( green * G )

Release of the Green relations.

Parameters

G	The Green relations.

◆ delete_morphism()

void delete_morphism ( morphism * M )

Release of a morphism.

Parameters

M	The morphism.

◆ dfa_to_morphism()

morphism * dfa_to_morphism	(	dfa *	A,
		bool	order,
		int *	,
		uint **	funs )

Computation of the transition morphism associated to a complete DFA.

Remarks: The ordering on the elements of the DFA is used to compute partial information on the corresponding ordering on the elements of the morphism. For each J-class, if e is the idempotent representing this J-class, then all elements larger than e for the ordering and for the H-order are computed (this is enough for all the membership tests). If the ordering is NULL, nothing is computed for the morphism.

Returns: The transition morphism.

Parameters

A	The complete DFA.
order	Should the ordering on the elements of the morphism be computed ? (only works for minimal input DFAs)
funs	A pointer to return function table used to construct the monoid (NULL if not used).

◆ dfa_to_morphism_size()

uint dfa_to_morphism_size ( dfa * A )

Computes the size of the morphism associated to a complete DFA without storing the actual morphism.

Returns: The size of the morphism.

Parameters

A	The complete DFA.

◆ gr_green_compute()

void gr_green_compute	(	uint *	idem_list,
		uint	nb_idems,
		green *	G )

Computation of informations on regular elements and groups (the Green relations themselves must be already computed).

Remarks: The computation requires the list of idempotent elements.

Parameters

idem_list	The list of idempotents.
nb_idems	The number of idempotents.
G	The Green relations.

◆ green_sorted_jclass()

uint * green_sorted_jclass	(	green *	G,
		uint	i )

Computes an array containing all elements in a given J-class sorted according to the indices of their R-class (first) and L-classes (second).

Returns: The sorted array.

Parameters

G	The Green relations.
i	The index of the J-class.

◆ h_green_compute()

void h_green_compute ( green * GREL )

Computation of the relation H from J, L and R (which must be already computed).

Parameters

GREL	The Green relations (J, R et L must be computed).

◆ left_morphism_to_dfa()

dfa * left_morphism_to_dfa ( morphism * M )

Computation of a complete DFA from the left Cayley graph of a morphism.

Returns: The complete DFA.

Parameters

M	The morphism.

◆ mor_all_regular()

bool mor_all_regular ( morphism * M )

Tests if all elements in a morphism are regular.

Returns: A Boolean indicating whether all elements are regular.

Parameters

M	The morphism.

◆ mor_compute_green()

void mor_compute_green ( morphism * M )

Allocates and computes the Green relations of a morphism.

Remarks: All other mandatorty fields of the morphism must have been computed.

Parameters

M	The morphism.

◆ mor_compute_image()

uint mor_compute_image	(	morphism *	M,
		word *	w )

Computes the image of a word.

Remarks: If the word is not defined over the alphabet of the morphism, the (invalid) element M->r_cayley->size_graph is returned.

Returns: The image

Parameters

M	The morphism.
w	The word.

◆ mor_compute_leftcayley()

void mor_compute_leftcayley ( morphism * M )

Computation of the left Cayley graph of a morphism.

Remarks: The right Cayley graph of the morphism must be computed.

Parameters

M	The morphism.

◆ mor_compute_min_regular_jcl()

void mor_compute_min_regular_jcl ( morphism * )

Computation of the number of strict J-classes.

Remarks: The Green relations must have been computed.

◆ mor_compute_mult()

void mor_compute_mult ( morphism * M )

Computation of the multiplication table of a morphism.

Remarks: The computation is only made if the multiplication table has not already been computed.

Parameters

M	The morphism.

◆ mor_compute_order()

dequeue ** mor_compute_order ( morphism * M )

Computation of the syntactic order table of a morphism.

Attention: The morphism has to be a syntactic morphism.

Remarks: The computation is only made if the syntactic order has not already been computed.

Parameters

M	The morphism.

◆ mor_compute_rep()

void mor_compute_rep ( morphism * M )

Computation of list of representative idempotents for the morphism.

Remarks: The computation requires the full computation of the Green relations.

◆ mor_duplicate_alpha()

letter * mor_duplicate_alpha ( const morphism * M )

Copy the alphabet of a morphism.

Returns: A copy of the alphabet array.

Parameters

M	The morphism.

◆ mor_extract_rcl()

dgraph * mor_extract_rcl	(	morphism *	M,
		uint	rcl )

Returns the graph of a single R-class.

Remarks: Transitions that go out of the R-class are mapped to UINT_MAX.

Returns: The graph of the R-class.

Parameters

M	The morphism.
rcl	The index of the R-class.

◆ mor_letter_index()

uint mor_letter_index	(	const morphism *	M,
		letter	l )

Retrieves the index of a letter in the alphabet of a morphism.

Remarks: If the letter does not belong to the alphabet the invalid index UINT_MAX is returned.

Returns: The index of the letter.

Parameters

M	The morphism.
l	The letter.

◆ mor_lmirror()

lgraph * mor_lmirror ( morphism * M )

Computation of the mirror of the left Cayley graph.

Returns: The mirror.

Parameters

M	The morphism.

◆ mor_mult()

uint mor_mult	(	morphism *	M,
		uint	s,
		uint	t )

Multiplication of two elements.

Remarks: More efficient if the multiplication table has been computed.

Returns: The resulting element.

Parameters

M	The morphism.
s	First element.
t	Second element.

◆ mor_mult_gen()

uint mor_mult_gen	(	morphism *	M,
		uint	n,
			... )

Multiplication of an arbitrary number of elements.

Remarks: More efficient if the multiplication table has been computed.

Returns: The resulting element.

Parameters

M	The morphism.
n	The number of elements to multiply.
...	The elements.

◆ mor_name()

dequeue * mor_name	(	morphism *	M,
		uint	q )

Return the name of an element (product of generators) in a dequeue.

Returns: The name of the element.

Parameters

M	The morphism.
q	The element.

◆ mor_neutral_letter()

bool mor_neutral_letter	(	morphism *	M,
		FILE *	out )

Tests if there exists a letter mapped to the neutral element.

Remarks: Can dislpay the results of the test on a stream given as input.

Returns: A Boolean indicating whether there exists a letter mapped to the neutral element.

Parameters

M	The morphism.
out	The stream (NULL if no display is desired).

◆ mor_nonempty_neutral()

bool mor_nonempty_neutral ( morphism * M )

Tests if there exists a nonempty antecedent of the neutral element in a morphism.

Returns: A Boolean indicating whether there exists a nonempty antecedent of the neutral element.

Parameters

M	The morphism.

◆ mor_num_idem()

bool mor_num_idem	(	morphism *	M,
		uint	s,
		uint *	res )

Computes the index of an idempotent element.

Returns false if the element given as input is not an idempotent. The index is returned using the third parameter.

Returns: A Boolean indicating if the element is an idempotent.

Parameters

M	The morphism.
s	The element.
res	A pointer used to return the index of the idempotent.

◆ mor_omega()

uint mor_omega	(	morphism *	M,
		uint	s )

Computes the omega power of an element.

Returns: The omega power.

Parameters

M	The morphism.
s	The element.

◆ mor_rmirror()

lgraph * mor_rmirror ( morphism * M )

Computation of the mirror of the right Cayley graph.

Returns: The mirror.

Parameters

M	The morphism.

◆ morphism_to_dfa()

dfa * morphism_to_dfa ( morphism * M )

Computation of a complete DFA from the right Cayley graph of a morphism.

Returns: The complete DFA.

Parameters

M	The morphism.

Classes

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ max

◆ min

Function Documentation

◆ delete_green()

◆ delete_morphism()

◆ dfa_to_morphism()

◆ dfa_to_morphism_size()

◆ gr_green_compute()

◆ green_sorted_jclass()

◆ h_green_compute()

◆ left_morphism_to_dfa()

◆ mor_all_regular()

◆ mor_compute_green()

◆ mor_compute_image()

◆ mor_compute_leftcayley()

◆ mor_compute_min_regular_jcl()

◆ mor_compute_mult()

◆ mor_compute_order()

◆ mor_compute_rep()

◆ mor_duplicate_alpha()

◆ mor_extract_rcl()

◆ mor_letter_index()

◆ mor_lmirror()

◆ mor_mult()

◆ mor_mult_gen()

◆ mor_name()

◆ mor_neutral_letter()

◆ mor_nonempty_neutral()

◆ mor_num_idem()

◆ mor_omega()

◆ mor_rmirror()

◆ morphism_to_dfa()