monoid.h

Go to the documentation of this file.

 
#ifndef _MONOID_H_
#define _MONOID_H_
 
#ifndef max
#define max(a, b) (((a) > (b)) ? (a) : (b))
#endif
 
#ifndef min
#define min(a, b) (((a) < (b)) ? (a) : (b))
#endif
 
#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>
 
 /*  __  __                   _     _                       _  */
 /* |  \/  | ___  _ __   ___ (_) __| |___    __ _ _ __   __| | */
 /* | |\/| |/ _ \| '_ \ / _ \| |/ _` / __|  / _` | '_ \ / _` | */
 /* | |  | | (_) | | | | (_) | | (_| \__ \ | (_| | | | | (_| | */
 /* |_|  |_|\___/|_| |_|\___/|_|\__,_|___/  \__,_|_| |_|\__,_| */
 /*  _ __ ___   ___  _ __ _ __ | |__ (_)___ _ __ ___  ___      */
 /* | '_ ` _ \ / _ \| '__| '_ \| '_ \| / __| '_ ` _ \/ __|     */
 /* | | | | | | (_) | |  | |_) | | | | \__ \ | | | | \__ \     */
 /* |_| |_| |_|\___/|_|  | .__/|_| |_|_|___/_| |_| |_|___/     */
 /*                      |_|                                   */
 
 
 
//#define DEBUG_MONO
 

#define ONE 0

typedef struct {
 
    /* Partitions */
    parti* JCL;            
    parti* LCL;            
    parti* RCL;            
    parti* HCL;            
 
    /* Informations on regular elements */
    uint nb_regular_elems; 
    bool* regular_array;     
 
    /* Information on groups */
    bool* group_array;     
} green;
 
 

typedef struct {
    /* Mandatory fields */
    letter* alphabet;     
    uint* pred_ele;       
    uint* pred_lab;       
    dgraph* r_cayley;     
    dgraph* l_cayley;     
 
    uint nb_idems;        
    uint* idem_list;      
    bool* idem_array;     
    uint nb_accept;       
    uint* accept_list;    
    bool* accept_array;   
    green* rels;          
 
    uint nb_regular_jcl;   
    uint nb_min_regular_jcl; 
    uint* regular_idems;   
 
    /* Optional fields (NULL if not computed) */
    uint* mult; 
    uint** order; 
    uint* order_size; 
    uint* order_storage; 
} morphism;
 
/*******************/
/* Basic functions */
/*******************/

void delete_green(green* 
);

void delete_morphism(morphism* 
);

letter* mor_duplicate_alpha(const morphism* 
);

uint mor_letter_index(const morphism*, 
    letter            
);

 
uint mor_regular_jclass(const morphism*, 
    uint              
);
 
 
/**********************************************/
/* Preliminary functions for the construction */
/**********************************************/

void mor_compute_leftcayley(morphism* 
);

uint* green_sorted_jclass(green*, 
    uint 
);

void h_green_compute(green* 
);

void gr_green_compute(uint*,    
    uint,       
    green* 
);
 

void mor_compute_rep(morphism*
);
 

void mor_compute_green(morphism* 
);

void mor_compute_min_regular_jcl(morphism* 
);
 
 
/************************************/
/* Construction from a complete DFA */
/************************************/
 

morphism* dfa_to_morphism(dfa*, 
    bool, 
    int*,  
    uint** 
);
 

uint dfa_to_morphism_size(dfa* A 
);

dfa* morphism_to_dfa(morphism* 
);

dfa* left_morphism_to_dfa(morphism* 
);
 
 
 
 
/***************************************/
/* Computing information on a morphism */
/***************************************/
 
 

void mor_compute_mult(morphism* 
);

lgraph* mor_rmirror(morphism* 
);

lgraph* mor_lmirror(morphism* 
);

dequeue** mor_compute_order(morphism* 
);
 
 
/***************************/
/* Operations on morphisms */
/***************************/

dequeue* mor_name(morphism*, 
    uint              
);
 

uint mor_mult(morphism*, 
    uint,       
    uint        
);

uint mor_mult_gen(morphism*, 
    uint,       
    ...         
);

uint mor_omega(morphism*, 
    uint        
);

bool mor_num_idem(morphism*, 
    uint,       
    uint*      
);
 
 
 
 
 
/**************/
/* Properties */
/**************/

bool mor_neutral_letter(morphism*, 
    FILE*      
);

bool mor_nonempty_neutral(morphism* 
);

bool mor_all_regular(morphism* 
);
 
 

uint mor_compute_image(morphism*, 
    word*      
);
 
 

dgraph* mor_extract_rcl(morphism* M, 
    uint rcl 
);
 
/*
 
// Récupération des éléments intersectant chaque alphabet dans un tableau
dequeue** at_table_cayley(morphism*);
 
// Affichage du tableau
void print_at_table(morphism* M, dequeue** table, FILE* out); */
 
#endif // _MONOID_H_