by Scot Dyer (Lincoln, Nebraska), David Epstein (Warwick) and
Derek Holt (Warwick), Paul Sanders (Warwick).
Date: 11 August 1995.
PHILOSOPHY
We give the details of some file formats for finite state
automata, for group presentations, for rewriting systems, and for some
related objects. Why file formats?
The main reason is that if one writes one's programs so that they
always expect input and always give output in the agreed format, then
the programs can cooperate with each other. Moreover, definite rules
make it easy to write filters which convert one format into another.
Software for which such rules are not fixed ahead of time is likely to
be impossible to convert.
We have decided to use the syntax of the GAP package. This is a widely
used packagefor computational group theory developed at Aachen. Our hope
is that programs developed using our file formats will thereby become
part of GAP, an established system. This will make our programs
accessible to people who have not yet heard of GASP. Using the GAP format
make it easier to apply other parts of the GAP package before
and/or after applying our programs. Another advantage is that details of
design of language, including aspects such as flow of control, are left
to others, and we are freed to concentrate on aspects which are more
central to our interests.
Fixing the format eases the use of Unix pipes, and information
can also be exchanged using files.
We have tried to design the formats so that they are easily readable
by humans. In particular, our format is in readable ASCII characters.
Human readability makes it much easier to check on correctness of
input and output.
I/O usually takes a very small proportion of the time
of a computational group theory package. If fast I/O is required for
some purpose, this will presumably be in binary and subject to a very
different set of criteria from the ones we have adopted in this
document.
INTRODUCTION
This document is the development of some ideas which were discussed in the
preliminary GASP (Groups, Automata and Semigroups Project)
meeting in August 1994. This version was written at the WASGAS (Workshop on Algorithms and Software for
Groups, Automata and Semigroups) meeting in August 1995, and contains a number
of minor additions and amendments that have been introduced as a result of the
experiences of programmers using the format during the past year.
A formal description of the grammar has been written by Paul Sanders.
For those completely unfamiliar with GAP, we have included a brief
introduction to those parts of GAP syntax which are relevant to our
file format in Appendix A, at the end of the document. Careful study
of the examples below might also be sufficient. GAP is free and available
from a number of sites via anonymous ftp. Further information is
included in Appendix B.
A small penalty we have to pay for using GAP rather than our very own
format is that the GAP format may be a little more difficult for humans
to read than our own format would be. However this is a small price
to pay compared with the advantages. Some of us may develop our own
formats which are easier for humans to read, and filters to and from GAP.
However the main line will be the GAP format.
Those who have already developed their own formats for finite state
automata, are encouraged to write filters to and from GAP.
It must be stressed that a file format is not the same thing as a data
structure in a particular language. It is perfectly possible for a
program to read in a "dense" file format and then decide to use a sparse
data structure, or vice versa.
This file format is intended to be extensible. If our file format
is used by others, they are likely to be interested in different
applications, and different fields will be necessary. Programmers
using this file format should bear this possibility in mind,
particularly when writing parsers. The program you wrote yesterday
should not crash when the file format is extended tomorrow. Your
program's response to an unknown field should be to issue a warning,
and to continue to do its computation as well as it can.
Future changes to the file format should take into account the need for compatibility. As far as possible, data files which run under one
format should continue to run under future formats. We should not make
changes lightly.
Our philosophy is to keep our file format as simple as possible within
these constraints. Our design is intended to deal with current
applications and with applications we intend to develop in the near
future. The value of an agreed file format is precisely that the number of
possibilities is limited. Catering for all possible future extensions
is counter-productive, in that time is wasted on ideas which will never
be implemented; we also believe that looking forward too far will
result in an unnecessarily complicated format. The shape of a file
format needs to be guided by experience.
We start with two important generalities.
As in GAP, if the symbol '#' occurs, not within a quoted string, then that
symbol and and all symbols up to and including the next newline should
be ignored by input routines.
(This is the method used for inserting comments within files.)
If the backslash symbol '\' occurs followed immediately by a newline, then
both are ignored.
(This is the method used to break lines containing very long constructs.)
FORMAT FOR A FINITE STATE AUTOMATON (FSA)
Each of the following fields is required in each GAP record representing
an FSA. Each field name is followed by a type and a body of motivation and
description of its function. Examples are given later in the document
under the heading FSA EXAMPLES.
The fields must occur in the order listed below, except that the 'alphabet' and 'states' field can occur in either order, as can the 'initial' and 'accepting' fields.
To try and ensure that existing code doesn't break when the grammar is
extended, we allow fields of the form
GAP identifier := GAP expression
to occur anywhere in the record ( with a couple of exceptions ) provided
that the result is still a legal GAP record and the identifier is not
already used by us as a field identifier.
Programs should be capable of reading over such fields and ignoring them,
possibly printing a warning message.
The naming convention used here is to use mixed case -- the first
mnemonic component in the name of a field name is in lower case, and each
of the subsequent mnemonic components begins with a capital letter.
isFSA : boolean
The isFSA slot is used merely to identify this record as a GAP/GASP FSA.
It must be set to true and must be the first field of the record.
alphabet: record
states: record
These fields are in the finite set record format, which describes a
fixed correspondence between a finite set (sometimes with additional
structure) and the set of natural numbers from 1 up to the cardinality
of that set.
See: FINITE SET RECORDS
The alphabet field gives the labels of the transitions between states
and the state field gives the states of the automaton.
flags : list of strings
A particular flag is said to be set if it occurs in the list. If it
does not occur it is said to be unset. The following strings will be
supported in the current version of this format:
(Other flags which occur in files should probably be ignored by
programs, with the printing of a warning message. This allows individual programmers to use their own local
flags without having to introduce them officially into the format.)
"DFA" If set, the automaton is known to be deterministic.
"NFA" If set, the automaton is known to be nondeterministic.
"MIDFA" If set, the automaton is known to have a deterministic transition
table but (possibly) more than one initial state.
"minimized" If set, the automaton is known to be minimized and
deterministic.
"accessible" If set, the automaton is known to be have the property that
every state is reachable from an initial state.
"trim" If set, the automaton is known to be have the property that
every state is reachable from an initial state, and furthermore
there is a path to a success state from every state.
"sparse" If set, this flag indicates that it might be wise for the
programmer to use a data structure relevant to a sparse automaton
(few transitions from most states).
"dense" If set, this flag indicates that it might be wise for the
programmer to use a data structure relevant to a dense automaton
(when the average number of transitions from a state exceeds
some ratio of the alphabet's size).
"BFS" If set, the automaton is known to be deterministic, and
the states occur in BFS (= breadth-first-search) order.
The alphabet is ordered as in the alphabet field. The initial state
is numbered 1, and other states are numbered consecutively, using a
breadth-first search controlled by the ordering of the alphabet.
In general, programs which read files in this format should not
be expected to check any of the properties of the automaton implied
by these flags, but will accept them as correct. So, if they were
incorrect, then programs would be liable to produce incorrect
results.
initial: list of positive integers
accepting: list of positive integers
These lists represent respectively the initial states of the
automaton and the accepting states of this automaton, encoded
according to the correspondences given by the states field
between actual states and natural numbers.
Note that the GAP expression [1..n], which is an abbreviation for
the list of integers i satisfying 1 <= i <= n in their natural order,
may be used here.
(Note that it is meaningless, though grammatically correct, for
the list of accept states to include an integer not
corresponding to any state. Programs are entitled to assume
that their input is not only grammatical, but also meaningful.
Correspondingly greater care should be taken that output from
programs is always meaningful. Programs which receive
meaningless input are entitled to give meaningless output---it
may take too long to check for meaningfulness. Programs
designed to accept human input should check for more than
grammatical correctness.)
table: record
This field contains the transition table for the finite state
automaton. It is a GAP record. The table record must have a 'format' field, containing a string specifying the format of the
transition table itself. The current possibilities forthis string
are "sparse", "dense deterministic", and "dense nondeterministic".
The transitions themselves are specified in the field named "transitions".
The 'format' field must be the first field of the table record - other
fields not in the list of required fields may occur anywhere else.
In the case of a sparse format, an optional field named 'defaultTarget'
may be specified ( provided that it occurs after the format field and
before the 'transitions' field ). This is explained below. If present, it should be after the 'format' field and before the 'transitions' field.
Let n be the number of states and let m be the
size of the alphabet. In all cases, the transition field is a list
with n entries, the i-th entry representing all transitions from
state with the number i. However, the interpretation of the contents
of this i-th entry varies according to the format of the transition
table, and is given in the following.
"sparse"
the i-th entry is a list of entries of the form [x,j],
where x represents the label of a transition with source i, and j
represents the target of the transition. If x is a positive
integer, it should satisfy 1 <= x <= m, and it represents
the corresponding element of the alphabet which is the label
of the transition. If x is blank or 0 or the GAP string "epsilon"
then the transition is an epsilon transition in a
nondeterministic automaton.
Note that a "sparse" table may describe a DFA or an NFA,
depending on whether there is at most one transition
labeled by a given x, 1 <= x <= m. (In addition, to be
deterministic, there must be a unique initial state, and no
epsilon-transitions.)
If the optional 'defaultTarget' field is defined, then
its value should be an integer t satisfying 1 <= t <= n,
corresponding to some element of the state set. The meaning
is that for any letter number x of the alphabet and any
state number i, if no transition is specified in the table with
source i and label x, then there is such an transition with
target t.
"dense deterministic"
The i-th entry is a list of m entries.
The x-th entry j within the i-th entry represents a transition from
state i in which the label is the letter with number x.
The entry j must either be blank, or an integer. If j is a positive integer, then it must correspond to
the target state of this transition. If j is blank or a non-positive
integer, then there is no transition with source i and label x.
"dense nondeterministic"
The i-th entry is a list of at most m+1 entries.
The x-th entry j within the i-th entry represents the set of all
transitions from state i in which the label is the letter
with number x. The entry j must either be blank, or a list of
integers. If j is a list of integers, then j represents the set of
all targets with label number x and source i. If j is blank, then there are no such transitions.
The (m+1)-th entry, if present, represents the targets of
all epsilon transitions from state i.
Some of these rules allow the same transition to be listed twice.
Programs are entitled to treat this as meaningless.
FINITE SET RECORDS
The purpose of a finite set record is to provide a one-to-one
correspondence between an initial segment of the natural numbers and
a finite set which will often have additional structure. All finite
set records contain at least the following two fields, which must come in this order before other required fields.
Other fields, not in the list of required fields may occur in any position
after the 'type' field.
Programs should be capable of reading over such fields and ignoring them,
possibly printing a warning message.
type: GAP string
size: non-negative integer
The 'type' is a string saying what kind of algebraic structure
the set has.
The 'size' is the number of elements in the set.
The 'type' string should carry an implicit algorithm which has as
input a positive integer corresponding to an element of the set and
as output a humanly readable string corresponding to that element. This algorithm should be recorded in the documentation for the
particular finite set record format and not in the record itself.
Finite Set Record Format Types
"simple"
The "simple" type meets the minimal requirements of a finite
set record. That is, it has only the fields named 'size' and 'type'. The algorithm used to convert to strings for humans to
read is to use the canonical translation from natural numbers
to strings over the decimal digits.
"identifiers" "strings"
In these two cases, each element of the set has a name,
and no two elements have the same name. Two further fields
besides 'size' and 'type' are required: 'format' and 'names'.
The former must precede the latter.
The 'names' field gives the list of names, in a format
defined by the 'format' field (see below).
In the "identifiers" type, each name must be either a GAP
identifier (alphanumeric string starting with a letter or underscore),
or a GAP identifier followed by a '.' and a positive
integer <n> (for example gp.3).
(In GAP syntax, the second form is actually a reference to a
field of a record, but it is used principally to denote the
n-th generator of the algebraic structure named by the
GAP identifier.)
In the "strings" type, each name must be a GAP string,
which is essentially any string of characters enclosed in
double-quotes.
Identifiers, words and strings all print as their GAP
input representation.
The 'format' field must be set to one of the two strings "dense"
and "sparse". In the dense format, the 'names' field is simply a list
of length equal to the size of the set, of which the x-th entry is the
name of the element of the set with the number x.
In the sparse format, the 'names' field is a list of entries of the
form [x,z], meaning that the name of the element of the set with the
number x is z. (Since all elements of the set have a unique name, this list will again have length equal to the size of the set.)
Note that in the previous two paragraphs, the words 'dense'
and 'sparse'do not convey the true intentions of designers of this file format. The motivation for having these two
possibilities is that the first is more compact and easy to
understand for a small alphabet, whereas when the alphabet is
huge, the second will help the
human to get right the correspondence between the ordinal number x
of the letter in the alphabet and the name z. The motivation for the choice of word 'dense' and 'sparse' is to make
the usage consistent with other parts of this document, and
therefore easier to remember.
"words" "list of words"
In these two types, three further fields are required 'alphabet', 'format' and 'names', and must occur in that order.
The 'alphabet' field contains a list of GAP identifiers. This specifies the identifiers that may appear in the words
that occur in the 'names' field.
The 'format' field has the same meaning as it does in the "identifier"
and "strings" types.
In the "words" type, each name must be a GAP word.
A GAP word is either equal to 'IdWord' (representing the empty word)
or to an expression of the form <q_1>*<q_2>* ... <q_r> for some
r >= 1, where each <q_i> is either an identifier, or an expression of
the form <ident>^<integer>, where <ident> is a GAP identifier.
In the "list of words" type, each name is a GAP list of GAP words.
All identifiers used in the words must be in the 'alphabet' list.
Identifiers print as their GAP input representation.
"labeled" or "labelled" (user's choice)
Here we have a finite set labeled by another finite set. This is the most flexible of the finite set record types, and
is included to provide for applications which we have not yet
foreseen.
Three fields beyond 'size' and 'type' are required: 'labels', 'format' and 'setToLabels'.
These fields must occur in that order.
The 'labels' field contains a finite set record representing
the set of labels.
The 'format' field contains a GAP string, either "dense" or "sparse", and describes the format of the 'setToLabels' field.
The 'setToLabels' field describes the labeling in terms of a
(partial) function. Let m be the cardinality of the finite set
itself (i.e. the value of its 'size' field), and p be the
cardinality of the 'labels' set in the following:
In the "dense" format, the 'setToLabels' field takes the form
of a (partial) list with m entries, each entry z satisfying
0 <= z <= p. The i-th entry in the list specifies the number of
the label assigned to the i-th element of the finite set. It
may be blank or 0, indicating no label.
In the "sparse" format, the 'setToLabels' field takes the form of a
list of two-element lists [i,z], with 1 <= i <= m and 1 <= z <= p.
Each entry signifies that element number z of the 'labels' set labels
element number i of the finite set. It is meaningless to label
the same element of the base alphabet two different ways.
Elements of a labeled set print as X-Y where X is the number
of the element of the set being printed, and Y is
the printed representation of the label, or the empty string if that element of the set is unlabeled.
"product"
In thiscase, the set is in one-one correspondence with the
n-tuples of a base set together with a padding symbol.
(The point of the padding symbol is to allow n words of
possibly different lengths in the alphabet of the base set
to be put together to form a word in the alphabet of the product set.
The padding symbol is added to the end of some of these words until
they all have the same lengths.)
Three fields beyond 'size' and 'type' are required: 'arity', 'padding' and 'base'. 'arity' and 'padding' can occur in either order, but they must
precede 'base'.
The positive integer n must be specified in the 'arity' field of the
record.
The padding symbol must be specified in the 'padding' field of
the record, and it should be an identifier or string - in the case of identifier, a single underscore `_' is recommended.
The base set must be specified in the 'base' field of the record,
and it should itself be a finite set record. The base set
should not include the padding symbol. The base set has its
natural order, and the padding symbol is normally ordered after
the elements of the base set.
The algorithm to convert from the natural number representing the
state to its printing form is to number the n-tuples
lexicographically, and then use their list representations.
#Note that the language of fsa_1 is identical to the language of fsa_2
#(i.e. all strings starting with the second symbol), and
#fsa_2 is a minimized form of fsa_1.
#The following two examples are nondeterministic automata accepting the
#same language. They are identical, but different formats are used for
#their transition tables.
fsa_5 := rec (
# This is the word-acceptor for the free group on two generators a,b
# A and B are the inverses of a and b respectively.
# The accepted language consists of all strings that do not have
# aA, Aa, bB or Bb as a substring.
isFSA := true,
alphabet := rec (
type := "identifiers",
size := 4,
format := "dense",
names := [a,A,b,B]
),
states := rec (
# This is a contrived example to illustrate the labeled type.
type := "labeled",
size := 5,
labels := rec(type:="strings", size:=2, format:="dense",
names:=["early state","late state"]
),
format := "dense",
setToLabels := [1,1,,2,2]
),
flags := ["DFA","minimized","BFS"],
initial := [1],
accepting := [1..5],
table := rec(
format := "dense deterministic",
transitions := [
[2,3,4,5],
[2,0,4,5],
[0,3,4,5],
[2,3,4,0],
[2,3,0,5]
]
)
);
fsa_6 := rec (
# This is the word-difference machine arising in the automatic structure
# of the free group on two generators.
# It is included here to illustrate the product set record type.
isFSA := true,
alphabet := rec (
type := "product",
size := 24,
arity := 2,
padding := _,
base := rec (
type := "identifiers",
size := 4,
format := "dense",
names := [a,A,b,B]
)
),
states := rec (
type := "words",
size := 5,
alphabet := [a,A,b,B]
format := "sparse",
names := [[ 1, IdWord],
[ 2, a],
[ 3, A],
[ 4, b],
[ 5, B]
]
),
flags := ["DFA"],
initial := [1],
accepting := [1],
table := rec(
format := "sparse",
transitions := [
[[ 5, 3 ],[ 10, 2 ],[ 15, 5 ],[ 20, 4 ]],
[[ 5, 1 ]],
[[ 10, 1 ]],
[[ 15, 1 ]],
[[ 20, 1 ]]
]
)
);
FORMAT FOR A REWRITING SYSTEM (RWS)
Some or all of the following fields are required in each GAP record
representing an RWS. Each field name is followed by a type and a body of
motivation and description of its function.
Examples are given later in the document under the heading RWS EXAMPLES.
The fields that are present must occur in the order listed below except that
the ordering and generatorOrder fields can come in either order.
Other fields not required by the format may occur in any position after the "isRWS" field ( which must be the first field of the record ).
Programs should be capable of reading over such fields and ignoring them,
possibly printing a warning message.
In particular, there are many possible fields that might be used to
control the running of a Knuth-Bendix program, such as limits on the
total number of rewriting rules, on the maximal lengths of stored rules,
or on the maximal lengths of overlaps to be processed. We shall not
attempt to list all such possibilities in detail.
isRWS : boolean (compulsory)
The isRWS slot is used merely to identify this record as a GAP/GASP
RWS. It must be set to true.
isConfluent: boolean (optional) This can be used if the system of rewriting rules is known to be
confluent, or known not to be confluent.
ordering: string (compulsory) This defines the ordering used on words in the generators, when
forming the rewriting rules. Some possibilities are "shortlex", "wtshortlex", "recursive", "wreathprod".
Others may be added freely by programmers.
generatorOrder: list of identifiers (compulsory) This is a list of GAP identifiers, which are the generators of
the underlying group or monoid of the rewriting system.
The field is called 'generatorOrder' to emphasise the fact that
the order in which they occur in this list is significant in
defining the ordering of words in the generators.
Some of the orderings may require a further field to complete
the definition of the orderings on strings, and this should
come here. For example, the "wtshortlex" ordering requires a field 'weight',
which is a list of integers, specifying the weights of the
generators. The "wreathprod" ordering requires a 'level' field,
which specifies the levels of the generators.
inverses: list of identifiers (compulsory) This should be a GAP list, of length at most that of
the list 'generatorOrder', specifying the two-sided inverses, if
any, of the generators. If a generator has no such inverse (or
is not known to), then that entry should be blank. The non-blank
entries must (currently) themselves be generators (although
words in the generators would also make sense mathematically),
and if the inverse of generator 'x' is 'y', then the inverse of 'y' must be specified as 'x'. If it is required that a program reading the file should recognise
the monoid being defined to be a group, then all generators should
have inverses specified.
Currently, there is no facility for specifying right- or left-
inverses, although that might be introduced in the future.
equations: list of lists (compulsory) This field contains the relations or equations which define the
group or monoid. Each entry in the list corresponds to one such
relation, and should itself be a list of length two, containing the
two GAP words 'w1' and 'w2' in the generators for which 'w1 = w2'
is the relation. Remember that 'IdWord' is the GAP name for the
empty word.
The relations in the group that are implicitly defined by the 'inverses' field do not need to be inserted here, although it
is not an error to do so.
2.
#monoid presentation of F(2,7) - should produce a monoid of length 30
#which is the same as the group, together with the empty word.
rws_2 := rec(
isRWS := true,
ordering := "recursive",
maxstoredlen := [15,15], #a control parameter
generatorOrder := [a,b,c,d,e,f,g],
inverses := [], #no inverses
equations := [[a*b,c], [b*c,d], [c*d,e], [d*e,f], [e*f,g], [f*g,a], [g*a,b]
]
);
3.
# Note that the generator _H, which stand for a subgroup, has no inverse in
# this example.
rws_3 := rec(
isRWS := true,
ordering := "wreathprod",
tidyint := 10, # a control parameter not explicitly defined in the format
generatorOrder := [a,b,A,B,_H,x,X],
level := [2,2,2,2,1,1,1],
inverses := [A,B,a,b,,X,x],
equations := [
[_H*a*b,x*_H], [b*a,a*b]
]
);
¤ Dauer der Verarbeitung: 0.27 Sekunden
(vorverarbeitet)
¤
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.
