gfsmAlgebra.h

Go to the documentation of this file.

/*=============================================================================*\
 * File: gfsmAlgebra.h
 * Author: Bryan Jurish <moocow.bovine@gmail.com>
 * Description: finite state machine library
 *
 * Copyright (c) 2004-2007 Bryan Jurish.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 3 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *=============================================================================*/

#ifndef _GFSM_ALGEBRA_H
#define _GFSM_ALGEBRA_H

#include <gfsmCompound.h>
#include <gfsmArcIndex.h>

/*======================================================================
 * Methods: algebra
 */

//------------------------------


gfsmAutomaton *gfsm_automaton_closure(gfsmAutomaton *fsm, gboolean is_plus);

/* Final-state pre-traversal utility for \c closure(fsm). */
//gboolean gfsm_automaton_closure_final_func_(gfsmStateId id, gpointer pw, gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_n_closure(gfsmAutomaton *fsm, guint n);

gfsmAutomaton *gfsm_automaton_optional(gfsmAutomaton *fsm);

//------------------------------


gfsmAutomaton *gfsm_automaton_complement(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_complement_full(gfsmAutomaton *fsm, gfsmAlphabet *alph);

gfsmAutomaton *gfsm_automaton_complete(gfsmAutomaton    *fsm,
                                       gfsmAlphabet     *alph,
                                       gfsmStateId      *sinkp);

//------------------------------


gfsmAutomaton *gfsm_automaton_compose(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);


gfsmAutomaton *gfsm_automaton_compose_full(gfsmAutomaton *fsm1,
                                           gfsmAutomaton *fsm2,
                                           gfsmAutomaton *composition,
                                           gfsmComposeStateEnum *spenum);

typedef guint32 gfsmComposeFlags; 
typedef enum {
  gfsmCFEfsm1NeedsArcSort = 0x1,
  gfsmCFEfsm2NeedsArcSort = 0x2
} gfsmComposeFlagsE;

void gfsm_automaton_compose_visit_(gfsmStateId       qid,
                                   gfsmAutomaton    *fsm1,
                                   gfsmAutomaton    *fsm2,
                                   gfsmAutomaton    *fsm,
                                   gfsmComposeStateEnum *spenum,
                                   GArray               *spenumr, //-- GArray of gfsmComposeState
                                   GQueue               *queue,   //-- queue of gfsmStateId
                                   gfsmComposeFlags  flags);

//------------------------------


gfsmAutomaton *gfsm_automaton_n_concat(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2, guint n);

gfsmAutomaton *gfsm_automaton_concat(gfsmAutomaton *fsm1, gfsmAutomaton *_fsm2);

/* Final-state pre-traversal utility for \a concat(fsm,fsm2).
 *
 *  \note Assumes \a fsm->root_id has been temporarily set to the translated gfsmStateId
 *        of \a fsm2->root_id.
 *
 *  \param pw  final ::gfsmWeight encoded as a gpointer (e.g. with gfsm_weight2ptr())
 *  \param fsm concatenation first argument / return value
 *  \returns FALSE
 */
//gboolean gfsm_automaton_concat_final_func_(gfsmStateId id, gpointer pw, gfsmAutomaton *fsm);


//------------------------------


gfsmAutomaton *gfsm_automaton_connect(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_connect_fw(gfsmAutomaton *fsm, gfsmBitVector *visited);

gfsmAutomaton *gfsm_automaton_connect_bw(gfsmAutomaton       *fsm,
                                         gfsmReverseArcIndex *rarcs,
                                         gfsmBitVector       *finalizable);

gfsmAutomaton *gfsm_automaton_prune_states(gfsmAutomaton *fsm, gfsmBitVector *wanted);


//------------------------------


gfsmAutomaton *gfsm_automaton_determinize(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_determinize_full(gfsmAutomaton *nfa, gfsmAutomaton *dfa);

#define gfsm_automaton_determinise(fsm) gfsm_automaton_determinize(fsm)

#define gfsm_automaton_determinise_full(nfa,dfa) gfsm_automaton_determinize_full((nfa),(dfa))


//------------------------------


gfsmAutomaton *gfsm_automaton_difference(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

gfsmAutomaton *gfsm_automaton_difference_full(gfsmAutomaton *fsm1,
                                              gfsmAutomaton *fsm2,
                                              gfsmAutomaton *diff);


//------------------------------


gfsmAutomaton *gfsm_automaton_intersect(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

gfsmAutomaton *gfsm_automaton_intersect_full(gfsmAutomaton *fsm1,
                                             gfsmAutomaton *fsm2,
                                             gfsmAutomaton *intersect,
                                             gfsmStatePairEnum *spenum);

gfsmStateId gfsm_automaton_intersect_visit_(gfsmStatePair  sp,
                                            gfsmAutomaton *fsm1,
                                            gfsmAutomaton *fsm2,
                                            gfsmAutomaton *fsm,
                                            gfsmStatePairEnum *spenum,
                                            gfsmComposeFlags   flags);

//------------------------------


gfsmAutomaton *gfsm_automaton_minimize(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_minimize_full(gfsmAutomaton *fsm, gboolean rmeps);

gfsmAutomaton *gfsm_automaton_compact(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_compact_full(gfsmAutomaton *fsm, gboolean rmeps);



//------------------------------


gfsmAutomaton *gfsm_automaton_invert(gfsmAutomaton *fsm);

gfsmAutomaton *gfsm_automaton_project(gfsmAutomaton *fsm, gfsmLabelSide which);


//------------------------------


gfsmAutomaton *gfsm_automaton_product(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

gfsmAutomaton *gfsm_automaton_product2(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

/* Backwards-compatible alias for gfsm_automaton_product2() [DISABLED] */
//#define _gfsm_automaton_product gfsm_automaton_product2



//------------------------------


gfsmAutomaton *gfsm_automaton_replace(gfsmAutomaton *fsm1, gfsmLabelVal lo, gfsmLabelVal hi, gfsmAutomaton *fsm2);

gfsmAutomaton *gfsm_automaton_insert_automaton(gfsmAutomaton *fsm1,
                                               gfsmStateId    q1from,
                                               gfsmStateId    q1to,
                                               gfsmAutomaton *fsm2,
                                               gfsmWeight     w);



//------------------------------


gfsmAutomaton *gfsm_automaton_reverse(gfsmAutomaton *fsm);


//------------------------------


gfsmAutomaton *gfsm_automaton_rmepsilon(gfsmAutomaton *fsm);


//------------------------------


gfsmAutomaton *gfsm_automaton_sigma(gfsmAutomaton *fsm, gfsmAlphabet *abet);

//------------------------------


gfsmAutomaton *gfsm_automaton_union(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

#endif /* _GFSM_ALGEBRA_H */