2
* \brief declarations for monoids, d-class decompositions
3
* Copyright (c) ? - 2000 Lehrstuhl fuer Informatik VII, RWTH Aachen
4
* Copyright (c) 2000 - 2002 Burak Emir
5
* This file is part of the libAMoRE library.
7
* libAMoRE is free software; you can redistribute it and/or
8
* modify it under the terms of the GNU Lesser General Public
9
* License as published by the Free Software Foundation; either
10
* version 2.1 of the License, or (at your option) any later version.
11
* You should have received a copy of the GNU Lesser General Public
12
* License along with the GNU C Library; if not, write to the Free
13
* Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
22
/** D-class (Green's relations)
25
/** element in the upper left hclass */
27
/** #r-classes,#lclasses */
29
/** #elements in a h-class */
31
/** array of prefixes(suffixes)
32
* of representatives of
33
* each r(l)-class (0 to r(l)no-1)
36
/** one full h-class (0 to hsize-1) */
38
/** true iff regular d-class */
40
/** rang of d-class */
42
/** max.\ length of an element */
44
/** height of dclass in partial order */
47
/** pointer to a D-class */
48
typedef struct dclass *d_class;
50
/** array of D-classes */
51
typedef d_class *darray;
53
/** D-class decomposition */
63
/** height of d-class partial order */
71
/** pointer to a D-class decomposition */
72
typedef struct d_struct *dstruct;
76
posint rno; /**<no of relations*/
77
array lside; /**< leftside(number of a monoidelement) (0 .. rno-1) */
78
array rside; /**< rightside(number of a generator) (0 .. rno-1) */
81
/** pointer to a relation */
82
typedef struct r_struct *rstruct;
96
/** list of generators (0 to gno)*/
99
* j is the least letter with the
100
* transformation of generator i
103
/** transf_ of elements(0 to mno-1, 0 to qno) */
104
arrayofarray no2trans;
105
/** gensucc[i][0]= predecessor of i
107
* gensucc[i][gen]=i*gen (0 to mno-1,0gno)
109
arrayofarray gensucc;
110
/** last letter of a shortest
111
* representation of a element (0 to mno-1)
114
/** length of the representation (0 to mno-1) */
116
/** number of the zero if one exists
118
* stamon->mno if no zero exists
121
/** syn.\ monoid = syn.\ semigroup */
123
/** d-classes are computed */
124
boole dclassiscomputed;
125
/** dclass structure if computed */
127
/** no2rang is computed */
128
boole relationcomputed;
129
/** relation if computed */
131
/** free space used for the computation
132
* of a representative with
133
* lastletter and gensucc[0]
136
/** free space for display of repr. */
139
/** pointer to a monoid
142
typedef struct mono *monoid;
144
/** allocates a new monoid
147
/** frees the memory used by the monoid mon
149
void freemon(monoid mon) ;
151
/** frees the memory used by the D-class structure dcl
153
* i is the number of the used entries in dclassarray
155
void freedcl(dstruct dcl, posint i) ;
157
/** allocates a new dclass
159
d_class newdclass() ;
161
/** allorcates a new dstruct
163
dstruct newdstruct() ;
165
/** allocates a new rstruct
167
rstruct newrstruct() ;
168
/** allocates a new darray
170
darray newdarray(posint a) ;
172
/** same as prword1((char **)NULL,FALSE,(posint *)NULL,no,mon,with,TRUE));
174
char *prword( posint no,
178
/** returns the shortest representative of the element no in monoid mon
180
* if (copy) word contains a copy of the output
182
* in this case length is the size of word
184
* if (with) mark idempotent elements with a star
186
* if (zeroone) print 0 for mon->zero else the representative of the zero
188
* print 1 for the identity else ""
190
char* prword1( char **word,
198
/** multiplication of 2 monoidelements a and b */
200
posint mult(monoid mon,posint a,posint b) ;
202
/** needed when loading... from file */
203
void comprestofmon(monoid mon,dfa indfa) ;
205
/** compute length of longest representative of monoid mon */
206
posint monmaxlen(monoid mon) ;