Quelle gpsubpres.c Sprache: C

/* gpsubpres.c   16/1/96.
* 13/10/98 large scale reorganisation to omit globals, etc.
* 16/3/96 - changed command-line syntax to
* gpmimult [options] groupname [subfilename]
* where subfilename defaults to "sub".
* Find relations of a subgroup of a coset automatic group, using the
* Schreier generators that are the initial states of the generalised
* multiplier automaton.
* It is based on gpaxioms. We form the coset mi-multipliers for the group
* relators, and then their initial states are the relators of the subgroup.
*
* This program assumes that makecosfile, kbprogcos, gpmakefsa -cos,
* gpaxios -cos, have already been run on groupname.
*
* Input is from groupname (for group relators) and groupname.cosfile.gm
* where cosfile is derived from subfilename as in makecosfile.
* Output is to groupname.subfilename.pres, in GAP format.
*
* SYNOPSIS:
* gpsubpres [-ip d/s[dr]] [-op d/s] [-silent] [-v] [-l] [-s] [-pref prefix]
*           groupname [subfilename]
*
* OPTIONS:
* -ip d/s[dr]  input in dense or sparse format - dense is default
* -op d/s      output in dense or sparse format - sparse is default
* -v           verbose
* -silent      no diagnostics
* -l/-h        large/huge hash-tables (for big examples)
* -s Throw away files immediately after use whenever possible, to
*              save disk-space. This will slow things down considerably.
* -pref prefix Use the string 'prefix' as prefix for subgroup generators
*              Their names are 'prefix'1. 'prefix'2, etc.
*              Default is "_x".
*              It will also be used as the name of the group in the GAP file.
*/

#include <stdio.h>

#include "defs.h"
#include "fsa.h"
#include "rws.h"
#include "definitions.h"

#define MAXEQNS 1024
#define MAXREDUCELEN 4096

static rewriting_system rws, *rwsptr;

static char gpname[100], subname[100], cosgpname[100], inf[100], outf[100],
    outfp[100], fsaname[100], prefix[16], tablefilename[100];
static fsa migm, migm2, *migm2ptr;
static int ngens, neqns, *inv, numstoredmult, nsubgens;
static reduction_equation *eqn;
static char **storedmult;
static storage_type ip_store = DENSE;
static int dr = 0;
static storage_type op_store = SPARSE;
static boolean readback = TRUE;
static boolean keepfiles = TRUE;
static boolean first_relator;
static FILE *rfile, *wfile, *wfilep;

/* Functions defined in this file */
static int find_subrels(gen *r);
static int long_word_multiplier(gen *w, char *s);
static void badusage(void);

int main(int argc, char *argv[])
{
  int arg, i, j, ct;
  gen *relator, *ptr, *ptr2;
  boolean seengpname, seensubname;

  setbuf(stdout, (char *)0);
  setbuf(stderr, (char *)0);

  rwsptr = &rws;
  rwsptr->maxeqns = MAXEQNS;
  rwsptr->maxreducelen = MAXREDUCELEN;
  rwsptr->maxreducelenset = FALSE;
  rwsptr->cosets = FALSE;
  /* even in the cosets case we read relations from original group file */
  rwsptr->inv_of = 0;
  rwsptr->weight = 0;
  rwsptr->level = 0;
  rwsptr->history = 0;
  rwsptr->slowhistory = 0;
  rwsptr->slowhistorysp = 0;
  rwsptr->preflen = 0;
  rwsptr->prefno = 0;

  strcpy(prefix, "_x");
  arg = 1;
  seengpname = seensubname = FALSE;
  while (argc > arg) {
    if (strcmp(argv[arg], "-ip") == 0) {
      arg++;
      if (arg >= argc)
        badusage();
      if (strcmp(argv[arg], "d") == 0)
        ip_store = DENSE;
      else if (argv[arg][0] == 's') {
        ip_store = SPARSE;
        if (stringlen(argv[arg]) > 1)
          dr = atoi(argv[arg] + 1);
      }
      else
        badusage();
    }
    else if (strcmp(argv[arg], "-op") == 0) {
      arg++;
      if (arg >= argc)
        badusage();
      if (strcmp(argv[arg], "d") == 0)
        op_store = DENSE;
      else if (strcmp(argv[arg], "s") == 0)
        op_store = SPARSE;
      else
        badusage();
    }
    else if (strcmp(argv[arg], "-silent") == 0)
      kbm_print_level = 0;
    else if (strcmp(argv[arg], "-v") == 0)
      kbm_print_level = 2;
    else if (strcmp(argv[arg], "-vv") == 0)
      kbm_print_level = 3;
    else if (strcmp(argv[arg], "-l") == 0)
      kbm_large = TRUE;
    else if (strcmp(argv[arg], "-h") == 0)
      kbm_huge = TRUE;
    else if (strcmp(argv[arg], "-s") == 0)
      keepfiles = FALSE;
    else if (strcmp(argv[arg], "-pref") == 0) {
      arg++;
      if (arg >= argc)
        badusage();
      strcpy(prefix, argv[arg]);
    }
    else if (argv[arg][0] == '-')
      badusage();
    else if (!seengpname) {
      seengpname = TRUE;
      strcpy(gpname, argv[arg]);
    }
    else if (!seensubname) {
      seensubname = TRUE;
      strcpy(subname, argv[arg]);
    }
    else
      badusage();
    arg++;
  }
  if (!seengpname)
    badusage();
  if (!seensubname)
    strcpy(subname, "sub");
  if (strncmp(subname, "sub", 3) == 0) {
    strcpy(cosgpname, gpname);
    strcat(cosgpname, ".cos");
    strcat(cosgpname, subname + 3);
  }
  else {
    strcpy(cosgpname, gpname);
    strcat(cosgpname, ".");
    strcat(cosgpname, subname);
    strcat(cosgpname, "_cos");
  }

  strcpy(tablefilename, cosgpname);
  strcat(tablefilename, "temp_axXXX");

  /* First read in the defining relations for the group. */
  strcpy(inf, gpname);
  if ((rfile = fopen(inf, "r")) == 0) {
    fprintf(stderr, "Cannot open file %s.\n", inf);
    exit(1);
  }
  read_kbinput_simple(rfile, FALSE, rwsptr);
  fclose(rfile);
  ngens = rws.num_gens;
  neqns = rws.num_eqns;
  inv = rws.inv_of;
  eqn = rws.eqns;

  /* Now read in the general multiplier, and see how many subgroup generators
   * there are (which is just the number of initial states - 1).
   */
  strcpy(inf, cosgpname);
  strcat(inf, ".migm");
  if ((rfile = fopen(inf, "r")) == 0) {
    fprintf(stderr, "Cannot open file %s.\n", inf);
    exit(1);
  }
  fsa_read(rfile, &migm, ip_store, dr, 0, TRUE, fsaname);
  fclose(rfile);

  nsubgens = migm.num_initial - 1;
  /* The first initial state always corresponds to the identity.
   * Now we can open the output file and commence the output in GAP format.
   */
  sprintf(outfp, "%s.%s.pres", gpname, subname);
  wfilep = fopen(outfp, "w");
  fprintf(wfilep, "%sg := FreeGroup(%d);\n", prefix, nsubgens);
  for (i = 1; i <= nsubgens; i++)
    fprintf(wfilep, "%s%d := %sg.%d;\n", prefix, i, prefix, i);
  fprintf(wfilep, "%s_relators:=[\n", prefix);

  /* Now calculate the general multiplier for words of length 2 */
  if (kbm_print_level > 1)
    printf(" #Calculating general word-length 2 multiplier.\n");
  migm2ptr = fsa_migm2(&migm, op_store, TRUE, tablefilename, readback, prefix);
  if (migm2ptr == 0)
    exit(1);
  if (kbm_print_level > 1)
    printf(" #Number of states of migm2 = %d.\n", migm2ptr->states->size);

  if (readback) { /* always true */
    if (midfa_labeled_minimize(migm2ptr) == -1)
      exit(1);
  }
  /*
    else
      fsa_ip_labeled_minimize(migm2ptr);
  */
  if (kbm_print_level > 1)
    printf(" #Number of states of migm2 after minimization = %d.\n",
           migm2ptr->states->size);
  strcpy(fsaname, rws.name);
  strcat(fsaname, ".migm2");
  strcpy(outf, cosgpname);
  strcat(outf, ".migm2");
  wfile = fopen(outf, "w");
  fsa_print(wfile, migm2ptr, fsaname);
  if (kbm_print_level > 0)
    printf("#General length-2 multiplier with %d states computed.\n",
           migm2ptr->states->size);
  fclose(wfile);
  fsa_clear(migm2ptr);
  tfree(migm2ptr);

  /* If keepfiles is false, then we will throw away every multiplier immediately
   * after it has been used. Otherwise, we will keep them, in case they are
   * needed again.
   * We store a list of words for which we have got the multipliers in
   * storedmult. We first form a rough upper bound on how long this list
   * could get - ngens + total relator length - 1.
   */
  strcpy(fsaname, rws.name);
  strcat(fsaname, ".mimult"); /* this is unimportant, since file is temporary */
  if (keepfiles) {
    ct = ngens;
    for (i = 1; i <= neqns; i++)
      ct += (genstrlen(eqn[i].lhs) + genstrlen(eqn[i].rhs));
    tmalloc(storedmult, char *, ct);
    numstoredmult = 0;
  }

  /* Now we are ready to start building the multipliers for the group relators,
   * which will give rise to the subgroup relators.
   * We use rws.testword1 to store the relators of G as they arise.
   * We start with the inverse relators.
   */
  first_relator = TRUE;
  relator = rws.testword1;
  for (i = 1; i <= ngens; i++) {
    relator[0] = i;
    relator[1] = inv[i];
    relator[2] = '\0';
    if (kbm_print_level > 0) {
      kbm_buffer[0] = '\0';
      add_to_buffer(0, "#Processing relator: ");
      add_word_to_buffer(stdout, relator, rws.gen_name);
      printbuffer(stdout);
    }
    if (find_subrels(relator) == -1)
      exit(1);
  }

  /* Now the other relators.
   * We first need to get them from equation to relator form.
   */
  for (i = 1; i <= neqns; i++) {
    if (genstrlen(eqn[i].lhs) == 0 && genstrlen(eqn[i].rhs) == 0)
      continue;
    genstrcpy(relator, eqn[i].lhs);
    ptr = relator + genstrlen(relator);
    ptr2 = eqn[i].rhs;
    for (j = genstrlen(ptr2) - 1; j >= 0; j--)
      *(ptr++) = inv[ptr2[j]];
    *ptr = '\0';
    if (genstrlen(relator) == 2 && relator[1] == inv[relator[0]])
      continue; /* since we have already done this one */
    if (kbm_print_level > 0) {
      kbm_buffer[0] = '\0';
      add_to_buffer(0, "#Processing relator: ");
      add_word_to_buffer(stdout, relator, rws.gen_name);
      printbuffer(stdout);
    }
    if (find_subrels(relator) == -1)
      exit(1);
  }

  fprintf(wfilep, "\n];\n");
  fclose(wfilep);

  if (keepfiles) {
    for (i = 1; i <= numstoredmult; i++) {
      sprintf(outf, "%s.mim%s", cosgpname, storedmult[i]);
      unlink(outf);
      tfree(storedmult[i]);
    }
    tfree(storedmult);
  }
  strcpy(outf, cosgpname);
  strcat(outf, ".migm2");
  unlink(outf);
  rws_clear(&rws);
  exit(0);
}

/* For a word w in the generators, this function returns a corresponding
* string with the terms of w replaced by integers separated by '_'.
* This is used as a suffix in the filenames used for storing the
* corresponding multiplier fsa's.
*/
static char *file_suffix(gen *w)
{
  char *s;
  gen *p;
  boolean first;
  int len;
  /* First work out the length of the required string. */
  len = genstrlen(w);
  p = w - 1;
  while (*(++p) != 0)
    len += int_len((int)(*p));
  tmalloc(s, char, len);
  s[0] = '\0';
  first = TRUE;
  p = w - 1;
  while (*(++p) != 0) {
    if (first)
      first = FALSE;
    else
      sprintf(s + stringlen(s), "_");
    sprintf(s + stringlen(s), "%d", *p);
  }
  return s;
}

/* Find and output the subgroup relators arising from the group relator */
int find_subrels(gen *r)
{
  char *suff;
  gen ***labnames, *rel, *relend;
  char **alph;
  boolean got, *laboccurs;
  fsa mult;
  int i, j, nlabs;

  suff = file_suffix(r);
  /* First see if we have formed the multiplier for  r  already - if
   * not, build and store it using long_word_multiplier().
   */
  got = FALSE;
  if (keepfiles) {
    for (i = 1; i <= numstoredmult; i++) {
      if (strcmp(suff, storedmult[i]) == 0) {
        got = TRUE;
        break;
      }
    }
  }
  if (!got) {
    if (long_word_multiplier(r, suff) == -1)
      return -1;
  }
  /* Now we read the composite multiplier in */
  sprintf(inf, "%s.mim%s", cosgpname, suff);
  if ((rfile = fopen(inf, "r")) == 0) {
    fprintf(stderr, "Cannot open file %s.\n", inf);
    exit(1);
  }
  fsa_read(rfile, &mult, ip_store, dr, 0, TRUE, fsaname);
  fclose(rfile);
  /* Now we write the words for its initial states into the GAP file.
   * They occur among the names of the labels of the state-set.
   */
  nlabs = mult.states->labels->size;
  tmalloc(laboccurs, boolean, nlabs + 1);
  for (i = 1; i <= nlabs; i++)
    laboccurs[i] = FALSE;
  for (i = 1; i <= mult.states->size; i++)
    laboccurs[mult.states->setToLabels[i]] = TRUE;
  labnames = mult.states->labels->wordslist;
  alph = mult.states->labels->alphabet;
  for (i = 1; i <= nlabs; i++)
    if (laboccurs[i]) {
      j = 0;
      while (labnames[i][j]) {
        rel = labnames[i][j];
        if (*rel != '\0') {
          /* We have a subgroup relator */
          if (first_relator) {
            first_relator = FALSE;
            fprintf(wfilep, " ");
          }
          else
            fprintf(wfilep, ",\n ");
          relend = rel + genstrlen(rel) - 1;
          while (rel <= relend) {
            fprintf(wfilep, "%s", alph[*rel]);
            if (rel != relend)
              fprintf(wfilep, "*");
            rel++;
          }
        }
        j++;
      }
    }
  fsa_clear(&mult);
  unlink(inf);
  tfree(suff);
  tfree(laboccurs);
  return 0;
}

/* Calculate the multiplier associated with the word w.
* s is the suffix of the file in which it will be stored.
* (s has been derived from w by a call of file_suffix.)
*/
int long_word_multiplier(gen *w, char *s)
{
  int i, l;
  gen *wl, *wlt, *wr, *wrt;
  char *suffl, *sufflt, *suffr, *suffrt;
  boolean gotl, gotr, gotlt, gotrt;
  fsa mult1, mult2, *compmult;
  if (kbm_print_level >= 3) {
    kbm_buffer[0] = '\0';
    add_to_buffer(0, " #Calculating multiplier for word: ");
    add_word_to_buffer(stdout, w, rws.gen_name);
    printbuffer(stdout);
  }
  l = genstrlen(w);

  if (l == 1) { /* Length 1 - use fsa_mimakemult */
    strcpy(inf, cosgpname);
    strcat(inf, ".migm");
    if ((rfile = fopen(inf, "r")) == 0) {
      fprintf(stderr, "Cannot open file %s.\n", inf);
      exit(1);
    }
    fsa_read(rfile, &migm, op_store, 0, 0, TRUE, fsaname);
    fclose(rfile);
    if (fsa_mimakemult(&migm, w[0], prefix) == -1)
      return -1;
    if (mimult_minimize(&migm) == -1)
      return -1;
    sprintf(outf, "%s.mim%s", cosgpname, s);
    wfile = fopen(outf, "w");
    fsa_print(wfile, &migm, fsaname);
    fclose(wfile);
    fsa_clear(&migm);
  }
  else if (l == 2) { /* Length 2 - use fsa_mimakemult2 */
    strcpy(inf, cosgpname);
    strcat(inf, ".migm2");
    if ((rfile = fopen(inf, "r")) == 0) {
      fprintf(stderr, "Cannot open file %s.\n", inf);
      exit(1);
    }
    fsa_read(rfile, &migm2, op_store, 0, 0, TRUE, fsaname);
    fclose(rfile);
    if (fsa_mimakemult2(&migm2, w[0], w[1], prefix) == -1)
      return -1;
    mimult_minimize(&migm2);
    sprintf(outf, "%s.mim%s", cosgpname, s);
    wfile = fopen(outf, "w");
    fsa_print(wfile, &migm2, fsaname);
    fclose(wfile);
    fsa_clear(&migm2);
  }
  else { /* general case - we have to split w up */
    if (l % 2 == 0) {
      tmalloc(wl, gen, l / 2 + 1);
      tmalloc(wr, gen, l / 2 + 1);
      for (i = 0; i < l / 2; i++)
        wl[i] = w[i];
      wl[l / 2] = '\0';
      genstrcpy(wr, w + l / 2);
      suffl = file_suffix(wl);
      suffr = file_suffix(wr);
    }
    else {
      tmalloc(wl, gen, l / 2 + 2);
      tmalloc(wr, gen, l / 2 + 1);
      for (i = 0; i <= l / 2; i++)
        wl[i] = w[i];
      wl[l / 2 + 1] = '\0';
      genstrcpy(wr, w + l / 2 + 1);
      suffl = file_suffix(wl);
      suffr = file_suffix(wr);
    }
    /* See whether we have either of them already */
    gotl = gotr = FALSE;
    if (keepfiles) {
      for (i = 1; i <= numstoredmult; i++) {
        if (strcmp(suffl, storedmult[i]) == 0)
          gotl = TRUE;
        if (strcmp(suffr, storedmult[i]) == 0)
          gotr = TRUE;
      }
    }

    if (keepfiles && l % 2 == 1 && (!gotl || !gotr)) {
      /* In this case, there are two possible ways to split w up -
       * we see if the other way has more multipliers already stored.
       */
      tmalloc(wlt, gen, l / 2 + 1);
      tmalloc(wrt, gen, l / 2 + 2);
      for (i = 0; i < l / 2; i++)
        wlt[i] = w[i];
      wlt[l / 2] = '\0';
      genstrcpy(wrt, w + l / 2);
      sufflt = file_suffix(wlt);
      suffrt = file_suffix(wrt);
      gotlt = gotrt = FALSE;
      for (i = 1; i <= numstoredmult; i++) {
        if (strcmp(sufflt, storedmult[i]) == 0)
          gotlt = TRUE;
        if (strcmp(suffrt, storedmult[i]) == 0)
          gotrt = TRUE;
      }
      if ((gotlt && gotrt) || ((gotlt || gotrt) && !gotl && !gotr)) {
        tfree(wl);
        tfree(wr);
        tfree(suffl);
        tfree(suffr);
        wl = wlt;
        wr = wrt;
        suffl = sufflt;
        suffr = suffrt;
        gotl = gotlt;
        gotr = gotrt;
      }
      else {
        tfree(wlt);
        tfree(wrt);
        tfree(sufflt);
        tfree(suffrt);
      }
    }
    if (!gotl) {
      if (long_word_multiplier(wl, suffl) == -1)
        return -1;
    }
    if (!gotr && genstrcmp(wl, wr) != 0) {
      if (long_word_multiplier(wr, suffr) == -1)
        return -1;
    }
    /* Read back in the two multipliers and form their composite */
    sprintf(inf, "%s.mim%s", cosgpname, suffl);
    if ((rfile = fopen(inf, "r")) == 0) {
      fprintf(stderr, "Cannot open file %s.\n", inf);
      exit(1);
    }
    fsa_read(rfile, &mult1, ip_store, dr, 0, TRUE, fsaname);
    fclose(rfile);
    sprintf(inf, "%s.mim%s", cosgpname, suffr);
    if ((rfile = fopen(inf, "r")) == 0) {
      fprintf(stderr, "Cannot open file %s.\n", inf);
      exit(1);
    }
    fsa_read(rfile, &mult2, ip_store, dr, 0, TRUE, fsaname);
    fclose(rfile);

    compmult = fsa_micomposite(&mult1, &mult2, op_store, TRUE, tablefilename,
                               readback);
    fsa_clear(&mult1);
    fsa_clear(&mult2);
    if (readback) /* always true */
      mimult_minimize(compmult);
    /*
        else
          fsa_ip_minimize(compmult);
    */
    sprintf(outf, "%s.mim%s", cosgpname, s);
    wfile = fopen(outf, "w");
    fsa_print(wfile, compmult, fsaname);
    fclose(wfile);
    fsa_clear(compmult);
    tfree(compmult);

    if (keepfiles) {
      if (gotl)
        tfree(suffl) else storedmult[++numstoredmult] = suffl;
      if (gotr)
        tfree(suffr) else storedmult[++numstoredmult] = suffr;
    }
    else {
      sprintf(inf, "%s.mim%s", cosgpname, suffl);
      unlink(inf);
      sprintf(inf, "%s.mim%s", cosgpname, suffr);
      unlink(inf);
      tfree(suffl);
      tfree(suffr);
    }
    tfree(wl);
    tfree(wr);
  }

  return 0;
}

void badusage(void)
{
  fprintf(
      stderr,
      "Usage: gpsubpres [-ip d/s[dr]] [-op d/s] [-silent] [-v] [-l] [-f]\n");
  fprintf(stderr, "\t\t groupname [subname].\n");
  exit(1);
}

quality89%

¤ Dauer der Verarbeitung: 0.2 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.