sep_group.h

Go to the documentation of this file.

 
#ifndef SEP_GROUP_H
#define SEP_GROUP_H
 
#include "graphs_tarjan.h"
#include "nfa.h"
#include "nfa_intersec.h"
#include "printing.h"
#include "type_dlist.h"
#include "type_partitions.h"
#include "flint/fmpz.h"
#include "flint/fmpz_mat.h"
#include <stdbool.h>
#include <stdlib.h>
 
 /*  ____                             _   _                  ____ */
 /* / ___|  ___ _ __   __ _ _ __ __ _| |_(_) ___  _ __  _   / ___|_ __ ___  _    __ __   */
 /* \___ \ / _ \ '_ \ / _` | '__/ _` | __| |/ _ \| '_ \‍(_) | |  _| '__/ _ \| | | | '_ \  */
 /*  ___) |  __/ |_) | (_| | | | (_| | |_| | (_) | | | |_  | |_| | | | (_) | |_| | |_) | */
 /* |____/ \___| .__/ \__,_|_|  \__,_|\__|_|\___/|_| |_(_)  \____|_|  \___/\__,_ | .__/  */
 /* | | __ _ _ |_|  __ _ _   _  __ _  __ _  ___  ___ |_|     */
 /* | |/ _` | '_ \ / _` | | | |/ _` |/ _` |/ _ \/ __| */
 /* | | (_| | | | | (_| | |_| | (_| | (_| |  __/\__ \ */
 /* |_|\__,_|_| |_|\__, |\__,_|\__,_|\__, |\___||___/ */
 /*                |___/             |___/ */
 
 
/********************/
/*+ AMT-separation +*/
/********************/
 
bool solve_system_amt(fmpz_mat_t MAT, int* target, uint nb_rows, uint nb_cols);

typedef struct {
    uint size_graph; 
    uint size_alpha; 
    uint nb_trees;   
    int** span_forest; 
    uint* numtree; 
    uint* root; 
    dequeue** dropped; 
} num_span_forest;

num_span_forest* compute_span_forest(dgraph* G, 
    parti* sccs, 
    bool* allowed 
);
 

void delete_span_forest(num_span_forest* forest 
);

parti* dgraph_amt_fold(dgraph* g, 
    parti* sccs 
);
 
 

void compute_amt_kernel_regular(
    morphism*, 
    bool*,     
    uint*      
);
 
void build_hnf_matrix_two(dgraph* g1, dgraph* g2, num_span_forest* span1, num_span_forest* span2, uint q1, uint q2, fmpz_mat_t MAT);

void compute_amt_pairs_regular(
    morphism* M, 
    num_span_forest* rspan, 
    num_span_forest* lspan, 
    uint e,             
    uint f,             
    dequeue* first, 
    dequeue* second 
);
 
/**************************/
/*+ Dealing with dgraphs +*/
/**************************/

parti* dgraph_stal_fold(dgraph* G, 
    parti* sccs, 
    basis ba 
);
 
 

dgraph* shrink_mod(dgraph* g, 
    parti* fold, 
    parti* sccs 
);

dgraph* shrink_mod_mirror(dgraph* g, 
    parti* fold, 
    parti* sccs 
);

dgraph* shrink_grp(dgraph* g, 
    parti* fold, 
    parti* sccs 
);

dgraph* shrink_grp_mirror(dgraph* g, 
    parti* fold, 
    parti* sccs 
);
 
 

dgraph* dgraph_implement_fold(dgraph* g, 
    parti* sccs, 
    parti* fold 
);
 
dfa* dfa_compute_folding(dfa* A, 
    basis ba 
);
 
/***********************/
/*+ Inverse extension +*/
/***********************/

parti* nfa_inv_ext(nfa* 
);

void nfa_remove_inv(nfa* 
);
 
/***********************************/
/*+ Separation by group languages +*/
/***********************************/

parti* nfa_stal_fold(nfa*, 
    parti* 
);
 
 

nfa* nfa_dyck_ext(
    nfa*,  
    parti* 
);

bool decid_grp_sep(nfa*, 
    nfa*, 
    bool,  
    FILE* 
);
 
/************************************/
/*+ Separation by modulo languages +*/
/************************************/

nfa* nfa_proj_unary(nfa* 
);

bool decid_mod_sep(nfa*, 
    nfa*, 
    bool,  
    FILE* 
);
 
/*************************************/
/*+ Separation by trivial languages +*/
/*************************************/

bool decid_st_sep(nfa*, 
    nfa*, 
    FILE* 
);
 
#endif