1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
/*=============================================================================*\
* File: gfsmSemiring.h
* Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
* 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 2.1 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
*=============================================================================*/
/** \file gfsmSemiring.h
* \brief semiring types & operations
*/
#ifndef _GFSM_SEMIRING_H
#define _GFSM_SEMIRING_H
#include <gfsmCommon.h>
#include <float.h>
/*======================================================================
* Semiring: types
*/
/** Builtin semiring types
* \see fsmcost(3)
*/
typedef enum {
gfsmSRTUnknown = 0, ///< unknown semiring (should never happen)
gfsmSRTBoolean = 1, ///< boolean semiring <set:{0,1}, plus:||, times:&&, less:>, zero:0, one:1>
gfsmSRTLog = 2, ///< negative log semiring <set:[-inf,inf], plus:-log(e^-x+e^-y), times:+, less:<, zero:inf, one:0>
gfsmSRTReal = 3, ///< real semiring: <set:[0,inf], plus:+, times:*, less:<, zero:0, one:1>
gfsmSRTTrivial = 4, ///< trivial semiring <set:{0}, plus:+, times:+, less:!=, zero:0, one:0>
gfsmSRTTropical = 5, ///< tropical semiring: <set:[-inf,inf], plus:min, times:+, less:<, zero:inf, one:0>
gfsmSRTPLog = 6, ///< positive log semiring <set:[-inf,inf], plus:log(e^x+e^y), times:+, less:>, zero:-inf, one:0>
gfsmSRTUser = 256 ///< user-defined semiring
} gfsmSRType;
/*======================================================================
* Semiring: types: structs
*/
/// struct to represent a builtin semi-ring for gfsm arc weights
typedef struct {
gfsmSRType type; /**< type of this semiring */
gfsmWeight zero; /**< nil element of this semiring (identity for '+') */
gfsmWeight one; /**< unity element of this semiring (idendity for '*') */
} gfsmSemiring;
/*======================================================================
* Semiring: types: functions
*/
/** Type for user-defined semiring unary predicates (i.e. member) */
typedef gboolean (*gfsmSRUnaryPredicate) (gfsmSemiring *sr, gfsmWeight x);
/// Type for user-defined semiring binary predicates (i.e. equal) */
typedef gboolean (*gfsmSRBinaryPredicate) (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/// Type for user-defined semiring unary operations */
typedef gfsmWeight (*gfsmSRUnaryOp) (gfsmSemiring *sr, gfsmWeight x);
/// Type for user-defined semiring binary operations */
typedef gfsmWeight (*gfsmSRBinaryOp) (gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/*======================================================================
* Semiring: types: user structs
*/
/// User-defined semirings for gfsm operations
typedef struct {
gfsmSemiring sr; /**< inheritance magic */
//-- user-defined semirings *must* set these functions
gfsmSRBinaryPredicate equal_func; /**< equality predicate */
gfsmSRBinaryPredicate less_func; /**< order predicate */
gfsmSRBinaryOp plus_func; /**< addition operation */
gfsmSRBinaryOp times_func; /**< multiplication operation */
} gfsmUserSemiring;
/*======================================================================
* Semiring: methods: constructors etc.
*/
///\name Constructors etc.
//@{
/** Create, initialize (for builtin types), and return new semiring of type \a type */
GFSM_INLINE
gfsmSemiring *gfsm_semiring_new(gfsmSRType type);
/** Initialize and return a builtin semiring */
GFSM_INLINE
void gfsm_semiring_init(gfsmSemiring *sr, gfsmSRType type);
/** Initialize and return a semiring */
GFSM_INLINE
gfsmUserSemiring *gfsm_user_semiring_new(gfsmSRBinaryPredicate equal_func,
gfsmSRBinaryPredicate less_func,
gfsmSRBinaryOp plus_func,
gfsmSRBinaryOp times_func);
/** Copy a semiring */
GFSM_INLINE
gfsmSemiring *gfsm_semiring_copy(gfsmSemiring *sr);
/** Destroy a gfsmSemiring */
GFSM_INLINE
void gfsm_semiring_free(gfsmSemiring *sr);
//@}
/*======================================================================
* Semiring: general accessors
*/
///\name General Accessors
//@{
/** Get 'zero' element of the ::gfsmSemiring* \a sr */
GFSM_INLINE
gfsmWeight gfsm_sr_zero(gfsmSemiring *sr);
/** Get 'one' element of the ::gfsmSemiring* \a sr */
GFSM_INLINE
gfsmWeight gfsm_sr_one(gfsmSemiring *sr);
/** Check equality of elements \a x and \a y with respect to ::gfsmSemiring* \a sr */
GFSM_INLINE
gboolean gfsm_sr_equal(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/** Check semiring element order */
GFSM_INLINE
gboolean gfsm_sr_less(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/** 3-way comparison for semiring values */
gint gfsm_sr_compare(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/** Semiring addition */
GFSM_INLINE
gfsmWeight gfsm_sr_plus(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
/** Semiring multiplication */
GFSM_INLINE
gfsmWeight gfsm_sr_times(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y);
//@}
/*======================================================================
* Semiring: methods: string utilities
*/
///\name String utilities
//@{
/** Convert symbolic name of a semiring to a gfsmSRType */
gfsmSRType gfsm_sr_name_to_type(const char *name);
/** Convert a gfsmSRType to a (constant) symbolic name */
gchar *gfsm_sr_type_to_name(gfsmSRType type);
//@}
/*======================================================================
* Semiring: methods: general utilities
*/
///\name General utilities
//@{
/** stable log addition.
* \returns log(exp(x)+exp(y))
*/
GFSM_INLINE
gfsmWeight gfsm_log_add(gfsmWeight x, gfsmWeight y);
//@}
//-- inline definitions
#ifdef GFSM_INLINE_ENABLED
# include <gfsmSemiring.hi>
#endif
#endif /* _GFSM_SEMIRING_H */
|
