gfsmSemiring.h

Go to the documentation of this file.

/*=============================================================================*\
 * File: gfsmSemiring.h
 * Author: Bryan Jurish <moocow.bovine@gmail.com>
 * Description: finite state machine library
 *
 * Copyright (c) 2004-2011 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_SEMIRING_H
#define _GFSM_SEMIRING_H

#include <gfsmCommon.h>
#include <float.h>

/*======================================================================
 * Semiring: types
 */
typedef enum {
  gfsmSRTUnknown  = 0,  
  gfsmSRTBoolean  = 1,  
  gfsmSRTLog      = 2,  
  gfsmSRTReal     = 3,  
  gfsmSRTTrivial  = 4,  
  gfsmSRTTropical = 5,  
  gfsmSRTPLog     = 6,  
  gfsmSRTArctic   = 7,  
  gfsmSRTFuzzy    = 8,  
  gfsmSRTProb     = 9,  
  //gfsmSRTViterbi  = 10, ///< Viterbi semiring: <set:[0,1], plus:max, times:*, less:>, zero:0, one:1>
  // -log(gfsmSRTViterbi) === gfsmSRTTropical === -gfsmSRTArctic
  //gfsmSRTLogViterbi,  ///< log-Viterbi semiring: <set:[-inf,0], plus:max, times:+, less:??, zero:-inf, one:0> 
  // SRTLogViterbi === gfsmSRTArctic over set [-inf,0]
  // TODO: concatenation sr: <set:2^(\Sigma^*), plus:\union, times:\concat, less:??, zero:\emptyset, one:{\epsilon}>
  // TODO: string sr: <set:\sigma^* \union {s_\infty}, plus:LCP, times:\concat, less:??, zero:s_\infty, one:\epsilon>
  // TODO: set sr: <set:2^M, plus:\union, times:\intersect, less:??, zero:\emptyset, one:M>, M an arbitrary set
  // TODO: unification sr: <set:2^F, plus:\union, times:\unify, less:??, zero:\emptyset, one:{\bottom}>, F set of FSs
  
  gfsmSRTUser     = 256 
} gfsmSRType;

/*======================================================================
 * Semiring: types: structs
 */
typedef struct {
  gfsmSRType type;    
  gfsmWeight zero;    
  gfsmWeight one;     
} gfsmSemiring;

/*======================================================================
 * Semiring: types: functions
 */
typedef gboolean (*gfsmSRUnaryPredicate) (gfsmSemiring *sr, gfsmWeight x);

typedef gboolean (*gfsmSRBinaryPredicate) (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

typedef gfsmWeight (*gfsmSRUnaryOp) (gfsmSemiring *sr, gfsmWeight x);

typedef gfsmWeight (*gfsmSRBinaryOp) (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);


/*======================================================================
 * Semiring: types: user structs
 */
typedef struct {
  gfsmSemiring sr;                  
  //-- user-defined semirings *must* set these functions
  gfsmSRBinaryPredicate equal_func; 
  gfsmSRBinaryPredicate less_func;  
  gfsmSRBinaryOp        plus_func;  
  gfsmSRBinaryOp        times_func; 
  gfsmSRUnaryOp         inv_l_func; 
  gfsmSRBinaryOp        pow_func;   
  gfsmSRUnaryOp         star_func;  
} gfsmUserSemiring;

/*======================================================================
 * Semiring: methods: constructors etc.
 */


GFSM_INLINE
gfsmSemiring *gfsm_semiring_new(gfsmSRType type);

void gfsm_semiring_init(gfsmSemiring *sr, gfsmSRType type);

GFSM_INLINE
gfsmUserSemiring *gfsm_user_semiring_new(gfsmSRBinaryPredicate equal_func,
                                         gfsmSRBinaryPredicate less_func,
                                         gfsmSRBinaryOp        plus_func,
                                         gfsmSRBinaryOp        times_func);

GFSM_INLINE
gfsmSemiring *gfsm_semiring_copy(gfsmSemiring *sr);

GFSM_INLINE
void gfsm_semiring_free(gfsmSemiring *sr);

/*======================================================================
 * Semiring: general accessors & operations
 */


GFSM_INLINE
gfsmSRType gfsm_sr_type(const gfsmSemiring *sr);

GFSM_INLINE
gfsmWeight gfsm_sr_zero(gfsmSemiring *sr);

GFSM_INLINE
gfsmWeight gfsm_sr_one(gfsmSemiring *sr);

GFSM_INLINE
gboolean gfsm_sr_equal(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

GFSM_INLINE
gboolean gfsm_sr_less(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

gint gfsm_sr_compare(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

GFSM_INLINE
gfsmWeight gfsm_sr_plus(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

GFSM_INLINE
gfsmWeight gfsm_sr_times(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);

GFSM_INLINE
gfsmWeight gfsm_sr_inv_l(gfsmSemiring *sr, gfsmWeight x);

GFSM_INLINE
gfsmWeight gfsm_sr_pow(gfsmSemiring *sr, gfsmWeight x, gfsmWeight n);

gfsmWeight gfsm_sr_pow_n(gfsmSemiring *sr, gfsmWeight x, gint n);

GFSM_INLINE
gfsmWeight gfsm_sr_star(gfsmSemiring *sr, gfsmWeight x);

#define GFSM_SR_STAR_N_DEFAULT 8
gfsmWeight gfsm_sr_star_n(gfsmSemiring *sr, gfsmWeight x, guint n);


/*======================================================================
 * Semiring: methods: string utilities
 */


gfsmSRType gfsm_sr_name_to_type(const char *name);

gchar *gfsm_sr_type_to_name(gfsmSRType type);

/*======================================================================
 * Semiring: methods: general utilities
 */


GFSM_INLINE
gfsmWeight gfsm_log_add(gfsmWeight x, gfsmWeight y);

//-- inline definitions
#ifdef GFSM_INLINE_ENABLED
# include <gfsmSemiring.hi>
#endif

#endif /* _GFSM_SEMIRING_H */