1 /* file fsacomposite.c 24. 11. 94.
2 * 29/9/98 large-scale re-organisation.
3 * 3/8/98 - put in code for integer hash tables.
4 * 13/1/98 - changes for `gen' type of generator replacing char.
5 *
6 * This file contains the routines necessary for axiom checking in an
7 * automatic group.
8 *
9 * 13/9/95 - make the length 2 generalised multiplier have state set of
10 * type setToLabels, where the labels are lists of words (of length 2),
11 * rather than words.
12 */
13
14 #define LABHTSIZE 8192
15
16 #include <stdio.h>
17 #include "defs.h"
18 #include "fsa.h"
19 #include "hash.h"
20 #include "externals.h"
21
22 /* Functions defined in this file: */
23 static fsa *fsa_genmult2_short(fsa *genmultptr, storage_type op_table_type,
24 boolean destroy, char *genmult2filename,
25 boolean readback);
26 static fsa *fsa_genmult2_int(fsa *genmultptr, storage_type op_table_type,
27 boolean destroy, char *genmult2filename,
28 boolean readback);
29 static fsa *fsa_composite_short(fsa *mult1ptr, fsa *mult2ptr,
30 storage_type op_table_type, boolean destroy,
31 char *compfilename, boolean readback);
32 static fsa *fsa_composite_int(fsa *mult1ptr, fsa *mult2ptr,
33 storage_type op_table_type, boolean destroy,
34 char *compfilename, boolean readback);
35
36 /* *genmultptr should be the general multiplier fsa of an automatic group.
37 * This function calculates the transition table of the general multiplier for
38 * products of two generators. This is output (in unformatted form) to the
39 * file with name genmult2filename, followed by a list of states, which
40 * specifies which states are accept-states for which length-two words.
41 * It can then be minimised for any such word as required.
42 * If readback is false, then
43 * the fsa returned does not have its transition table stored internally
44 * (since these are in the file genmult2filename) - instead, its table
45 * component table->filename contains the name of this file.
46 * Otherwise, the transition table is read back in as usual.
47 * If genmult2filename is the empty string, then the transition table is
48 * not stored at all.
49 * (This can be done when all relators of the group have length at most 4.)
50 */
fsa_genmult2(fsa * genmultptr,storage_type op_table_type,boolean destroy,char * genmult2filename,boolean readback)51 fsa *fsa_genmult2(fsa *genmultptr, storage_type op_table_type, boolean destroy,
52 char *genmult2filename, boolean readback)
53 {
54 if (kbm_print_level >= 3)
55 printf(" #Calling fsa_genmult2.\n");
56 if (genmultptr->states->size < MAXUSHORT)
57 return fsa_genmult2_short(genmultptr, op_table_type, destroy,
58 genmult2filename, readback);
59 else
60 return fsa_genmult2_int(genmultptr, op_table_type, destroy,
61 genmult2filename, readback);
62 }
63
fsa_genmult2_short(fsa * genmultptr,storage_type op_table_type,boolean destroy,char * genmult2filename,boolean readback)64 static fsa *fsa_genmult2_short(fsa *genmultptr, storage_type op_table_type,
65 boolean destroy, char *genmult2filename,
66 boolean readback)
67 {
68 int **table, ne, ngens, ngens1, ns, *fsarow, e, e1, e2, es1, ef1, dr, nt,
69 cstate, im, csa, csb, csima, csimb, i, j, j1, j2, g1, g2, g3, len = 0, reclen,
70 nlab, ct;
71 unsigned short *ht_ptr, *ht_chptr, *ht_ptrb, *ht_ptre, *cs_ptr, *cs_ptre,
72 *ptr;
73 boolean dense_ip, dense_op, got, leftpad, rightpad, keeptable;
74 setToLabelsType *label, l1, l2, *newlabel;
75 gen **labellist1, **labellist2;
76 short_hash_table ht, labelht;
77 fsa *genmult2ptr;
78 srec *labelset;
79 FILE *tablefile = 0;
80
81 if (kbm_print_level >= 3)
82 printf(" #Calling fsa_genmult2_short.\n");
83 if (!genmultptr->flags[DFA]) {
84 fprintf(stderr, "Error: fsa_genmult2 only applies to DFA's.\n");
85 return 0;
86 }
87
88 if (genmultptr->alphabet->type != PRODUCT ||
89 genmultptr->alphabet->arity != 2) {
90 fprintf(stderr, "Error in fsa_genmult2: fsa must be 2-variable.\n");
91 return 0;
92 }
93
94 if (genmultptr->states->type != LABELED) {
95 fprintf(stderr, "Error in fsa_genmult2: states of fsa must be labeled.\n");
96 return 0;
97 }
98
99 keeptable = stringlen(genmult2filename) > 0;
100 if (readback && !keeptable) {
101 fprintf(stderr,
102 "Error in fsa_genmult2: readback true but empty filename.\n");
103 return 0;
104 }
105
106 tmalloc(genmult2ptr, fsa, 1);
107 fsa_init(genmult2ptr);
108 srec_copy(genmult2ptr->alphabet, genmultptr->alphabet);
109 genmult2ptr->num_initial = 1;
110 tmalloc(genmult2ptr->initial, int, 2);
111 genmult2ptr->initial[1] = 1;
112 genmult2ptr->flags[DFA] = TRUE;
113 genmult2ptr->flags[ACCESSIBLE] = TRUE;
114 genmult2ptr->flags[BFS] = TRUE;
115
116 genmult2ptr->table->table_type = op_table_type;
117 genmult2ptr->table->denserows = 0;
118 genmult2ptr->table->printing_format = op_table_type;
119 if (!readback) {
120 tmalloc(genmult2ptr->table->filename, char,
121 stringlen(genmult2filename) + 1);
122 strcpy(genmult2ptr->table->filename, genmult2filename);
123 }
124
125 ne = genmultptr->alphabet->size;
126 ngens = genmultptr->alphabet->base->size;
127 ngens1 = ngens + 1;
128
129 if (ne != ngens1 * ngens1 - 1) {
130 fprintf(stderr, "Error: in a 2-variable fsa, alphabet size should = "
131 "(ngens+1)^2 - 1.\n");
132 return 0;
133 }
134
135 fsa_set_is_accepting(genmultptr);
136
137 dense_ip = genmultptr->table->table_type == DENSE;
138 dr = genmultptr->table->denserows;
139 dense_op = op_table_type == DENSE;
140 table = genmultptr->table->table_data_ptr;
141
142 short_hash_init(&ht, FALSE, 0, 0, 0);
143 ht_ptr = ht.current_ptr;
144 ht_ptr[0] = genmultptr->initial[1];
145 ht_ptr[1] = genmultptr->initial[1];
146 im = short_hash_locate(&ht, 2);
147 /* Each state in the composite transition table will be represented as a
148 * subset of the set of ordered pairs of states of *genmultptr. The initial
149 * state contains just one such pair, of which both components are the initial
150 * state of *genmultptr. The subsets will be stored as variable-length records
151 * in the hash-table, as a list of pairs in increasing order. If a state is
152 * reached from a transition ($,x) or (x,$) (with $ the padding symbol), then
153 * it needs to be marked as such, since we do not allow a $ to be followed by
154 * any other generator. We do this by adding a 1 or a 2 to the end of the
155 * statelist - this is recognisable by the fact that the length of the
156 * statelist then becomes odd.
157 */
158 if (im != 1) {
159 fprintf(stderr, "Hash-initialisation problem in fsa_genmult2.\n");
160 return 0;
161 }
162 if (keeptable)
163 if ((tablefile = fopen(genmult2filename, "w")) == 0) {
164 fprintf(stderr, "Error: cannot open file %s\n", genmult2filename);
165 return 0;
166 }
167 if (dense_op)
168 tmalloc(fsarow, int, ne) else tmalloc(fsarow, int, 2 * ne + 1)
169
170 label = genmultptr->states->setToLabels;
171 cstate = 0;
172 if (dense_op)
173 len = ne; /* The length of the fsarow output. */
174 nt = 0; /* Number of transitions in genmult2ptr */
175
176 while (++cstate <= ht.num_recs) {
177 if (kbm_print_level >= 3) {
178 if ((cstate <= 1000 && cstate % 100 == 0) ||
179 (cstate <= 10000 && cstate % 1000 == 0) ||
180 (cstate <= 100000 && cstate % 5000 == 0) || cstate % 50000 == 0)
181 printf(" #cstate = %d; number of states = %d.\n", cstate,
182 ht.num_recs);
183 }
184 reclen = short_hash_rec_len(&ht, cstate);
185 cs_ptr = short_hash_rec(&ht, cstate);
186 cs_ptre = short_hash_rec(&ht, cstate) + reclen - 1;
187 if (reclen % 2 == 1) {
188 if (*cs_ptre == 1) {
189 leftpad = TRUE;
190 rightpad = FALSE;
191 }
192 else {
193 leftpad = FALSE;
194 rightpad = TRUE;
195 }
196 cs_ptre--;
197 }
198 else {
199 leftpad = FALSE;
200 rightpad = FALSE;
201 }
202
203 if (dense_op)
204 for (i = 0; i < ne; i++)
205 fsarow[i] = 0;
206 else
207 len = 0;
208
209 e = 0; /* e is the edge number of generator pair (g1,g3) */
210 for (g1 = 1; g1 <= ngens1; g1++)
211 for (g3 = 1; g3 <= ngens1; g3++) {
212 /* Calculate action of pair (g1,g3) on state cstate - to get the image,
213 * we have to apply ( (g1,g2), (g2,g3) ) to each ordered pair in the
214 * subset corresponding to cstate, * and this for each generator g2 of
215 * the base-alphabet (including the padding symbol).
216 */
217
218 e++;
219 if (g1 == ngens1 && g3 == ngens1)
220 continue;
221
222 if ((leftpad && g1 <= ngens) || (rightpad && g3 <= ngens))
223 continue;
224 ht_ptrb = ht.current_ptr;
225 ht_ptre = ht_ptrb - 1;
226
227 es1 = (g1 - 1) * ngens1 + 1;
228 ef1 = g1 * ngens1;
229 /* As g2 ranges from 1 to ngens+1 in the pair (g1,g2), for fixed g1, the
230 * corresponding edge number in the fsa ranges from es1 to ef1.
231 *
232 * As g2 ranges from 1 to ngens+1 in the pair (g2,g3), for fixed g3, the
233 * corresponding edge number in the fsa ranges from g3 upwards, with
234 * increments of size ngens+1.
235 */
236
237 ptr = cs_ptr;
238 while (ptr <= cs_ptre) {
239 csa = *(ptr++);
240 csb = *(ptr++);
241 for (g2 = 1, e1 = es1, e2 = g3; e1 <= ef1; g2++, e1++, e2 += ngens1) {
242 csima = g1 == ngens1 && g2 == ngens1
243 ? (genmultptr->is_accepting[csa] ? csa : 0)
244 : target(dense_ip, table, e1, csa, dr);
245 if (csima == 0)
246 continue;
247
248 csimb = g2 == ngens1 && g3 == ngens1
249 ? (genmultptr->is_accepting[csb] ? csb : 0)
250 : target(dense_ip, table, e2, csb, dr);
251 if (csimb == 0)
252 continue;
253 if (ht_ptrb > ht_ptre || csima > *(ht_ptre - 1) ||
254 (csima == *(ht_ptre - 1) && csimb > *ht_ptre)) {
255 /* We have a new state for the image subset to be added to the end
256 */
257 *(++ht_ptre) = csima;
258 *(++ht_ptre) = csimb;
259 }
260 else {
261 ht_chptr = ht_ptrb;
262 while (*ht_chptr < csima)
263 ht_chptr += 2;
264 while (*ht_chptr == csima && *(ht_chptr + 1) < csimb)
265 ht_chptr += 2;
266 if (csima < *ht_chptr || csimb < *(ht_chptr + 1)) {
267 /* we have a new state for the image subset to be added in the
268 * middle */
269 ht_ptr = ht_ptre;
270 ht_ptre += 2;
271 while (ht_ptr >= ht_chptr) {
272 *(ht_ptr + 2) = *ht_ptr;
273 ht_ptr--;
274 }
275 *ht_chptr = csima;
276 *(ht_chptr + 1) = csimb;
277 }
278 }
279 }
280 }
281 if (ht_ptre > ht_ptrb) {
282 if (g1 == ngens1)
283 *(++ht_ptre) = 1;
284 else if (g3 == ngens1)
285 *(++ht_ptre) = 2;
286 }
287 im = short_hash_locate(&ht, ht_ptre - ht_ptrb + 1);
288 if (im > 0) {
289 if (dense_op)
290 fsarow[e - 1] = im;
291 else {
292 fsarow[++len] = e;
293 fsarow[++len] = im;
294 }
295 nt++;
296 }
297 }
298 if (!dense_op)
299 fsarow[0] = len++;
300 if (keeptable)
301 fwrite((void *)fsarow, sizeof(int), (size_t)len, tablefile);
302 }
303
304 if (keeptable)
305 fclose(tablefile);
306 tfree(fsarow);
307
308 ns = genmult2ptr->states->size = ht.num_recs;
309 genmult2ptr->table->numTransitions = nt;
310
311 if (kbm_print_level >= 3) {
312 printf(" #Calculated transitions - %d states, %d transitions.\n", ns,
313 nt);
314 printf(" #Now calculating state labels.\n");
315 }
316
317 /* Locate the accept states for Mult_(a*b) each generator pair (a,b).
318 * This is slightly cumbersome, since a state S
319 * is an accept state if either the subset representing S contains a
320 * pair (s1,s2), where s1 is accept state for Mult_a and s2 for Mult_b,
321 * or we can get from to such a state by applying ( ($,g), (g,$) ) to one
322 * of the pairs in S, for some generator g.
323 * It is most convenient to work out this information taking the states
324 * S in reverse order.
325 * The information on the accept-states will be stored as labels, which
326 * (13/9/95 - change labels from words to lists of words)
327 * will be lists of words in the generators. Each such list will have the form
328 * [a1*b1,a2*b2,...,ar*br], where the (ai,bi) are the generator pairs for
329 * which that particular state is an accept state. The labels will be
330 * collected initially in a new hash-table.
331 * The identity generator will be numbered ngens+1 and given name '_'
332 * rather than represented by the empty word. This is so that we can
333 * distinguish between multipliers for "_*a" and "a*_" if necessary.
334 */
335
336 genmult2ptr->states->type = LABELED;
337 tmalloc(genmult2ptr->states->labels, srec, 1);
338 labelset = genmult2ptr->states->labels;
339 labelset->type = LISTOFWORDS;
340 labelset->alphabet_size = ngens1;
341 for (i = 1; i <= ngens; i++) {
342 tmalloc(labelset->alphabet[i], char,
343 stringlen(genmultptr->states->labels->alphabet[i]) + 1);
344 strcpy(labelset->alphabet[i], genmultptr->states->labels->alphabet[i]);
345 }
346 tmalloc(labelset->alphabet[ngens1], char, 2);
347 labelset->alphabet[ngens1][0] = '_';
348 labelset->alphabet[ngens1][1] = 0;
349 tmalloc(genmult2ptr->states->setToLabels, setToLabelsType, ns + 1);
350 newlabel = genmult2ptr->states->setToLabels;
351 tmalloc(genmult2ptr->is_accepting, boolean, ns + 1);
352 for (i = 1; i <= ns; i++)
353 genmult2ptr->is_accepting[i] = FALSE;
354 short_hash_init(&labelht, FALSE, 0, LABHTSIZE, 2 * LABHTSIZE);
355
356 es1 = ngens * ngens1 + 1;
357 ef1 = ngens1 * ngens1 - 1;
358 for (cstate = ns; cstate >= 1; cstate--) {
359 /* We work backwards through the states, since we wish to add on additional
360 * elements at the end of the list in the hash-table - this destroys
361 * later entries, but that doesn't matter, since we have already dealt
362 * with them.
363 */
364 cs_ptr = short_hash_rec(&ht, cstate);
365 reclen = short_hash_rec_len(&ht, cstate);
366 if (reclen % 2 == 1)
367 reclen--;
368 /* The last entry only marks the fact that this is a "padded state"*/
369 cs_ptre = short_hash_rec(&ht, cstate) + reclen - 1;
370 /* Apply generators ( ($,g2), (g2,$) ) and see if we get anything new.
371 * We won't bother about having them in increasing order this time.
372 */
373 ptr = cs_ptr;
374 while (ptr <= cs_ptre) {
375 csa = *(ptr++);
376 csb = *(ptr++);
377 for (e1 = es1, e2 = ngens1; e1 <= ef1; e1++, e2 += ngens1) {
378 csima = target(dense_ip, table, e1, csa, dr);
379 if (csima == 0)
380 continue;
381 csimb = target(dense_ip, table, e2, csb, dr);
382 if (csimb == 0)
383 continue;
384 /* see if (csima,csimb) is new */
385 ht_chptr = cs_ptr;
386 got = FALSE;
387 while (ht_chptr < cs_ptre) {
388 if (csima == ht_chptr[0] && csimb == ht_chptr[1]) {
389 got = TRUE;
390 break;
391 }
392 ht_chptr += 2;
393 }
394 if (!got) {
395 /* add (csima,csimb) to the end */
396 *(++cs_ptre) = csima;
397 *(++cs_ptre) = csimb;
398 }
399 }
400 }
401 /* Now we see which pairs in the subset are of form (s,t), where s is
402 * an accept state for a generator a, and t for a generator b.
403 * The list of all such pairs (a,b) will form the label of the state, which
404 * will be the list of words [a1*b1,a2*b2,..,ar*br], with the (ai,bi) coming
405 * in lex-order.
406 */
407
408 ht_ptrb = labelht.current_ptr;
409 ht_ptre = ht_ptrb - 1;
410 ptr = cs_ptr;
411 while (ptr <= cs_ptre) {
412 csa = *(ptr++);
413 csb = *(ptr++);
414 if (((l1 = label[csa]) != 0) && ((l2 = label[csb]) != 0)) {
415 labellist1 = genmultptr->states->labels->wordslist[l1];
416 labellist2 = genmultptr->states->labels->wordslist[l2];
417 j1 = 0;
418 while (labellist1[j1]) {
419 g1 = labellist1[j1][0];
420 if (g1 == 0)
421 g1 = ngens1;
422 j2 = 0;
423 while (labellist2[j2]) {
424 genmult2ptr->is_accepting[cstate] = TRUE;
425 g2 = labellist2[j2][0];
426 if (g2 == 0)
427 g2 = ngens1;
428 if (ht_ptrb > ht_ptre || g1 > *(ht_ptre - 1) ||
429 (g1 == *(ht_ptre - 1) && g2 > *ht_ptre)) {
430 /* We have a new generator pair to be added to the end */
431 *(++ht_ptre) = g1;
432 *(++ht_ptre) = g2;
433 }
434 else {
435 ht_chptr = ht_ptrb;
436 while (*ht_chptr < g1)
437 ht_chptr += 2;
438 while (*ht_chptr == g1 && *(ht_chptr + 1) < g2)
439 ht_chptr += 2;
440 if (g1 < *ht_chptr || g2 < *(ht_chptr + 1)) {
441 /* we have a new generator pair to be added in the middle */
442 ht_ptr = ht_ptre;
443 ht_ptre += 2;
444 while (ht_ptr >= ht_chptr) {
445 *(ht_ptr + 2) = *ht_ptr;
446 ht_ptr--;
447 }
448 *ht_chptr = g1;
449 *(ht_chptr + 1) = g2;
450 }
451 }
452 j2++;
453 }
454 j1++;
455 }
456 }
457 }
458 /* That completes the calculation of the label for cstate */
459 newlabel[cstate] = short_hash_locate(&labelht, ht_ptre - ht_ptrb + 1);
460 }
461 short_hash_clear(&ht);
462
463 ct = 0;
464 for (i = 1; i <= ns; i++)
465 if (genmult2ptr->is_accepting[i])
466 ct++;
467 genmult2ptr->num_accepting = ct;
468 if (ct == 1 || ct != ns) {
469 tmalloc(genmult2ptr->accepting, int, ct + 1);
470 ct = 0;
471 for (i = 1; i <= ns; i++)
472 if (genmult2ptr->is_accepting[i])
473 genmult2ptr->accepting[++ct] = i;
474 }
475 tfree(genmult2ptr->is_accepting);
476 tfree(genmultptr->is_accepting);
477
478 /* Finally copy the records from the label hash-table into the set of labels
479 */
480 nlab = labelset->size = labelht.num_recs;
481 if (kbm_print_level >= 3)
482 printf(" #There are %d distinct labels.\n", nlab);
483 tmalloc(labelset->wordslist, gen **, nlab + 1);
484 for (i = 1; i <= nlab; i++) {
485 len = short_hash_rec_len(&labelht, i) / 2;
486 tmalloc(labelset->wordslist[i], gen *, len + 1);
487 ht_ptr = short_hash_rec(&labelht, i);
488 for (j = 0; j < len; j++) {
489 tmalloc(labelset->wordslist[i][j], gen, 3);
490 labelset->wordslist[i][j][0] = ht_ptr[2 * j];
491 labelset->wordslist[i][j][1] = ht_ptr[2 * j + 1];
492 labelset->wordslist[i][j][2] = 0;
493 }
494 labelset->wordslist[i][len] = 0;
495 }
496
497 short_hash_clear(&labelht);
498 if (destroy)
499 fsa_clear(genmultptr);
500
501 if (readback) {
502 tablefile = fopen(genmult2filename, "r");
503 compressed_transitions_read(genmult2ptr, tablefile);
504 fclose(tablefile);
505 unlink(genmult2filename);
506 }
507
508 return genmult2ptr;
509 }
510
fsa_genmult2_int(fsa * genmultptr,storage_type op_table_type,boolean destroy,char * genmult2filename,boolean readback)511 static fsa *fsa_genmult2_int(fsa *genmultptr, storage_type op_table_type,
512 boolean destroy, char *genmult2filename,
513 boolean readback)
514 {
515 int **table, ne, ngens, ngens1, ns, *fsarow, e, e1, e2, es1, ef1, dr, nt,
516 cstate, im, csa, csb, csima, csimb, i, j, j1, j2, g1, g2, g3, len = 0, reclen,
517 nlab, ct;
518 int *ht_ptr, *ht_chptr, *ht_ptrb, *ht_ptre, *cs_ptr, *cs_ptre, *ptr;
519 boolean dense_ip, dense_op, got, leftpad, rightpad, keeptable;
520 setToLabelsType *label, l1, l2, *newlabel;
521 gen **labellist1, **labellist2;
522 hash_table ht, labelht;
523 fsa *genmult2ptr;
524 srec *labelset;
525 FILE *tablefile = 0;
526
527 if (kbm_print_level >= 3)
528 printf(" #Calling fsa_genmult2_int.\n");
529 if (!genmultptr->flags[DFA]) {
530 fprintf(stderr, "Error: fsa_genmult2 only applies to DFA's.\n");
531 return 0;
532 }
533
534 if (genmultptr->alphabet->type != PRODUCT ||
535 genmultptr->alphabet->arity != 2) {
536 fprintf(stderr, "Error in fsa_genmult2: fsa must be 2-variable.\n");
537 return 0;
538 }
539
540 if (genmultptr->states->type != LABELED) {
541 fprintf(stderr, "Error in fsa_genmult2: states of fsa must be labeled.\n");
542 return 0;
543 }
544
545 keeptable = stringlen(genmult2filename) > 0;
546 if (readback && !keeptable) {
547 fprintf(stderr,
548 "Error in fsa_genmult2: readback true but empty filename.\n");
549 return 0;
550 }
551
552 tmalloc(genmult2ptr, fsa, 1);
553 fsa_init(genmult2ptr);
554 srec_copy(genmult2ptr->alphabet, genmultptr->alphabet);
555 genmult2ptr->num_initial = 1;
556 tmalloc(genmult2ptr->initial, int, 2);
557 genmult2ptr->initial[1] = 1;
558 genmult2ptr->flags[DFA] = TRUE;
559 genmult2ptr->flags[ACCESSIBLE] = TRUE;
560 genmult2ptr->flags[BFS] = TRUE;
561
562 genmult2ptr->table->table_type = op_table_type;
563 genmult2ptr->table->denserows = 0;
564 genmult2ptr->table->printing_format = op_table_type;
565 if (!readback) {
566 tmalloc(genmult2ptr->table->filename, char,
567 stringlen(genmult2filename) + 1);
568 strcpy(genmult2ptr->table->filename, genmult2filename);
569 }
570
571 ne = genmultptr->alphabet->size;
572 ngens = genmultptr->alphabet->base->size;
573 ngens1 = ngens + 1;
574
575 if (ne != ngens1 * ngens1 - 1) {
576 fprintf(stderr, "Error: in a 2-variable fsa, alphabet size should = "
577 "(ngens+1)^2 - 1.\n");
578 return 0;
579 }
580
581 fsa_set_is_accepting(genmultptr);
582
583 dense_ip = genmultptr->table->table_type == DENSE;
584 dr = genmultptr->table->denserows;
585 dense_op = op_table_type == DENSE;
586 table = genmultptr->table->table_data_ptr;
587
588 hash_init(&ht, FALSE, 0, 0, 0);
589 ht_ptr = ht.current_ptr;
590 ht_ptr[0] = genmultptr->initial[1];
591 ht_ptr[1] = genmultptr->initial[1];
592 im = hash_locate(&ht, 2);
593 /* Each state in the composite transition table will be represented as a
594 * subset of the set of ordered pairs of states of *genmultptr. The initial
595 * state contains just one such pair, of which both components are the initial
596 * state of *genmultptr. The subsets will be stored as variable-length records
597 * in the hash-table, as a list of pairs in increasing order. If a state is
598 * reached from a transition ($,x) or (x,$) (with $ the padding symbol), then
599 * it needs to be marked as such, since we do not allow a $ to be followed by
600 * any other generator. We do this by adding a 1 or a 2 to the end of the
601 * statelist - this is recognisable by the fact that the length of the
602 * statelist then becomes odd.
603 */
604 if (im != 1) {
605 fprintf(stderr, "Hash-initialisation problem in fsa_genmult2.\n");
606 return 0;
607 }
608 if (keeptable)
609 if ((tablefile = fopen(genmult2filename, "w")) == 0) {
610 fprintf(stderr, "Error: cannot open file %s\n", genmult2filename);
611 return 0;
612 }
613 if (dense_op)
614 tmalloc(fsarow, int, ne) else tmalloc(fsarow, int, 2 * ne + 1)
615
616 label = genmultptr->states->setToLabels;
617 cstate = 0;
618 if (dense_op)
619 len = ne; /* The length of the fsarow output. */
620 nt = 0; /* Number of transitions in genmult2ptr */
621
622 while (++cstate <= ht.num_recs) {
623 if (kbm_print_level >= 3) {
624 if ((cstate <= 1000 && cstate % 100 == 0) ||
625 (cstate <= 10000 && cstate % 1000 == 0) ||
626 (cstate <= 100000 && cstate % 5000 == 0) || cstate % 50000 == 0)
627 printf(" #cstate = %d; number of states = %d.\n", cstate,
628 ht.num_recs);
629 }
630 reclen = hash_rec_len(&ht, cstate);
631 cs_ptr = hash_rec(&ht, cstate);
632 cs_ptre = hash_rec(&ht, cstate) + reclen - 1;
633 if (reclen % 2 == 1) {
634 if (*cs_ptre == 1) {
635 leftpad = TRUE;
636 rightpad = FALSE;
637 }
638 else {
639 leftpad = FALSE;
640 rightpad = TRUE;
641 }
642 cs_ptre--;
643 }
644 else {
645 leftpad = FALSE;
646 rightpad = FALSE;
647 }
648
649 if (dense_op)
650 for (i = 0; i < ne; i++)
651 fsarow[i] = 0;
652 else
653 len = 0;
654
655 e = 0; /* e is the edge number of generator pair (g1,g3) */
656 for (g1 = 1; g1 <= ngens1; g1++)
657 for (g3 = 1; g3 <= ngens1; g3++) {
658 /* Calculate action of pair (g1,g3) on state cstate - to get the image,
659 * we have to apply ( (g1,g2), (g2,g3) ) to each ordered pair in the
660 * subset corresponding to cstate, * and this for each generator g2 of
661 * the base-alphabet (including the padding symbol).
662 */
663
664 e++;
665 if (g1 == ngens1 && g3 == ngens1)
666 continue;
667
668 if ((leftpad && g1 <= ngens) || (rightpad && g3 <= ngens))
669 continue;
670 ht_ptrb = ht.current_ptr;
671 ht_ptre = ht_ptrb - 1;
672
673 es1 = (g1 - 1) * ngens1 + 1;
674 ef1 = g1 * ngens1;
675 /* As g2 ranges from 1 to ngens+1 in the pair (g1,g2), for fixed g1, the
676 * corresponding edge number in the fsa ranges from es1 to ef1.
677 *
678 * As g2 ranges from 1 to ngens+1 in the pair (g2,g3), for fixed g3, the
679 * corresponding edge number in the fsa ranges from g3 upwards, with
680 * increments of size ngens+1.
681 */
682
683 ptr = cs_ptr;
684 while (ptr <= cs_ptre) {
685 csa = *(ptr++);
686 csb = *(ptr++);
687 for (g2 = 1, e1 = es1, e2 = g3; e1 <= ef1; g2++, e1++, e2 += ngens1) {
688 csima = g1 == ngens1 && g2 == ngens1
689 ? (genmultptr->is_accepting[csa] ? csa : 0)
690 : target(dense_ip, table, e1, csa, dr);
691 if (csima == 0)
692 continue;
693
694 csimb = g2 == ngens1 && g3 == ngens1
695 ? (genmultptr->is_accepting[csb] ? csb : 0)
696 : target(dense_ip, table, e2, csb, dr);
697 if (csimb == 0)
698 continue;
699 if (ht_ptrb > ht_ptre || csima > *(ht_ptre - 1) ||
700 (csima == *(ht_ptre - 1) && csimb > *ht_ptre)) {
701 /* We have a new state for the image subset to be added to the end
702 */
703 *(++ht_ptre) = csima;
704 *(++ht_ptre) = csimb;
705 }
706 else {
707 ht_chptr = ht_ptrb;
708 while (*ht_chptr < csima)
709 ht_chptr += 2;
710 while (*ht_chptr == csima && *(ht_chptr + 1) < csimb)
711 ht_chptr += 2;
712 if (csima < *ht_chptr || csimb < *(ht_chptr + 1)) {
713 /* we have a new state for the image subset to be added in the
714 * middle */
715 ht_ptr = ht_ptre;
716 ht_ptre += 2;
717 while (ht_ptr >= ht_chptr) {
718 *(ht_ptr + 2) = *ht_ptr;
719 ht_ptr--;
720 }
721 *ht_chptr = csima;
722 *(ht_chptr + 1) = csimb;
723 }
724 }
725 }
726 }
727 if (ht_ptre > ht_ptrb) {
728 if (g1 == ngens1)
729 *(++ht_ptre) = 1;
730 else if (g3 == ngens1)
731 *(++ht_ptre) = 2;
732 }
733 im = hash_locate(&ht, ht_ptre - ht_ptrb + 1);
734 if (im > 0) {
735 if (dense_op)
736 fsarow[e - 1] = im;
737 else {
738 fsarow[++len] = e;
739 fsarow[++len] = im;
740 }
741 nt++;
742 }
743 }
744 if (!dense_op)
745 fsarow[0] = len++;
746 if (keeptable)
747 fwrite((void *)fsarow, sizeof(int), (size_t)len, tablefile);
748 }
749
750 if (keeptable)
751 fclose(tablefile);
752 tfree(fsarow);
753
754 ns = genmult2ptr->states->size = ht.num_recs;
755 genmult2ptr->table->numTransitions = nt;
756
757 if (kbm_print_level >= 3) {
758 printf(" #Calculated transitions - %d states, %d transitions.\n", ns,
759 nt);
760 printf(" #Now calculating state labels.\n");
761 }
762
763 /* Locate the accept states for Mult_(a*b) each generator pair (a,b).
764 * This is slightly cumbersome, since a state S
765 * is an accept state if either the subset representing S contains a
766 * pair (s1,s2), where s1 is accept state for Mult_a and s2 for Mult_b,
767 * or we can get from to such a state by applying ( ($,g), (g,$) ) to one
768 * of the pairs in S, for some generator g.
769 * It is most convenient to work out this information taking the states
770 * S in reverse order.
771 * The information on the accept-states will be stored as labels, which
772 * (13/9/95 - change labels from words to lists of words)
773 * will be lists of words in the generators. Each such list will have the form
774 * [a1*b1,a2*b2,...,ar*br], where the (ai,bi) are the generator pairs for
775 * which that particular state is an accept state. The labels will be
776 * collected initially in a new hash-table.
777 * The identity generator will be numbered ngens+1 and given name '_'
778 * rather than represented by the empty word. This is so that we can
779 * distinguish between multipliers for "_*a" and "a*_" if necessary.
780 */
781
782 genmult2ptr->states->type = LABELED;
783 tmalloc(genmult2ptr->states->labels, srec, 1);
784 labelset = genmult2ptr->states->labels;
785 labelset->type = LISTOFWORDS;
786 labelset->alphabet_size = ngens1;
787 for (i = 1; i <= ngens; i++) {
788 tmalloc(labelset->alphabet[i], char,
789 stringlen(genmultptr->states->labels->alphabet[i]) + 1);
790 strcpy(labelset->alphabet[i], genmultptr->states->labels->alphabet[i]);
791 }
792 tmalloc(labelset->alphabet[ngens1], char, 2);
793 labelset->alphabet[ngens1][0] = '_';
794 labelset->alphabet[ngens1][1] = 0;
795 tmalloc(genmult2ptr->states->setToLabels, setToLabelsType, ns + 1);
796 newlabel = genmult2ptr->states->setToLabels;
797 tmalloc(genmult2ptr->is_accepting, boolean, ns + 1);
798 for (i = 1; i <= ns; i++)
799 genmult2ptr->is_accepting[i] = FALSE;
800 hash_init(&labelht, FALSE, 0, LABHTSIZE, 2 * LABHTSIZE);
801
802 es1 = ngens * ngens1 + 1;
803 ef1 = ngens1 * ngens1 - 1;
804 for (cstate = ns; cstate >= 1; cstate--) {
805 /* We work backwards through the states, since we wish to add on additional
806 * elements at the end of the list in the hash-table - this destroys
807 * later entries, but that doesn't matter, since we have already dealt
808 * with them.
809 */
810 cs_ptr = hash_rec(&ht, cstate);
811 reclen = hash_rec_len(&ht, cstate);
812 if (reclen % 2 == 1)
813 reclen--;
814 /* The last entry only marks the fact that this is a "padded state"*/
815 cs_ptre = hash_rec(&ht, cstate) + reclen - 1;
816 /* Apply generators ( ($,g2), (g2,$) ) and see if we get anything new.
817 * We won't bother about having them in increasing order this time.
818 */
819 ptr = cs_ptr;
820 while (ptr <= cs_ptre) {
821 csa = *(ptr++);
822 csb = *(ptr++);
823 for (e1 = es1, e2 = ngens1; e1 <= ef1; e1++, e2 += ngens1) {
824 csima = target(dense_ip, table, e1, csa, dr);
825 if (csima == 0)
826 continue;
827 csimb = target(dense_ip, table, e2, csb, dr);
828 if (csimb == 0)
829 continue;
830 /* see if (csima,csimb) is new */
831 ht_chptr = cs_ptr;
832 got = FALSE;
833 while (ht_chptr < cs_ptre) {
834 if (csima == ht_chptr[0] && csimb == ht_chptr[1]) {
835 got = TRUE;
836 break;
837 }
838 ht_chptr += 2;
839 }
840 if (!got) {
841 /* add (csima,csimb) to the end */
842 *(++cs_ptre) = csima;
843 *(++cs_ptre) = csimb;
844 }
845 }
846 }
847 /* Now we see which pairs in the subset are of form (s,t), where s is
848 * an accept state for a generator a, and t for a generator b.
849 * The list of all such pairs (a,b) will form the label of the state, which
850 * will be the list of words [a1*b1,a2*b2,..,ar*br], with the (ai,bi) coming
851 * in lex-order.
852 */
853
854 ht_ptrb = labelht.current_ptr;
855 ht_ptre = ht_ptrb - 1;
856 ptr = cs_ptr;
857 while (ptr <= cs_ptre) {
858 csa = *(ptr++);
859 csb = *(ptr++);
860 if (((l1 = label[csa]) != 0) && ((l2 = label[csb]) != 0)) {
861 labellist1 = genmultptr->states->labels->wordslist[l1];
862 labellist2 = genmultptr->states->labels->wordslist[l2];
863 j1 = 0;
864 while (labellist1[j1]) {
865 g1 = labellist1[j1][0];
866 if (g1 == 0)
867 g1 = ngens1;
868 j2 = 0;
869 while (labellist2[j2]) {
870 genmult2ptr->is_accepting[cstate] = TRUE;
871 g2 = labellist2[j2][0];
872 if (g2 == 0)
873 g2 = ngens1;
874 if (ht_ptrb > ht_ptre || g1 > *(ht_ptre - 1) ||
875 (g1 == *(ht_ptre - 1) && g2 > *ht_ptre)) {
876 /* We have a new generator pair to be added to the end */
877 *(++ht_ptre) = g1;
878 *(++ht_ptre) = g2;
879 }
880 else {
881 ht_chptr = ht_ptrb;
882 while (*ht_chptr < g1)
883 ht_chptr += 2;
884 while (*ht_chptr == g1 && *(ht_chptr + 1) < g2)
885 ht_chptr += 2;
886 if (g1 < *ht_chptr || g2 < *(ht_chptr + 1)) {
887 /* we have a new generator pair to be added in the middle */
888 ht_ptr = ht_ptre;
889 ht_ptre += 2;
890 while (ht_ptr >= ht_chptr) {
891 *(ht_ptr + 2) = *ht_ptr;
892 ht_ptr--;
893 }
894 *ht_chptr = g1;
895 *(ht_chptr + 1) = g2;
896 }
897 }
898 j2++;
899 }
900 j1++;
901 }
902 }
903 }
904 /* That completes the calculation of the label for cstate */
905 newlabel[cstate] = hash_locate(&labelht, ht_ptre - ht_ptrb + 1);
906 }
907 hash_clear(&ht);
908
909 ct = 0;
910 for (i = 1; i <= ns; i++)
911 if (genmult2ptr->is_accepting[i])
912 ct++;
913 genmult2ptr->num_accepting = ct;
914 if (ct == 1 || ct != ns) {
915 tmalloc(genmult2ptr->accepting, int, ct + 1);
916 ct = 0;
917 for (i = 1; i <= ns; i++)
918 if (genmult2ptr->is_accepting[i])
919 genmult2ptr->accepting[++ct] = i;
920 }
921 tfree(genmult2ptr->is_accepting);
922 tfree(genmultptr->is_accepting);
923
924 /* Finally copy the records from the label hash-table into the set of labels
925 */
926 nlab = labelset->size = labelht.num_recs;
927 if (kbm_print_level >= 3)
928 printf(" #There are %d distinct labels.\n", nlab);
929 tmalloc(labelset->wordslist, gen **, nlab + 1);
930 for (i = 1; i <= nlab; i++) {
931 len = hash_rec_len(&labelht, i) / 2;
932 tmalloc(labelset->wordslist[i], gen *, len + 1);
933 ht_ptr = hash_rec(&labelht, i);
934 for (j = 0; j < len; j++) {
935 tmalloc(labelset->wordslist[i][j], gen, 3);
936 labelset->wordslist[i][j][0] = ht_ptr[2 * j];
937 labelset->wordslist[i][j][1] = ht_ptr[2 * j + 1];
938 labelset->wordslist[i][j][2] = 0;
939 }
940 labelset->wordslist[i][len] = 0;
941 }
942
943 hash_clear(&labelht);
944 if (destroy)
945 fsa_clear(genmultptr);
946
947 if (readback) {
948 tablefile = fopen(genmult2filename, "r");
949 compressed_transitions_read(genmult2ptr, tablefile);
950 fclose(tablefile);
951 unlink(genmult2filename);
952 }
953
954 return genmult2ptr;
955 }
956
957 /* This procedure takes the fsa *genmultptr produced by fsa_triples,
958 * and builds a particular multiplier Mult_g1.
959 * This merely involves setting the accept states of *genmultptr
960 * in accordance with the labels of its states.
961 * g can be 0, for the identity generator, which (in shortlex case) inevitably
962 * produces the diagonal of the word-acceptor.
963 * This procedure alters its arguments and does not return anything.
964 */
fsa_makemult(fsa * genmultptr,int g)965 int fsa_makemult(fsa *genmultptr, int g)
966 {
967 int ngens, ns, i, j, ct;
968 gen **labellist;
969 setToLabelsType *label;
970
971 if (kbm_print_level >= 3)
972 printf(" #Calling fsa_makemult with generator number %d.\n", g);
973 if (!genmultptr->flags[DFA]) {
974 fprintf(stderr, "Error: fsa_makemult only applies to DFA's.\n");
975 return -1;
976 }
977
978 if (genmultptr->alphabet->type != PRODUCT ||
979 genmultptr->alphabet->arity != 2) {
980 fprintf(stderr, "Error in fsa_makemult: fsa must be 2-variable.\n");
981 return -1;
982 }
983
984 if (genmultptr->states->type != LABELED) {
985 fprintf(stderr, "Error in fsa_makemult: states of fsa must be labeled.\n");
986 return -1;
987 }
988
989 ns = genmultptr->states->size;
990 ngens = genmultptr->alphabet->base->size;
991 if (g < 0 || g > ngens + 1) {
992 fprintf(stderr, "#Error in fsa_makemult: Generator is out of range.\n");
993 return -1;
994 }
995
996 tfree(genmultptr->accepting);
997 tfree(genmultptr->is_accepting);
998 label = genmultptr->states->setToLabels;
999 ct = 0;
1000 for (i = 1; i <= ns; i++)
1001 if (label[i] > 0) {
1002 labellist = genmultptr->states->labels->wordslist[label[i]];
1003 j = 0;
1004 while (labellist[j]) {
1005 if (labellist[j][0] == g)
1006 ct++;
1007 j++;
1008 }
1009 }
1010 genmultptr->num_accepting = ct;
1011 if (ct < ns || ns == 1) {
1012 tfree(genmultptr->accepting);
1013 tmalloc(genmultptr->accepting, int, ct + 1);
1014 ct = 0;
1015 for (i = 1; i <= ns; i++)
1016 if (label[i] > 0) {
1017 labellist = genmultptr->states->labels->wordslist[label[i]];
1018 j = 0;
1019 while (labellist[j]) {
1020 if (labellist[j][0] == g)
1021 genmultptr->accepting[++ct] = i;
1022 j++;
1023 }
1024 }
1025 }
1026 /* The state labelling is no longer relevant, so we clear it */
1027 genmultptr->states->type = SIMPLE;
1028 srec_clear(genmultptr->states->labels);
1029 tfree(genmultptr->states->labels);
1030 tfree(genmultptr->states->setToLabels);
1031 return 0;
1032 }
1033
1034 /* This procedure takes the fsa *genmult2ptr produced by fsa_genmult2,
1035 * and builds a particular length-2 multiplier Mult_g1g2.
1036 * This merely involves locating the accept states.
1037 * This procedure alters its arguments and does not return anything.
1038 */
fsa_makemult2(fsa * genmult2ptr,int g1,int g2)1039 int fsa_makemult2(fsa *genmult2ptr, int g1, int g2)
1040 {
1041 int ngens, ns, nlabs, i, j, ct;
1042 gen ***labellist;
1043 boolean *accept;
1044 setToLabelsType *labelnumber;
1045
1046 if (kbm_print_level >= 3)
1047 printf(" #Calling fsa_makemult2 with generators %d and %d.\n", g1, g2);
1048 if (!genmult2ptr->flags[DFA]) {
1049 fprintf(stderr, "Error: fsa_makemult2 only applies to DFA's.\n");
1050 return -1;
1051 }
1052
1053 if (genmult2ptr->alphabet->type != PRODUCT ||
1054 genmult2ptr->alphabet->arity != 2) {
1055 fprintf(stderr, "Error in fsa_makemult2: fsa must be 2-variable.\n");
1056 return -1;
1057 }
1058
1059 if (genmult2ptr->states->type != LABELED) {
1060 fprintf(stderr, "Error in fsa_makemult2: states of fsa must be labeled.\n");
1061 return -1;
1062 }
1063
1064 if (genmult2ptr->states->labels->type != LISTOFWORDS) {
1065 fprintf(stderr, "Error in fsa_makemult2: labels must be lists of words.\n");
1066 return -1;
1067 }
1068
1069 ns = genmult2ptr->states->size;
1070 nlabs = genmult2ptr->states->labels->size;
1071 ngens = genmult2ptr->states->labels->alphabet_size;
1072 if (g1 <= 0 || g1 > ngens || g2 <= 0 || g2 > ngens) {
1073 fprintf(stderr, "#Error in fsa_makemult2: A generator is out of range.\n");
1074 return -1;
1075 }
1076
1077 tmalloc(accept, boolean, nlabs + 1);
1078 labellist = genmult2ptr->states->labels->wordslist;
1079 /* Now we see which labels are accept-labels for the pair (g1,g2) - the
1080 * label is an accept-label if the list of words which is its name
1081 * contains g1*g2.
1082 */
1083 accept[0] = FALSE;
1084 for (i = 1; i <= nlabs; i++) {
1085 accept[i] = FALSE;
1086 j = 0;
1087 while (labellist[i][j]) {
1088 if (labellist[i][j][0] == g1 && labellist[i][j][1] == g2) {
1089 accept[i] = TRUE;
1090 break;
1091 }
1092 j++;
1093 }
1094 }
1095
1096 /* Now we can see which states are accept-states. A state is an accept-state
1097 * iff its label is an accept-label.
1098 * First we count the number.
1099 */
1100 ct = 0;
1101 labelnumber = genmult2ptr->states->setToLabels;
1102 for (i = 1; i <= ns; i++)
1103 if (accept[labelnumber[i]])
1104 ct++;
1105
1106 genmult2ptr->num_accepting = ct;
1107 if (ct < ns || ns == 1) {
1108 tfree(genmult2ptr->accepting);
1109 tmalloc(genmult2ptr->accepting, int, ct + 1);
1110 ct = 0;
1111 for (i = 1; i <= ns; i++)
1112 if (accept[labelnumber[i]])
1113 genmult2ptr->accepting[++ct] = i;
1114 }
1115
1116 tfree(accept);
1117
1118 /* The state labelling is no longer relevant, so we clear it */
1119 genmult2ptr->states->type = SIMPLE;
1120 srec_clear(genmult2ptr->states->labels);
1121 tfree(genmult2ptr->states->labels);
1122 tfree(genmult2ptr->states->setToLabels);
1123 return 0;
1124 }
1125
1126 /* *mult1ptr and *mult2ptr should be multiplier fsa's of an automatic group.
1127 * This function calculates the composite of these two multipliers.
1128 * So if *mult1ptr is the mutiplier for the word w1 and *mult2ptr for w2,
1129 * then the returned fsa is the multiplier for w1*w2.
1130 * In fact, *mult1ptr and *mult2ptr can be any 2-variable automata over the
1131 * same alphabet, and the composite is returned.
1132 */
fsa_composite(fsa * mult1ptr,fsa * mult2ptr,storage_type op_table_type,boolean destroy,char * compfilename,boolean readback)1133 fsa *fsa_composite(fsa *mult1ptr, fsa *mult2ptr, storage_type op_table_type,
1134 boolean destroy, char *compfilename, boolean readback)
1135 {
1136 if (kbm_print_level >= 3)
1137 printf(" #Calling fsa_composite.\n");
1138 if (mult1ptr->states->size < MAXUSHORT && mult2ptr->states->size < MAXUSHORT)
1139 return fsa_composite_short(mult1ptr, mult2ptr, op_table_type, destroy,
1140 compfilename, readback);
1141 else
1142 return fsa_composite_int(mult1ptr, mult2ptr, op_table_type, destroy,
1143 compfilename, readback);
1144 }
1145
fsa_composite_short(fsa * mult1ptr,fsa * mult2ptr,storage_type op_table_type,boolean destroy,char * compfilename,boolean readback)1146 static fsa *fsa_composite_short(fsa *mult1ptr, fsa *mult2ptr,
1147 storage_type op_table_type, boolean destroy,
1148 char *compfilename, boolean readback)
1149 {
1150 int **table1, **table2, ne, ngens, ngens1, ns, *fsarow, e, e1, e2, es1, ef1,
1151 dr1, dr2, nt, cstate, im, csa, csb, csima, csimb, i, ct, g1, g2, g3, len = 0,
1152 reclen;
1153 unsigned short *ht_ptr, *ht_chptr, *ht_ptrb, *ht_ptre, *cs_ptr, *cs_ptre,
1154 *ptr;
1155 boolean dense_ip1, dense_ip2, dense_op, got, leftpad, rightpad;
1156 short_hash_table ht;
1157 fsa *compositeptr;
1158 FILE *tempfile;
1159
1160 if (kbm_print_level >= 3)
1161 printf(" #Calling fsa_composite_short.\n");
1162 if (!mult1ptr->flags[DFA] || !mult2ptr->flags[DFA]) {
1163 fprintf(stderr, "Error: fsa_composite only applies to DFA's.\n");
1164 return 0;
1165 }
1166
1167 if (mult1ptr->alphabet->type != PRODUCT || mult1ptr->alphabet->arity != 2) {
1168 fprintf(stderr, "Error in fsa_composite: fsa must be 2-variable.\n");
1169 return 0;
1170 }
1171 if (mult2ptr->alphabet->type != PRODUCT || mult2ptr->alphabet->arity != 2) {
1172 fprintf(stderr, "Error in fsa_composite: fsa must be 2-variable.\n");
1173 return 0;
1174 }
1175
1176 if (!srec_equal(mult1ptr->alphabet, mult2ptr->alphabet)) {
1177 fprintf(stderr, "Error in fsa_composite: fsa's must have same alphabet.\n");
1178 return 0;
1179 }
1180
1181 tmalloc(compositeptr, fsa, 1);
1182 fsa_init(compositeptr);
1183 srec_copy(compositeptr->alphabet, mult1ptr->alphabet);
1184 compositeptr->states->type = SIMPLE;
1185 compositeptr->num_initial = 1;
1186 tmalloc(compositeptr->initial, int, 2);
1187 compositeptr->initial[1] = 1;
1188 compositeptr->flags[DFA] = TRUE;
1189 compositeptr->flags[ACCESSIBLE] = TRUE;
1190 compositeptr->flags[BFS] = TRUE;
1191
1192 compositeptr->table->table_type = op_table_type;
1193 compositeptr->table->denserows = 0;
1194 compositeptr->table->printing_format = op_table_type;
1195 if (!readback) {
1196 tmalloc(compositeptr->table->filename, char, stringlen(compfilename) + 1);
1197 strcpy(compositeptr->table->filename, compfilename);
1198 }
1199
1200 ne = mult1ptr->alphabet->size;
1201 ngens = mult1ptr->alphabet->base->size;
1202 ngens1 = ngens + 1;
1203
1204 if (ne != ngens1 * ngens1 - 1) {
1205 fprintf(stderr, "Error: in a 2-variable fsa, alphabet size should = "
1206 "(ngens+1)^2 - 1.\n");
1207 return 0;
1208 }
1209
1210 fsa_set_is_accepting(mult1ptr);
1211 fsa_set_is_accepting(mult2ptr);
1212
1213 dense_ip1 = mult1ptr->table->table_type == DENSE;
1214 dr1 = mult1ptr->table->denserows;
1215 dense_ip2 = mult2ptr->table->table_type == DENSE;
1216 dr2 = mult2ptr->table->denserows;
1217 dense_op = op_table_type == DENSE;
1218 table1 = mult1ptr->table->table_data_ptr;
1219 table2 = mult2ptr->table->table_data_ptr;
1220
1221 short_hash_init(&ht, FALSE, 0, 0, 0);
1222 ht_ptr = ht.current_ptr;
1223 ht_ptr[0] = mult1ptr->initial[1];
1224 ht_ptr[1] = mult2ptr->initial[1];
1225 im = short_hash_locate(&ht, 2);
1226 /* Each state in the composite transition table will be represented as a
1227 * subset of the set of ordered pairs in which the first component is a state
1228 * in *multptr1 and the second a state in *multptr2. The initial state
1229 * contains just one such pair, of which the components are the initial states
1230 * of *mult1ptr and *multptr2. The subsets will be stored as variable-length
1231 * records in the hash-table, as a list of pairs in increasing order. If a
1232 * state is reached from a transition ($,x) or (x,$) (with $ the padding
1233 * symbol), then it needs to be marked as such, since we do not allow a $
1234 * to be followed by any other generator.
1235 * We do this by adding a 1 or a 2 to the end of the statelist - this is
1236 * recognisable by the fact that the length of the statelist then becomes odd.
1237 */
1238 if (im != 1) {
1239 fprintf(stderr, "Hash-initialisation problem in fsa_composite.\n");
1240 return 0;
1241 }
1242 if ((tempfile = fopen(compfilename, "w")) == 0) {
1243 fprintf(stderr, "Error: cannot open file %s\n", compfilename);
1244 return 0;
1245 }
1246 if (dense_op)
1247 tmalloc(fsarow, int, ne) else tmalloc(fsarow, int, 2 * ne + 1)
1248
1249 cstate = 0;
1250 if (dense_op)
1251 len = ne; /* The length of the fsarow output. */
1252 nt = 0; /* Number of transitions in compositeptr */
1253
1254 while (++cstate <= ht.num_recs) {
1255 if (kbm_print_level >= 3) {
1256 if ((cstate <= 1000 && cstate % 100 == 0) ||
1257 (cstate <= 10000 && cstate % 1000 == 0) ||
1258 (cstate <= 100000 && cstate % 5000 == 0) || cstate % 50000 == 0)
1259 printf(" #cstate = %d; number of states = %d.\n", cstate,
1260 ht.num_recs);
1261 }
1262 reclen = short_hash_rec_len(&ht, cstate);
1263 cs_ptr = short_hash_rec(&ht, cstate);
1264 cs_ptre = short_hash_rec(&ht, cstate) + reclen - 1;
1265 /* for (i=0;i<reclen;i++) printf(" %d",cs_ptr[i]); printf("\n"); */
1266 if (reclen % 2 == 1) {
1267 if (*cs_ptre == 1) {
1268 leftpad = TRUE;
1269 rightpad = FALSE;
1270 }
1271 else {
1272 leftpad = FALSE;
1273 rightpad = TRUE;
1274 }
1275 cs_ptre--;
1276 }
1277 else {
1278 leftpad = FALSE;
1279 rightpad = FALSE;
1280 }
1281
1282 if (dense_op)
1283 for (i = 0; i < ne; i++)
1284 fsarow[i] = 0;
1285 else
1286 len = 0;
1287
1288 e = 0; /* e is the edge number of generator pair (g1,g3) */
1289 for (g1 = 1; g1 <= ngens1; g1++)
1290 for (g3 = 1; g3 <= ngens1; g3++) {
1291 /* Calculate action of pair (g1,g3) on state cstate - to get the image,
1292 * we have to apply ( (g1,g2), (g2,g3) ) to each ordered pair in the
1293 * subset corresponding to cstate, and this for each generator g2 of the
1294 * base-alphabet (including the padding symbol).
1295 */
1296 e++;
1297 if (g1 == ngens1 && g3 == ngens1)
1298 continue;
1299 if ((leftpad && g1 <= ngens) || (rightpad && g3 <= ngens))
1300 continue;
1301 ht_ptrb = ht.current_ptr;
1302 ht_ptre = ht_ptrb - 1;
1303 es1 = (g1 - 1) * ngens1 + 1;
1304 ef1 = g1 * ngens1;
1305 /* As g2 ranges from 1 to ngens+1 in the pair (g1,g2), for fixed g1, the
1306 * corresponding edge number in the fsa ranges from es1 to ef1.
1307 *
1308 * As g2 ranges from 1 to ngens+1 in the pair (g2,g3), for fixed g3, the
1309 * corresponding edge number in the fsa ranges from g3 upwards, with
1310 * increments of size ngens+1.
1311 */
1312
1313 ptr = cs_ptr;
1314 while (ptr <= cs_ptre) {
1315 csa = *(ptr++);
1316 csb = *(ptr++);
1317 for (g2 = 1, e1 = es1, e2 = g3; e1 <= ef1; g2++, e1++, e2 += ngens1) {
1318 csima = g1 == ngens1 && g2 == ngens1
1319 ? (mult1ptr->is_accepting[csa] > 0 ? csa : 0)
1320 : target(dense_ip1, table1, e1, csa, dr1);
1321 if (csima == 0)
1322 continue;
1323
1324 csimb = g2 == ngens1 && g3 == ngens1
1325 ? (mult2ptr->is_accepting[csb] > 0 ? csb : 0)
1326 : target(dense_ip2, table2, e2, csb, dr2);
1327 if (csimb == 0)
1328 continue;
1329
1330 if (ht_ptrb > ht_ptre || csima > *(ht_ptre - 1) ||
1331 (csima == *(ht_ptre - 1) && csimb > *ht_ptre)) {
1332 /* We have a new state for the image subset to be added to the end
1333 */
1334 *(++ht_ptre) = csima;
1335 *(++ht_ptre) = csimb;
1336 }
1337 else {
1338 ht_chptr = ht_ptrb;
1339 while (*ht_chptr < csima)
1340 ht_chptr += 2;
1341 while (*ht_chptr == csima && *(ht_chptr + 1) < csimb)
1342 ht_chptr += 2;
1343 if (csima < *ht_chptr || csimb < *(ht_chptr + 1)) {
1344 /* we have a new state for the image subset to be added in the
1345 * middle */
1346 ht_ptr = ht_ptre;
1347 ht_ptre += 2;
1348 while (ht_ptr >= ht_chptr) {
1349 *(ht_ptr + 2) = *ht_ptr;
1350 ht_ptr--;
1351 }
1352 *ht_chptr = csima;
1353 *(ht_chptr + 1) = csimb;
1354 }
1355 }
1356 }
1357 }
1358 if (ht_ptre > ht_ptrb) {
1359 if (g1 == ngens1)
1360 *(++ht_ptre) = 1;
1361 else if (g3 == ngens1)
1362 *(++ht_ptre) = 2;
1363 }
1364 im = short_hash_locate(&ht, ht_ptre - ht_ptrb + 1);
1365 if (im > 0) {
1366 if (dense_op)
1367 fsarow[e - 1] = im;
1368 else {
1369 fsarow[++len] = e;
1370 fsarow[++len] = im;
1371 }
1372 nt++;
1373 }
1374 }
1375 if (!dense_op)
1376 fsarow[0] = len++;
1377 fwrite((void *)fsarow, sizeof(int), (size_t)len, tempfile);
1378 }
1379 fclose(tempfile);
1380
1381 ns = compositeptr->states->size = ht.num_recs;
1382 compositeptr->table->numTransitions = nt;
1383
1384 if (kbm_print_level >= 3)
1385 printf(" #Calculated transitions - %d states, %d transitions.\n", ns,
1386 nt);
1387
1388 /* Locate the accept states. This is slightly cumbersome, since a state
1389 * is an accept state if either the corresponding subset contains a
1390 * a pair (s1,s2), where s1 is and accept state of *mult1ptr and s2 an
1391 * accept state of *mult2ptr, or we can get from some such state to an
1392 * accept state by applying elements ( ($,x), (x,$ ).
1393 * We will need to use the array compositeptr->is_accepting.
1394 */
1395
1396 tmalloc(compositeptr->is_accepting, boolean, ns + 1);
1397 for (i = 1; i <= ns; i++)
1398 compositeptr->is_accepting[i] = FALSE;
1399 ct = 0;
1400 es1 = ngens * ngens1 + 1;
1401 ef1 = ngens1 * ngens1 - 1;
1402 for (cstate = ns; cstate >= 1; cstate--) {
1403 /* We work backwards through the states, since we wish to add on additional
1404 * elements at the end of the list in the hash-table - this destroys
1405 * later entries, but that doesn't matter, since we have already dealt
1406 * with them.
1407 */
1408 cs_ptr = short_hash_rec(&ht, cstate);
1409 reclen = short_hash_rec_len(&ht, cstate);
1410 if (reclen % 2 == 1)
1411 reclen--; /* The last entry marks the fact that this is a "padded state"*/
1412 cs_ptre = short_hash_rec(&ht, cstate) + reclen - 1;
1413 /* First see if the set itself contains an accept-state */
1414 ptr = cs_ptr;
1415 while (ptr <= cs_ptre) {
1416 csa = *(ptr++);
1417 csb = *(ptr++);
1418 if (mult1ptr->is_accepting[csa] && mult2ptr->is_accepting[csb]) {
1419 compositeptr->is_accepting[cstate] = TRUE;
1420 ct++;
1421 break;
1422 }
1423 }
1424 if (compositeptr->is_accepting[cstate])
1425 continue;
1426 /* Next apply generators ( ($,g2), (g2,$) ) and see if we get anything new.
1427 * We won't bother about having them in increasing order this time.
1428 */
1429 ptr = cs_ptr;
1430 while (ptr <= cs_ptre) {
1431 csa = *(ptr++);
1432 csb = *(ptr++);
1433 for (e1 = es1, e2 = ngens1; e1 <= ef1; e1++, e2 += ngens1) {
1434 csima = target(dense_ip1, table1, e1, csa, dr1);
1435 if (csima == 0)
1436 continue;
1437 csimb = target(dense_ip2, table2, e2, csb, dr2);
1438 if (csimb == 0)
1439 continue;
1440
1441 /* see if (csima,csimb) is accepting */
1442 if (mult1ptr->is_accepting[csima] && mult2ptr->is_accepting[csimb]) {
1443 compositeptr->is_accepting[cstate] = TRUE;
1444 ct++;
1445 break;
1446 }
1447 /* now see if it is new */
1448 ht_chptr = cs_ptr;
1449 got = FALSE;
1450 while (ht_chptr < cs_ptre) {
1451 if (csima == ht_chptr[0] && csimb == ht_chptr[1]) {
1452 got = TRUE;
1453 break;
1454 }
1455 ht_chptr += 2;
1456 }
1457 if (!got) {
1458 /* add (csima,csimb) to the end */
1459 *(++cs_ptre) = csima;
1460 *(++cs_ptre) = csimb;
1461 }
1462 }
1463 if (compositeptr->is_accepting[cstate])
1464 continue;
1465 }
1466 }
1467
1468 compositeptr->num_accepting = ct;
1469 if (ct == 1 || ct != ns) {
1470 tmalloc(compositeptr->accepting, int, ct + 1);
1471 ct = 0;
1472 for (i = 1; i <= ns; i++)
1473 if (compositeptr->is_accepting[i])
1474 compositeptr->accepting[++ct] = i;
1475 }
1476 tfree(compositeptr->is_accepting);
1477 tfree(mult1ptr->is_accepting);
1478 tfree(mult2ptr->is_accepting);
1479 short_hash_clear(&ht);
1480 tfree(fsarow);
1481 if (destroy) {
1482 fsa_clear(mult1ptr);
1483 fsa_clear(mult2ptr);
1484 }
1485
1486 if (readback) {
1487 tempfile = fopen(compfilename, "r");
1488 compressed_transitions_read(compositeptr, tempfile);
1489 fclose(tempfile);
1490 unlink(compfilename);
1491 }
1492
1493 return compositeptr;
1494 }
1495
fsa_composite_int(fsa * mult1ptr,fsa * mult2ptr,storage_type op_table_type,boolean destroy,char * compfilename,boolean readback)1496 static fsa *fsa_composite_int(fsa *mult1ptr, fsa *mult2ptr,
1497 storage_type op_table_type, boolean destroy,
1498 char *compfilename, boolean readback)
1499 {
1500 int **table1, **table2, ne, ngens, ngens1, ns, *fsarow, e, e1, e2, es1, ef1,
1501 dr1, dr2, nt, cstate, im, csa, csb, csima, csimb, i, ct, g1, g2, g3, len = 0,
1502 reclen;
1503 int *ht_ptr, *ht_chptr, *ht_ptrb, *ht_ptre, *cs_ptr, *cs_ptre, *ptr;
1504 boolean dense_ip1, dense_ip2, dense_op, got, leftpad, rightpad;
1505 hash_table ht;
1506 fsa *compositeptr;
1507 FILE *tempfile;
1508
1509 if (kbm_print_level >= 3)
1510 printf(" #Calling fsa_composite_int.\n");
1511 if (!mult1ptr->flags[DFA] || !mult2ptr->flags[DFA]) {
1512 fprintf(stderr, "Error: fsa_composite only applies to DFA's.\n");
1513 return 0;
1514 }
1515
1516 if (mult1ptr->alphabet->type != PRODUCT || mult1ptr->alphabet->arity != 2) {
1517 fprintf(stderr, "Error in fsa_composite: fsa must be 2-variable.\n");
1518 return 0;
1519 }
1520 if (mult2ptr->alphabet->type != PRODUCT || mult2ptr->alphabet->arity != 2) {
1521 fprintf(stderr, "Error in fsa_composite: fsa must be 2-variable.\n");
1522 return 0;
1523 }
1524
1525 if (!srec_equal(mult1ptr->alphabet, mult2ptr->alphabet)) {
1526 fprintf(stderr, "Error in fsa_composite: fsa's must have same alphabet.\n");
1527 return 0;
1528 }
1529
1530 tmalloc(compositeptr, fsa, 1);
1531 fsa_init(compositeptr);
1532 srec_copy(compositeptr->alphabet, mult1ptr->alphabet);
1533 compositeptr->states->type = SIMPLE;
1534 compositeptr->num_initial = 1;
1535 tmalloc(compositeptr->initial, int, 2);
1536 compositeptr->initial[1] = 1;
1537 compositeptr->flags[DFA] = TRUE;
1538 compositeptr->flags[ACCESSIBLE] = TRUE;
1539 compositeptr->flags[BFS] = TRUE;
1540
1541 compositeptr->table->table_type = op_table_type;
1542 compositeptr->table->denserows = 0;
1543 compositeptr->table->printing_format = op_table_type;
1544 if (!readback) {
1545 tmalloc(compositeptr->table->filename, char, stringlen(compfilename) + 1);
1546 strcpy(compositeptr->table->filename, compfilename);
1547 }
1548
1549 ne = mult1ptr->alphabet->size;
1550 ngens = mult1ptr->alphabet->base->size;
1551 ngens1 = ngens + 1;
1552
1553 if (ne != ngens1 * ngens1 - 1) {
1554 fprintf(stderr, "Error: in a 2-variable fsa, alphabet size should = "
1555 "(ngens+1)^2 - 1.\n");
1556 return 0;
1557 }
1558
1559 fsa_set_is_accepting(mult1ptr);
1560 fsa_set_is_accepting(mult2ptr);
1561
1562 dense_ip1 = mult1ptr->table->table_type == DENSE;
1563 dr1 = mult1ptr->table->denserows;
1564 dense_ip2 = mult2ptr->table->table_type == DENSE;
1565 dr2 = mult2ptr->table->denserows;
1566 dense_op = op_table_type == DENSE;
1567 table1 = mult1ptr->table->table_data_ptr;
1568 table2 = mult2ptr->table->table_data_ptr;
1569
1570 hash_init(&ht, FALSE, 0, 0, 0);
1571 ht_ptr = ht.current_ptr;
1572 ht_ptr[0] = mult1ptr->initial[1];
1573 ht_ptr[1] = mult2ptr->initial[1];
1574 im = hash_locate(&ht, 2);
1575 /* Each state in the composite transition table will be represented as a
1576 * subset of the set of ordered pairs in which the first component is a state
1577 * in *multptr1 and the second a state in *multptr2. The initial state
1578 * contains just one such pair, of which the components are the initial states
1579 * of *mult1ptr and *multptr2. The subsets will be stored as variable-length
1580 * records in the hash-table, as a list of pairs in increasing order. If a
1581 * state is reached from a transition ($,x) or (x,$) (with $ the padding
1582 * symbol), then it needs to be marked as such, since we do not allow a $
1583 * to be followed by any other generator.
1584 * We do this by adding a 1 or a 2 to the end of the statelist - this is
1585 * recognisable by the fact that the length of the statelist then becomes odd.
1586 */
1587 if (im != 1) {
1588 fprintf(stderr, "Hash-initialisation problem in fsa_composite.\n");
1589 return 0;
1590 }
1591 if ((tempfile = fopen(compfilename, "w")) == 0) {
1592 fprintf(stderr, "Error: cannot open file %s\n", compfilename);
1593 return 0;
1594 }
1595 if (dense_op)
1596 tmalloc(fsarow, int, ne) else tmalloc(fsarow, int, 2 * ne + 1)
1597
1598 cstate = 0;
1599 if (dense_op)
1600 len = ne; /* The length of the fsarow output. */
1601 nt = 0; /* Number of transitions in compositeptr */
1602
1603 while (++cstate <= ht.num_recs) {
1604 if (kbm_print_level >= 3) {
1605 if ((cstate <= 1000 && cstate % 100 == 0) ||
1606 (cstate <= 10000 && cstate % 1000 == 0) ||
1607 (cstate <= 100000 && cstate % 5000 == 0) || cstate % 50000 == 0)
1608 printf(" #cstate = %d; number of states = %d.\n", cstate,
1609 ht.num_recs);
1610 }
1611 reclen = hash_rec_len(&ht, cstate);
1612 cs_ptr = hash_rec(&ht, cstate);
1613 cs_ptre = hash_rec(&ht, cstate) + reclen - 1;
1614 /* for (i=0;i<reclen;i++) printf(" %d",cs_ptr[i]); printf("\n"); */
1615 if (reclen % 2 == 1) {
1616 if (*cs_ptre == 1) {
1617 leftpad = TRUE;
1618 rightpad = FALSE;
1619 }
1620 else {
1621 leftpad = FALSE;
1622 rightpad = TRUE;
1623 }
1624 cs_ptre--;
1625 }
1626 else {
1627 leftpad = FALSE;
1628 rightpad = FALSE;
1629 }
1630
1631 if (dense_op)
1632 for (i = 0; i < ne; i++)
1633 fsarow[i] = 0;
1634 else
1635 len = 0;
1636
1637 e = 0; /* e is the edge number of generator pair (g1,g3) */
1638 for (g1 = 1; g1 <= ngens1; g1++)
1639 for (g3 = 1; g3 <= ngens1; g3++) {
1640 /* Calculate action of pair (g1,g3) on state cstate - to get the image,
1641 * we have to apply ( (g1,g2), (g2,g3) ) to each ordered pair in the
1642 * subset corresponding to cstate, and this for each generator g2 of the
1643 * base-alphabet (including the padding symbol).
1644 */
1645 e++;
1646 if (g1 == ngens1 && g3 == ngens1)
1647 continue;
1648 if ((leftpad && g1 <= ngens) || (rightpad && g3 <= ngens))
1649 continue;
1650 ht_ptrb = ht.current_ptr;
1651 ht_ptre = ht_ptrb - 1;
1652 es1 = (g1 - 1) * ngens1 + 1;
1653 ef1 = g1 * ngens1;
1654 /* As g2 ranges from 1 to ngens+1 in the pair (g1,g2), for fixed g1, the
1655 * corresponding edge number in the fsa ranges from es1 to ef1.
1656 *
1657 * As g2 ranges from 1 to ngens+1 in the pair (g2,g3), for fixed g3, the
1658 * corresponding edge number in the fsa ranges from g3 upwards, with
1659 * increments of size ngens+1.
1660 */
1661
1662 ptr = cs_ptr;
1663 while (ptr <= cs_ptre) {
1664 csa = *(ptr++);
1665 csb = *(ptr++);
1666 for (g2 = 1, e1 = es1, e2 = g3; e1 <= ef1; g2++, e1++, e2 += ngens1) {
1667 csima = g1 == ngens1 && g2 == ngens1
1668 ? (mult1ptr->is_accepting[csa] > 0 ? csa : 0)
1669 : target(dense_ip1, table1, e1, csa, dr1);
1670 if (csima == 0)
1671 continue;
1672
1673 csimb = g2 == ngens1 && g3 == ngens1
1674 ? (mult2ptr->is_accepting[csb] > 0 ? csb : 0)
1675 : target(dense_ip2, table2, e2, csb, dr2);
1676 if (csimb == 0)
1677 continue;
1678
1679 if (ht_ptrb > ht_ptre || csima > *(ht_ptre - 1) ||
1680 (csima == *(ht_ptre - 1) && csimb > *ht_ptre)) {
1681 /* We have a new state for the image subset to be added to the end
1682 */
1683 *(++ht_ptre) = csima;
1684 *(++ht_ptre) = csimb;
1685 }
1686 else {
1687 ht_chptr = ht_ptrb;
1688 while (*ht_chptr < csima)
1689 ht_chptr += 2;
1690 while (*ht_chptr == csima && *(ht_chptr + 1) < csimb)
1691 ht_chptr += 2;
1692 if (csima < *ht_chptr || csimb < *(ht_chptr + 1)) {
1693 /* we have a new state for the image subset to be added in the
1694 * middle */
1695 ht_ptr = ht_ptre;
1696 ht_ptre += 2;
1697 while (ht_ptr >= ht_chptr) {
1698 *(ht_ptr + 2) = *ht_ptr;
1699 ht_ptr--;
1700 }
1701 *ht_chptr = csima;
1702 *(ht_chptr + 1) = csimb;
1703 }
1704 }
1705 }
1706 }
1707 if (ht_ptre > ht_ptrb) {
1708 if (g1 == ngens1)
1709 *(++ht_ptre) = 1;
1710 else if (g3 == ngens1)
1711 *(++ht_ptre) = 2;
1712 }
1713 im = hash_locate(&ht, ht_ptre - ht_ptrb + 1);
1714 if (im > 0) {
1715 if (dense_op)
1716 fsarow[e - 1] = im;
1717 else {
1718 fsarow[++len] = e;
1719 fsarow[++len] = im;
1720 }
1721 nt++;
1722 }
1723 }
1724 if (!dense_op)
1725 fsarow[0] = len++;
1726 fwrite((void *)fsarow, sizeof(int), (size_t)len, tempfile);
1727 }
1728 fclose(tempfile);
1729
1730 ns = compositeptr->states->size = ht.num_recs;
1731 compositeptr->table->numTransitions = nt;
1732
1733 if (kbm_print_level >= 3)
1734 printf(" #Calculated transitions - %d states, %d transitions.\n", ns,
1735 nt);
1736
1737 /* Locate the accept states. This is slightly cumbersome, since a state
1738 * is an accept state if either the corresponding subset contains a
1739 * a pair (s1,s2), where s1 is and accept state of *mult1ptr and s2 an
1740 * accept state of *mult2ptr, or we can get from some such state to an
1741 * accept state by applying elements ( ($,x), (x,$ ).
1742 * We will need to use the array compositeptr->is_accepting.
1743 */
1744
1745 tmalloc(compositeptr->is_accepting, boolean, ns + 1);
1746 for (i = 1; i <= ns; i++)
1747 compositeptr->is_accepting[i] = FALSE;
1748 ct = 0;
1749 es1 = ngens * ngens1 + 1;
1750 ef1 = ngens1 * ngens1 - 1;
1751 for (cstate = ns; cstate >= 1; cstate--) {
1752 /* We work backwards through the states, since we wish to add on additional
1753 * elements at the end of the list in the hash-table - this destroys
1754 * later entries, but that doesn't matter, since we have already dealt
1755 * with them.
1756 */
1757 cs_ptr = hash_rec(&ht, cstate);
1758 reclen = hash_rec_len(&ht, cstate);
1759 if (reclen % 2 == 1)
1760 reclen--; /* The last entry marks the fact that this is a "padded state"*/
1761 cs_ptre = hash_rec(&ht, cstate) + reclen - 1;
1762 /* First see if the set itself contains an accept-state */
1763 ptr = cs_ptr;
1764 while (ptr <= cs_ptre) {
1765 csa = *(ptr++);
1766 csb = *(ptr++);
1767 if (mult1ptr->is_accepting[csa] && mult2ptr->is_accepting[csb]) {
1768 compositeptr->is_accepting[cstate] = TRUE;
1769 ct++;
1770 break;
1771 }
1772 }
1773 if (compositeptr->is_accepting[cstate])
1774 continue;
1775 /* Next apply generators ( ($,g2), (g2,$) ) and see if we get anything new.
1776 * We won't bother about having them in increasing order this time.
1777 */
1778 ptr = cs_ptr;
1779 while (ptr <= cs_ptre) {
1780 csa = *(ptr++);
1781 csb = *(ptr++);
1782 for (e1 = es1, e2 = ngens1; e1 <= ef1; e1++, e2 += ngens1) {
1783 csima = target(dense_ip1, table1, e1, csa, dr1);
1784 if (csima == 0)
1785 continue;
1786 csimb = target(dense_ip2, table2, e2, csb, dr2);
1787 if (csimb == 0)
1788 continue;
1789
1790 /* see if (csima,csimb) is accepting */
1791 if (mult1ptr->is_accepting[csima] && mult2ptr->is_accepting[csimb]) {
1792 compositeptr->is_accepting[cstate] = TRUE;
1793 ct++;
1794 break;
1795 }
1796 /* now see if it is new */
1797 ht_chptr = cs_ptr;
1798 got = FALSE;
1799 while (ht_chptr < cs_ptre) {
1800 if (csima == ht_chptr[0] && csimb == ht_chptr[1]) {
1801 got = TRUE;
1802 break;
1803 }
1804 ht_chptr += 2;
1805 }
1806 if (!got) {
1807 /* add (csima,csimb) to the end */
1808 *(++cs_ptre) = csima;
1809 *(++cs_ptre) = csimb;
1810 }
1811 }
1812 if (compositeptr->is_accepting[cstate])
1813 continue;
1814 }
1815 }
1816
1817 compositeptr->num_accepting = ct;
1818 if (ct == 1 || ct != ns) {
1819 tmalloc(compositeptr->accepting, int, ct + 1);
1820 ct = 0;
1821 for (i = 1; i <= ns; i++)
1822 if (compositeptr->is_accepting[i])
1823 compositeptr->accepting[++ct] = i;
1824 }
1825 tfree(compositeptr->is_accepting);
1826 tfree(mult1ptr->is_accepting);
1827 tfree(mult2ptr->is_accepting);
1828 hash_clear(&ht);
1829 tfree(fsarow);
1830 if (destroy) {
1831 fsa_clear(mult1ptr);
1832 fsa_clear(mult2ptr);
1833 }
1834
1835 if (readback) {
1836 tempfile = fopen(compfilename, "r");
1837 compressed_transitions_read(compositeptr, tempfile);
1838 fclose(tempfile);
1839 unlink(compfilename);
1840 }
1841
1842 return compositeptr;
1843 }
1844