semiring types & operations More...

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

Include dependency graph for gfsmSemiring.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	gfsmSemiring
	struct to represent a builtin semi-ring for gfsm arc weights More...
struct	gfsmUserSemiring
	User-defined semirings for gfsm operations. More...

Typedefs
typedef gboolean(*	gfsmSRUnaryPredicate )(gfsmSemiring *sr, gfsmWeight x)
typedef gboolean(*	gfsmSRBinaryPredicate )(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
	Type for user-defined semiring binary predicates (i.e. equal) */.
typedef gfsmWeight(*	gfsmSRUnaryOp )(gfsmSemiring *sr, gfsmWeight x)
	Type for user-defined semiring unary operations */.
typedef gfsmWeight(*	gfsmSRBinaryOp )(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
	Type for user-defined semiring binary operations */.

Enumerations
enum	gfsmSRType { gfsmSRTUnknown = 0, gfsmSRTBoolean = 1, gfsmSRTLog = 2, gfsmSRTReal = 3, gfsmSRTTrivial = 4, gfsmSRTTropical = 5, gfsmSRTPLog = 6, gfsmSRTArctic = 7, gfsmSRTFuzzy = 8, gfsmSRTProb = 9, gfsmSRTUser = 256 }

Functions
Constructors etc.
static gfsmSemiring *	gfsm_semiring_new (gfsmSRType type)
void	gfsm_semiring_init (gfsmSemiring *sr, gfsmSRType type)
static gfsmUserSemiring *	gfsm_user_semiring_new (gfsmSRBinaryPredicate equal_func, gfsmSRBinaryPredicate less_func, gfsmSRBinaryOp plus_func, gfsmSRBinaryOp times_func)
static gfsmSemiring *	gfsm_semiring_copy (gfsmSemiring *sr)
static void	gfsm_semiring_free (gfsmSemiring *sr)
String utilities
gfsmSRType	gfsm_sr_name_to_type (const char *name)
gchar *	gfsm_sr_type_to_name (gfsmSRType type)
General utilities
static gfsmWeight	gfsm_log_add (gfsmWeight x, gfsmWeight y)

General Accessors & Operations
#define	GFSM_SR_STAR_N_DEFAULT 8
static gfsmSRType	gfsm_sr_type (const gfsmSemiring *sr)
static gfsmWeight	gfsm_sr_zero (gfsmSemiring *sr)
static gfsmWeight	gfsm_sr_one (gfsmSemiring *sr)
static gboolean	gfsm_sr_equal (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
static gboolean	gfsm_sr_less (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
gint	gfsm_sr_compare (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
static gfsmWeight	gfsm_sr_plus (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
static gfsmWeight	gfsm_sr_times (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
static gfsmWeight	gfsm_sr_inv_l (gfsmSemiring *sr, gfsmWeight x)
static gfsmWeight	gfsm_sr_pow (gfsmSemiring *sr, gfsmWeight x, gfsmWeight n)
gfsmWeight	gfsm_sr_pow_n (gfsmSemiring *sr, gfsmWeight x, gint n)
static gfsmWeight	gfsm_sr_star (gfsmSemiring *sr, gfsmWeight x)
gfsmWeight	gfsm_sr_star_n (gfsmSemiring *sr, gfsmWeight x, guint n)

Detailed Description

Macro Definition Documentation

#define GFSM_SR_STAR_N_DEFAULT 8

star-closure: n-approximation

Typedef Documentation

typedef gboolean(* gfsmSRUnaryPredicate)(gfsmSemiring *sr, gfsmWeight x)

Type for user-defined semiring unary predicates (i.e. member)

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)

Enumeration Type Documentation

enum gfsmSRType

Builtin semiring types

See Also: fsmcost(3)

Enumerator:

gfsmSRTUnknown	unknown semiring (should never happen)
gfsmSRTBoolean	boolean semiring <set:{0,1}, plus:\|\|, times:&&, less:>, zero:0, one:1>
gfsmSRTLog	negative log semiring <set:[-inf,inf], plus:-log(e^-x+e^-y), times:+, less:<, zero:inf, one:0>
gfsmSRTReal	real semiring: <set:[0,inf], plus:+, times:*, less:<, zero:0, one:1>
gfsmSRTTrivial	trivial semiring <set:{0}, plus:+, times:+, less:!=, zero:0, one:0>
gfsmSRTTropical	tropical semiring: <set:[-inf,inf], plus:min, times:+, less:<, zero:inf, one:0>
gfsmSRTPLog	positive log semiring <set:[-inf,inf], plus:log(e^x+e^y), times:+, less:>, zero:-inf, one:0>
gfsmSRTArctic	arctic semiring: <set:[-inf,inf], plus:max, times:+, less:>, zero:-inf, one:0>
gfsmSRTFuzzy	"fuzzy" semiring: <set:[0,1], plus:max, times:min, less:>, zero:0, one:1>
gfsmSRTProb	probabilistic sr: <set:[0,1], plus:+, times:*, less:>(?), zero:0, one:1>
gfsmSRTUser	user-defined semiring

Function Documentation

static gfsmSemiring* gfsm_semiring_new ( gfsmSRType type )

inlinestatic

Create, initialize (for builtin types), and return new semiring of type type

void gfsm_semiring_init	(	gfsmSemiring *	sr,
		gfsmSRType	type
	)

Initialize and return a builtin semiring

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

inlinestatic

Initialize and return a semiring

static gfsmSemiring* gfsm_semiring_copy ( gfsmSemiring * sr )

inlinestatic

Copy a semiring

static void gfsm_semiring_free ( gfsmSemiring * sr )

inlinestatic

Destroy a gfsmSemiring

static gfsmSRType gfsm_sr_type ( const gfsmSemiring * sr )

inlinestatic

Get type of a gfsmSemiring sr; returns gfsmSRTUnknown for sr==NULL

static gfsmWeight gfsm_sr_zero ( gfsmSemiring * sr )

inlinestatic

Get 'zero' element of the gfsmSemiring* sr

static gfsmWeight gfsm_sr_one ( gfsmSemiring * sr )

inlinestatic

Get 'one' element of the gfsmSemiring* sr

static gboolean gfsm_sr_equal	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		gfsmWeight	y
	)

inlinestatic

Check equality of elements x and y with respect to gfsmSemiring* sr

static gboolean gfsm_sr_less	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		gfsmWeight	y
	)

inlinestatic

Check semiring element order

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

3-way comparison for semiring values

static gfsmWeight gfsm_sr_plus	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		gfsmWeight	y
	)

inlinestatic

Semiring addition

static gfsmWeight gfsm_sr_times	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		gfsmWeight	y
	)

inlinestatic

Semiring multiplication

static gfsmWeight gfsm_sr_inv_l	(	gfsmSemiring *	sr,
		gfsmWeight	x
	)

inlinestatic

Left-multiplication inverse: inv_l(x) s.t. inv_l(x)*x = x (not for all semirings)

static gfsmWeight gfsm_sr_pow	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		gfsmWeight	n
	)

inlinestatic

Semiring power operation: x^0=1; x^(n+1)=(x^n)*x, (n a natural number)

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

power operation: n-approximation

static gfsmWeight gfsm_sr_star	(	gfsmSemiring *	sr,
		gfsmWeight	x
	)

inlinestatic

Semiring star-closure: x* = 1 + x + (x*x) + (x*x*x) + (x*x*x*x) + ...

gfsmWeight gfsm_sr_star_n	(	gfsmSemiring *	sr,
		gfsmWeight	x,
		guint	n
	)

gfsmSRType gfsm_sr_name_to_type ( const char * name )

Convert symbolic name of a semiring to a gfsmSRType

gchar* gfsm_sr_type_to_name ( gfsmSRType type )

Convert a gfsmSRType to a (constant) symbolic name

static gfsmWeight gfsm_log_add	(	gfsmWeight	x,
		gfsmWeight	y
	)

inlinestatic

stable log addition.

Returns: log(exp(x)+exp(y))

Data Structures

Typedefs

Enumerations

Functions

General Accessors & Operations

Detailed Description

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation