This package grew out of a desire to be able to work efficiently with elements of the asychronous rational group as described in the paper [GNS00].
Note that there are already two related packages in GAP. The first package is called "fr" by Laurent Bartholdi and the second package is AutomGrp by Yevgen Muntyan and Dmytro Savchuk. The package "fr" is meant to work with groups geneated by synchonous automata and more generally functionally recursive groups. The AutomGrp package works with automata as described in [GNS00] but where these automata are also constrained to be synchronous (one letter in, one letter out) and where one is considering the (semi)group generated by the states of the transducer.
The paper [GNS00] actually describes the group R of homeomorphisms of the binary Cantor space which are describable by finite initial asynchronous automata (the fact that the Cantor space is binary is not relevent). Groups generated by such homeomorphisms form a much broader class of groups; the group R contains many of the groups of homeomorphisms of Cantor space which are studied in the literature, such as the Thompson groups F, T, V, Grigorchuk's group, and hybrids such as Roever's group and other Nekrashevich type groups.
The paper [GNS00] gives several algorithms for performing calculations in these groups and this package implements all of that functionality although occasionally using different underlying algorithms. The names of various algorithms are natural from the text of the paper as one can see in this manual.
We will use the word "automaton" to represent a directed edge labelled graph where the edge labels come from a finite alphabet. We will use the word "transducer" to represent a machine which reads infinite strings according to the transitions of an automaton but when transitioning over an edge the machine will write a finite word (possibly empty). A transducer will represent a group element in R if when reading from the initial state it induces a bijection on Cantor space.
This package is built over the framework provided by the automata package in GAP (https://www.gap-system.org/Packages/automata.html).
In the following sections we will work with the following transducer and demonstrate various aspects of the algorithms in [GNS00].
gap> T := Transducer(2, 2, [[2, 3], [2, 3], [2, 3]], > [[[], []], [[0], [0]], [[1], [1]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 3 states.>
For the reader, the first two numbers represent input and output alphabet sizes. Then there is a list of transitions when reading letters 0 or 1 from the input alphabet (which has size 2 in this example). Finally there is a second list of output words from each state when reading the corresponding input letter. This notation seems obscure at first but it becomes easy to work with. We also have the capacity to represent this transducer is a more human-readable form through an autogenerated pdf image of the transducer. The following image is a representation of the transducer in the above example. This image can be generated with the command: "Splash(DotTransducer(T))". The example above represents an inefficient transducer representing the identity homeomorphism on the two letter alphabet Cantor space. In this document we will show how to check that the transducer represents a bijection on Cantor space, how to replace this transducer by a smaller transducer representing the same transformation, how to invert the transducer, how to take products of transducers, and in general, carry out the methods described in [GNS00].
Our transducer package allows users to write transducers which change alphabet sizes, and do generic transducer-type transformations to finite strings. Given a base initial transducer T with identital input and output alphabets, the package can verify that T represents an invertible homeomorphism h of Cantor space. If h is invertible the package supports inversion (by producing a transducer S representing the inverse of h). It also supports taking products and supports the minimisation and checking for incomplete response procedures as described in the GNS paper. More detailed technical processes are also supported as one can see by reading further into this manual.
generated by GAPDoc2HTML