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