2.1-12 \*
2.1-14 \*
2.1-15 \^
2.1-17 \=
2.1-20 \^
2.1-21 \^
In this section we descible methods for working with UDAF transducers and UDAF isomorphisms as described in the paper (https://arxiv.org/abs/2112.13359). Note that many of the functions here are only implemented for UDAF digraphs for the reasons discussed in the paper.
‣ UDAFIsomorphism( T ) | ( operation ) |
Returns: an isomorphism in the UDAF category
Creates an object called an UDAF isomorphism.
The input is an UDAF transducer, the stored isomorphism is the one obtained by composing the inverse of the induced domain map with the induced codomain map.
gap> L01 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 0, 1); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> L10 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 0); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L01, L10); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> UDAFIsomorphism(T); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.>
‣ UDAFIsomorphism( T ) | ( operation ) |
Returns: an isomorphism in the UDAF category
Creates an object called an UDAF isomorphism (seehttps://arxiv.org/abs/2112.13359).
The input is a core synchronizing aaa transducer object which induces an UDAF isomorphism. the stored isomorphism is this induced isomorphism.
gap> R := ResizeZeroStringTransducer(2, 2, 3); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 5 states.> gap> U := UDAFIsomorphism(R); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.>
‣ UDAFIsomorphism( W1, W2 ) | ( operation ) |
Returns: an isomorphism in the UDAF category
Same as UDAFIsomorphism(UDAFTransducer(W1, W2)).
gap> L01 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 0, 1); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> L10 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 0); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> UDAFIsomorphism(L01, L10); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.>
‣ UDAFIsomorphism( S ) | ( operation ) |
Returns: an isomorphism in the UDAF category
Creates an object called an UDAF isomorphism (seehttps://arxiv.org/abs/2112.13359).
The input is a shift isomorphism. Returns the corresponding UDAF isomorphism.
gap> T := Transducer(2, 2, [[1, 2], [1, 2]], [[[1], [1]], [[0], [0]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 2 states.> gap> ShiftIsomorphism(T); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> WalkHomomorphism(Digraph([[1, 1]]), Digraph([[1, 2], [1]]), [1], [[1], [2, 3]]); gap> UDAFIsomorphism(S); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.>
‣ UDAFTransducer( T ) | ( operation ) |
Returns: an UDAF transducer
The argument is to be a core synchronizing aaa transducer which induces an UDAF isomorphism.
The output is the corresponding UDAF transducer, where the alphabet of size n is replaces with the digraph with one vertex and n edges.
gap> T := ResizeZeroStringTransducer(3, 1, 2);; gap> U := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.>
‣ UDAFTransducer( W1, W2 ) | ( operation ) |
Returns: an UDAF transducer
The argument is to be a pair of UDAF foldings with the same domain digraph. The output is the corresponding UDAF transducer.
gap> L11 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 1); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> L20 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 2, 0); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L11, L20); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.>
‣ ComposeUDAFTransducers( T1, T2 ) | ( operation ) |
Returns: an UDAF transducer
The argument is to be a pair of UDAF transducers where the codomain digraph of T1 is the same as the domain digraph of T2.
The output is an UDAF transducer which induces the composite of the UDAF isomorphisms of the input transducers.
This operation can also be called with *.
gap> L11 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 1); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> L20 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 2, 0); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L11, L20); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> ComposeUDAFTransducers(T, T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 8 states.>
‣ MinimalUDAFTransducer( T ) | ( operation ) |
Returns: an UDAF transducer
An UDAF transducer is called minimal if its domain is a one-sided folding, its codomain is an UDAF folding without complete responce, and no two states have both the same domain image and the same codomain image.
The operation returns a minimal UDAF transducer which induces the same UDAF isomorphism as the given transducer.
gap> L10 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 0); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> L01 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 0, 1); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L01, L10); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> IsMinimalUDAFTransducer(T); false gap> M := MinimalUDAFTransducer(T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> IsMinimalUDAFTransducer(M); true gap> M = IdentityUDAFTransducer(Digraph([[1, 1]])); true
‣ IsMinimalUDAFTransducer( T ) | ( attribute ) |
Returns: true or false
An UDAF transducer is called minimal if its domain is a one-sided folding, its codomain is an UDAF folding without complete responce, and no two states have both the same domain image and the same codomain image.
The attribute returns true if and only if the given transducer is minimal.
gap> L10 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 0); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> L01 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 0, 1); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L01, L10); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> IsMinimalUDAFTransducer(T); false gap> M := MinimalUDAFTransducer(T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> IsMinimalUDAFTransducer(M); true gap> M = IdentityUDAFTransducer(Digraph([[1, 1]])); true
‣ AreIsomorphicLabeledUDAFTransducers( T1, T2, L1, L2 ) | ( operation ) |
Returns: true or false
Two UDAF transducers are called isomorphic if they have the same domain and codomain digraphs, and there is an isomorphism of their underlying digraphs which converts one into the other
Here T1, T2 are UDAF transducers and L1, L2 are lists with one entry for each state of T1 and T2 respectievly. These are intended to be thought of as labels for the states of the transdcuers.
The attribute returns true if and only if there is an isomorphism from T1 to T2 which preserves the given labels.
gap> T := ResizeZeroStringTransducer(3, 1, 2);; gap> U := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> T := ResizeZeroStringTransducer(3, 1, 2); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 4 states.> gap> U := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> I := U^-1; <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> AreIsomorphicUDAFTransducers(I, U); false gap> M := MinimalUDAFTransducer(I); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> AreIsomorphicUDAFTransducers(M, U); true
‣ AreIsomorphicUDAFTransducers( T1, T2 ) | ( operation ) |
Returns: true or false
Two UDAF transducers are called isomorphic if they have the same domain and codomain digraphs, and there is an isomorphism of their underlying digraphs which converts one into the other
The attribute returns true if and only if the given transducers are isomorphic.
gap> T := ResizeZeroStringTransducer(3, 1, 2);; gap> U := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> T := ResizeZeroStringTransducer(3, 1, 2); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 4 states.> gap> U := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> I := U^-1; <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> AreIsomorphicUDAFTransducers(I, U); false gap> M := MinimalUDAFTransducer(I); <UDAF Transducer whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 4 states.> gap> AreIsomorphicUDAFTransducers(M, U); true
2.1-12 \*‣ \*( T1, T2 ) | ( operation ) |
Returns: an UDAF transducer
The argument is to be a pair of UDAF transducers where the codomain digraph of T1 is the same as the domain digraph of T2.
The output is an UDAF transducer which induces the composite of the UDAF isomorphisms of the input transducers.
gap> L11 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 1); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> L20 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 2, 0); <walk homomorphism from a digraph with 8 edges to a digraph with 2 edges.> gap> T := UDAFTransducer(L11, L20); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> T * T; <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 8 states.>
‣ ComposeUDAFIsomorphisms( S1, S2 ) | ( operation ) |
Returns: an UDAF isomorphism
Returns the UDAF isomorphism obtained by composing the isomorphisms S1 and S2.
This operation can also be called with *.
gap> T1 := ResizeZeroStringTransducer(2, 2, 3);; gap> U1 := UDAFTransducer(T1); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> T2 := ResizeZeroStringTransducer(2, 2, 4);; gap> U2 := UDAFTransducer(T2); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 6 states.> gap> U1 * U2; <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 32 states.>
2.1-14 \*‣ \*( S1, S2 ) | ( operation ) |
Returns: an UDAF isomorphism
Returns the UDAF isomorphism obtained by composing the isomorphisms S1 and S2.
gap> T1 := ResizeZeroStringTransducer(2, 2, 3);; gap> U1 := UDAFTransducer(T1); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> T2 := ResizeZeroStringTransducer(2, 2, 4);; gap> U2 := UDAFTransducer(T2); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 6 states.> gap> U1 * U2; <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 32 states.>
2.1-15 \^‣ \^( S, n ) | ( operation ) |
Returns: an UDAF transducer
Returns the product of S with itself n times for positive n. Returns the product of the inverse of S with itself |n| times otherwise.
gap> T1 := ResizeZeroStringTransducer(2, 2, 3);; gap> U1 := UDAFTransducer(T1); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> U1^2; <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 16 states.> gap> U1^-1; <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.>
‣ UDAFNrStates( T ) | ( attribute ) |
Returns: an integer
Returns the number of states of an UDAF transducer T. That is, the number of vertices of the shared domain of the two UDAF foldings defining T.
gap> T := ResizeZeroStringTransducer(2, 2, 3);; gap> T := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> UDAFNrStates(T); 5
2.1-17 \=‣ \=( arg1, arg2 ) | ( operation ) |
‣ IdentityUDAFTransducer( D ) | ( operation ) |
Returns: an UDAF transducer
Returns the UDAF transducer defined using two copies of the identity folding on the given digraph.
gap> T := IdentityUDAFTransducer(PetersenGraph()); <UDAF Transducer whose domain digraph has 30 edges, whose codomain digraph has 30 edges, and which has 10 states.>
‣ DeterministicDomainCombineEquivalentStates( T ) | ( operation ) |
Returns: an UDAF transducer and a list of lists of integers
It is assumed that the domain folding of T is deterministic. The operation returns the transducer obtained from T by quotienting the the underlying digraph of T as much as possible such that the UDAF foldings of T are still well defined.
The operation also returns the list of equivalence classes of vertices of the above relation.
gap> L10 := LineDigraphWalkHomomorphism(Digraph([[1, 1]]), 1, 0); <walk homomorphism from a digraph with 4 edges to a digraph with 2 edges.> gap> U := UDAFTransducer(L10, L10); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> DeterministicDomainCombineEquivalentStates(U); [ <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.>, [ [ 1, 2 ] ] ]
2.1-20 \^‣ \^( S, n ) | ( operation ) |
Returns: an UDAF isomorphism
Returns the product of S with itself n times for positive n. Returns the product of the inverse of S with itself |n| times otherwise.
gap> T1 := ResizeZeroStringTransducer(2, 2, 3);; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> U1^2; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> U1^-1; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.>
2.1-21 \^‣ \^( S, T ) | ( operation ) |
Returns: an UDAF isomorphism
Returns the conjugate of S by T. That is to say the product T^-1 S T.
gap> T1 := ResizeZeroStringTransducer(2, 2, 3);; gap> U1 := UDAFIsomorphism(T1); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> U1^2; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> U1^-1; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 5 states.> gap> T2 := ResizeZeroStringTransducer(2, 2, 4);; gap> U2 := UDAFIsomorphism(T2); <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 6 states.> gap> U1^U2; <UDAF Isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 6 states.>
In this section we describe methods for working with isomorphisms between subshifts of finite type. If D is a finite digraph, then the corresponding shift space is defined to be the topological space of biinfinite edge walks throught D with the product topology. We call such a space a shift space. We call the dynamical system consisting of this space and the homomorphism defined by shifting the indexing of a walk by one, a subshift of finite type. If f is any isomorphism between the subshifts of finite type corresponding to two digraphs A and B, then one can find a third digraph C and a pair of two-sided f1:C->A and f2:C->B such that f is equal to the composit of the inverse of the homeomorphism induced by f1 with the homeomorphism induced by f2. This is how shift isomorphisms are handled in this package. Many of the functions in this section use UDAF transducers as a base and hense require the given digraphs to be UDAF digraphs.
‣ ShiftIsomorphism( T ) | ( operation ) |
Returns: an isomorphism of subshifts of finite type
Creates an object called a shift homomorphism. A shift isomorphism is a homomorphism between subshifts of finite type. This input method requires a full shift.
This is input as synchronous transducer from the aaa package (https://github.com/gap-packages/aaa) which is strongly synchronizing and such that the map it defines on the shift space is a bijection.
gap> gap> T := Transducer(2, 2, [[1, 2], [1, 2]], [[[1], [1]], [[0], [0]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 2 states.> gap> ShiftIsomorphism(T); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> WalkHomomorphism(Digraph([[1, 1]]), Digraph([[1, 2], [1]]), [1], [[1], [2, 3]]);
‣ ShiftIsomorphism( T ) | ( operation ) |
Returns: an isomorphism of subshifts of finite type
Creates an object called a shift homomorphism. A shift isomorphism is a homomorphism between subshifts of finite type.
This is input as an UDAF transducer for which both UDAF foldings are two-sided foldings. The isomorphism is the composite of the inverse of the homeomorphism induced by the first folding with the homeomorphism induced by the second folding.
gap> S := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1, 1, 1]]))); <shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 1 state.> gap> T := BlockCodeTransducer(2, 2, x-> [x[1]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 4 states.> gap> T := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> S := ShiftIsomorphism(T); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.>
‣ ShiftIsomorphism( T ) | ( operation ) |
Returns: an isomorphism of subshifts of finite type
Creates an object called a shift homomorphism. A shift isomorphism is a homomorphism between subshifts of finite type.
This is input as a minimal UDAF transducer and a valid annotation of its codomain folding. The isomorphism is the composite of the inverse of the homeomorphism induced by the first folding with the homeomorphism induced by the second folding using the annotation.
gap> S := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), > [-1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> T := BlockCodeTransducer(2, 2, x-> [x[1]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 4 states.> gap> T := UDAFTransducer(T); <UDAF Transducer whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> S := ShiftIsomorphism(T); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> S2 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [2]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 4 states.> gap> S=S2; true
‣ ComposeShiftIsomorphisms( S1, S2 ) | ( operation ) |
Returns: a shift isomorphism
Returns the shift isomorphism obtained by composing the homeomorphisms S1 and S2.
This operation can also be called with *.
gap> SM1 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [-1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> S0 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [0]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> S1 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> SM1 * S1 = S0; true
2.2-5 \*‣ \*( S1, S2 ) | ( operation ) |
Returns: a shift isomorphism
Returns the shift isomorphism obtained by composing the homeomorphisms S1 and S2.
gap> SM1 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [-1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> S0 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [0]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> S1 := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), [1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> SM1 * S1 = S0; true
2.2-6 \^‣ \^( S, T ) | ( operation ) |
Returns: a shift isomorphism
Returns the conjugate of S by T. That is to say the product T^-1 S T.
gap> C := Transducer(3, 3, [[1, 1, 1]], [[[1], [2], [0]]]); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 1 state.> gap> C:= ShiftIsomorphism(UDAFTransducer(C)); <shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 1 state.> gap> Fig5L := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[1], [2], [3], [1], [2], [3], [1], [2], [3]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5R := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[3], [1], [2], [3], [2], [1], [3], [2], [1]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5 := ShiftIsomorphism(UDAFTransducer(Fig5L, Fig5R)); <shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 3 states.> gap> Fig5^C; <shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 9 states.>
‣ IdentityShiftIsomorphism( n ) | ( operation ) |
Returns: a shift isomorphism
Returns the identity shift isomorphism on for the shift space of the digraph with one vertex and n edges (for n at least 2).
gap> IdentityShiftIsomorphism(2); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 1 state.> gap> IdentityShiftIsomorphism(4); <shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 1 state.>
2.2-8 \^‣ \^( S, n ) | ( operation ) |
Returns: a shift isomorphism
Returns the product of S with itself n times for positive n. Returns the product of the inverse of S with itself |n| times otherwise.
gap> S := ShiftIsomorphism(IdentityUDAFTransducer(Digraph([[1, 1]])), > [1]); <shift isomorphism whose domain digraph has 2 edges, whose codomain digraph has 2 edges, and which has 2 states.> gap> S!.Annotation; [ 1 ] gap> (S^3)!.Annotation; [ 3 ] gap> (S^-2)!.Annotation; [ -2 ]
In this section we describe methods for working with isomorphisms between one-sided subshifts of finite type. If D is a finite digraph, then the corresponding one-sided shift space is defined to be the topological space of backwards infinite edge walks throught D with the product topology. We call such a space a one-sided shift space. We call the dynamical system consisting of this space and the continuous map defined by deleting the last edge in a walk (and reindexing the remaining edges) a one-sided subshift of finite type. If f is any isomorphism between the one-sided subshifts of finite type corresponding to two digraphs A and B, then one can find a third digraph C and a pair of one-sided foldings f1:C->A and f2:C->B such that f is equal to the composit of the inverse of the homeomorphism induced by f1 with the homeomorphism induced by f2. This is how one-sided shift isomorphisms are handled in this package. Many of the functions in this section use UDAF transducers as a base and hense require the given digraphs to be UDAF digraphs.
‣ OneSidedShiftIsomorphism( T ) | ( operation ) |
Returns: an isomorphism of one-sided subshifts of finite type
Creates an object called a one-sided shift homomorphism. A one-sided shift isomorphism is a homomorphism between the backwards infinite walk spaces of domain and codomain digraph which commutes with the shift map (which removes the last edge in the walk).
This is input as an UDAF transducer for which both UDAF foldings are one-sided foldings. The isomorphism is the composite of the inverse of the homeomorphism induced by the first folding with the homeomorphism induced by the second folding.
gap> Fig5L := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[1], [2], [3], [1], [2], [3], [1], [2], [3]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5R := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[3], [1], [2], [3], [2], [1], [3], [2], [1]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5 := UDAFTransducer(Fig5L, Fig5R); gap> Fig5 := OneSidedShiftIsomorphism(Fig5); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.>
‣ OneSidedShiftIsomorphism( F1, F2 ) | ( operation ) |
Returns: an isomorphism of one-sided subshifts of finite type
Creates an object called a one-sided shift homomorphism. A one-sided shift isomorphism is a homomorphism between the backwards infinite walk spaces of domain and codomain digraph which commutes with the shift map (which removes the last edge in the walk).
This is input as a pair of one-sided foldings. The isomorphism is the composite of the inverse of the homeomorphism induced by the first folding with the homeomorphism induced by the second folding.
gap> Fig5L := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[1], [2], [3], [1], [2], [3], [1], [2], [3]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5R := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[3], [1], [2], [3], [2], [1], [3], [2], [1]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5 := OneSidedShiftIsomorphism(Fig5L, Fig5R); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.>
‣ ComposeOneSidedShiftIsomorphisms( S1, S2 ) | ( operation ) |
Returns: a one-sided shift isomorphism
Returns the one-sided shift isomorphism obtained by composing the homeomorphisms S1 and S2.
This operation can also be called with *.
gap> f := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 1 ], > [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> g := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 4 ], [ 3 ], [ 2 ], [ 1 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], > [ 1 ], [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> T := OneSidedShiftIsomorphism(f, g); <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 6 states.> gap> S := OneSidedTorsionDecomposition(T); [ <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 3 states.>, <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 5 states.> ] gap> S[1] * S[2] = T; true
2.3-4 \*‣ \*( S1, S2 ) | ( operation ) |
Returns: a one-sided shift isomorphism
Returns the one-sided shift isomorphism obtained by composing the homeomorphisms S1 and S2.
gap> f := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 1 ], > [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> g := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 4 ], [ 3 ], [ 2 ], [ 1 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], > [ 1 ], [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> T := OneSidedShiftIsomorphism(f, g); <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 6 states.> gap> S := OneSidedTorsionDecomposition(T); [ <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 3 states.>, <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 5 states.> ] gap> S[1] * S[2] = T; true
2.3-5 \^‣ \^( S, T ) | ( operation ) |
Returns: a one-sided shift isomorphism
Returns the conjugate of S by T. That is to say the product T^-1 S T.
gap> C := Transducer(3, 3, [[1, 1, 1]], [[[1], [2], [0]]]); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 1 state.> gap> C:= OneSidedShiftIsomorphism(UDAFTransducer(C)); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 1 state.> gap> Fig5L := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[1], [2], [3], [1], [2], [3], [1], [2], [3]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5R := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[3], [1], [2], [3], [2], [1], [3], [2], [1]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5 := OneSidedShiftIsomorphism(Fig5L, Fig5R); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.> gap> Fig5^C; <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.>
2.3-6 \^‣ \^( S, n ) | ( operation ) |
Returns: a one-sided shift isomorphism
Returns the product of S with itself n times for positive n. Returns the product of the inverse of S with itself |n| times otherwise.
gap> Fig5L := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[1], [2], [3], [1], [2], [3], [1], [2], [3]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5R := WalkHomomorphism(Digraph([[1, 2, 3], [1, 2, 3], [1, 2, 3]]), > Digraph([[1, 1, 1]]), > [1, 1, 1], > [[3], [1], [2], [3], [2], [1], [3], [2], [1]]); <walk homomorphism from a digraph with 9 edges to a digraph with 3 edges.> gap> Fig5 := OneSidedShiftIsomorphism(Fig5L, Fig5R); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.> gap> Fig5^2; <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 3 states.> gap> Fig5^-1; <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 2 states.>
‣ OneSidedTorsionDecomposition( T ) | ( attribute ) |
Returns: a list of one-sided shift isomorphisms
It is required that the given isomorphism have the same domain and codomain digraph. Returns a list of one-sided shift isomorphisms of finite order whose composite is the given isomorphism T. This is done via an slight generalisation of the algorithm presented in https://arxiv.org/abs/2004.08478v4by.
gap> f := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], [ 1 ], > [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> g := WalkHomomorphism(Digraph([ [ 6, 3 ], [ 5, 3 ], [ 2, 1 ], [ 5, 3 ], > [ 1, 2 ], [ 1, 4 ] ]), Digraph([ [ 2, 2 ], [ 1, 1 ] ]), [ 2, 2, 1, 2, 1, 1 ], > [ [ 3 ], [ 4 ], [ 4 ], [ 3 ], [ 2 ], [ 1 ], [ 3 ], [ 4 ], [ 1 ], [ 2 ], > [ 1 ], [ 2 ] ]); <walk homomorphism from a digraph with 12 edges to a digraph with 4 edges.> gap> T := OneSidedShiftIsomorphism(f, g); <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 6 states.> gap> S := OneSidedTorsionDecomposition(T); [ <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 3 states.>, <one sided shift isomorphism whose domain digraph has 4 edges, whose codomain digraph has 4 edges, and which has 5 states.> ] gap> S[1] * S[2] = T; true
‣ RandomOneSidedAut( D ) | ( operation ) |
Returns: a one-sided shift isomorphism
Returns a random one-sided isomorphism with D as it's domain and codomain digraph.
Warning this commant is currently very slow even on rather small examples.
gap> RandomOneSidedAut(Digraph([[1, 1, 1]])); <one sided shift isomorphism whose domain digraph has 3 edges, whose codomain digraph has 3 edges, and which has 3 states.>
By a GNS transducer we mean a transducer of the type described by Grigorchuk, Nekrashevich, and Sushchanskii as defined in the package aaa (https://github.com/gap-packages/aaa).
‣ BlockCodeTransducer( AlphSize, History, BlockMap ) | ( operation ) |
Returns: an aaa transducer object
AlphSize is assumed to be an integer which is at least 2. History is assumed to be a non-negative integer. BlockMap is a function which assigns each word over the alphabet [0, 1, ..., AlphSize - 1] of length History + 1 another word over the same alphbet.
The output object is an aaa (https://github.com/gap-packages/aaa) transducer whose input and output alphabets have AlphSize letters. There is a state for each word of length History in the alphbet. Transitions are done as is DeBruijin graphs, that is a letter a is read from a state w by transitioning to the state which is a suffix of the word wa. In this case the word wrtten that the word objetain by applying the function BlockMap to wa.
gap> T := BlockCodeTransducer(2, 2, x-> [x[1]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 4 states.>
‣ DeBruijnTransducer( AlphSize, History ) | ( operation ) |
Returns: an aaa transducer
The output object is an aaa (https://github.com/gap-packages/aaa) transducer whose input and output alphabets have AlphSize letters. There is a state for each word of length History in the alphbet. Transitions are done as is DeBruijin graphs, that is a letter a is read from a state w by transitioning to the state which is a suffix of the word wa. The write function is the identity function.
gap> DeBruijnTransducer(2, 3); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 8 states.>
‣ ResizeZeroStringTransducer( AlphSize, Len1, Len2 ) | ( operation ) |
Returns: an aaa transducer
It is required that AlphSize is at least 2. Returns the minimal aaa transducer which defines the homeomorphism of cantor space defined by finding all maximal contiguous all zero substrings in the given input, and replacing those with length Len1 with those with length Len2 and vice versa.
gap> ResizeZeroStringTransducer(2, 1, 3); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 5 states.> gap> ResizeZeroStringTransducer(3, 2, 1); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 4 states.>
‣ IsLipschitzTransducer( T ) | ( operation ) |
Returns: true or false
We say that a trasducer T is Lipschitz if for each state of T defines a well-defined function from the set of forwards infinite words in the domain alphabet to the set of infinite words, and these maps are all Lipschitz continuous.
This is done with respect to the metric:
d(x_0x_1x_2..., y_0y_1y_2...) := inf({1/2^n|where n is such that x_i=y_i for all i < n}).
Note that it is possible for the minimal transducer of a Lipschitz function to not be Lipschitz as the minimal transducer of a map with a constant state will have states which do not give output.
gap> T := Transducer(2, 2, [[2, 2], [1, 1]],[[[],[]],[[1],[1]]]);; gap> IsLipschitzTransducer(T); true gap> T := AlphabetChangeTransducer(4, 3);; gap> IsLipschitzTransducer(T); true gap> T := Transducer(3, 3, [[2, 2, 1], [3, 4, 3], [1, 1, 2], [2, 2, 3]], > [[[1, 0, 1], [0], [2, 2, 0]], [[], [2], [0, 1, 2, 2]], [[], [0, 1], [2, 2]], > [[2, 2], [0, 2], [1, 2, 2]]]);; gap> IsLipschitzTransducer(T); false gap> T := AlphabetChangeTransducer(3, 4);; gap> IsLipschitzTransducer(T); false gap> T := Transducer(2, 2, [[1, 2], [1, 3], [1, 3]], [[[1, 0], []], [[0], > [1, 1]], [[0], [1]]]);; gap> IsLipschitzTransducer(T); false gap> M := MinimalTransducer(T); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 2 states.> gap> IsLipschitzTransducer(T); true gap> IsLipschitzTransducer(M); false
‣ TransducerCore( T ) | ( operation ) |
Returns: an aaa transducer
If T is a synchronizing transducer, then we define the core of T to be the smallest non-empty transducer obtainable from T by removing states from T.
The Operation takes as input an synchronizing transducer and returns its Core
gap> T := Transducer(2, 2, [[2, 3], [3, 4], [3, 2], [3, 4]], > [[[1], [1, 0, 1]], [[1], []], [[1], [0, 1]], [[1], [0]]]);; gap> C := TransducerCore(T);; gap> OutputFunction(C); [ [ [ 1 ], [ 0, 1 ] ], [ [ 1 ], [ ] ], [ [ 1 ], [ 0 ] ] ] gap> TransitionFunction(C); [ [ 1, 2 ], [ 1, 3 ], [ 1, 3 ] ] gap> T := Transducer(2, 2, [[1, 2], [1, 3], [1, 3]], [[[1, 0], []], [[0], > [1, 1]], [[0], [1]]]);; gap> C := TransducerCore(T);; gap> OutputFunction(C); [ [ [ 1, 0 ], [ ] ], [ [ 0 ], [ 1, 1 ] ], [ [ 0 ], [ 1 ] ] ] gap> TransitionFunction(C); [ [ 1, 2 ], [ 1, 3 ], [ 1, 3 ] ] gap> T := Transducer(2, 2, [[2, 2], [1, 1]], [[[1], [1]], [[0], [0]]]); transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 2 states.> gap> TransducerCore(T); Error, autshift: TransducerCore: usage, the transducer must be synchronizing
‣ IsCoreTransducer( T ) | ( attribute ) |
Returns: true or false
If T is a synchronizing transducer, then we define the core of T to be the smallest non-empty transducer obtainable from T by removing states from T. We say that T is core if it is equal to its core.
The attribute returns true if and only if the given transducer is core.
gap> T := Transducer(2, 2, [[2, 3], [3, 4], [3, 2], [3, 4]], > [[[1], [1, 0, 1]], [[1], []], [[1], [0, 1]], [[1], [0]]]);; gap> IsCoreTransducer(T); false gap> C := TransducerCore(T);; gap> IsCoreTransducer(C); true gap> T := Transducer(2, 2, [[1, 2], [1, 3], [1, 3]], [[[1, 0], []], [[0], > [1, 1]], [[0], [1]]]);; gap> IsCoreTransducer(T); true gap> T := Transducer(2, 2, [[1, 2], [1, 3], [1, 3]], [[[1, 0], []], [[0], > [1, 1]], [[0], [1]]]);; gap> IsCoreTransducer(T); true gap> T := Transducer(2, 4, [[1, 2], [1, 3], [1, 1]], [[[0], []], [[1], []], > [[2], [3]]]);; gap> IsCoreTransducer(T); false gap> T := DeBruijnTransducer(2, 3);; gap> IsCoreTransducer(T); true gap> T := DeBruijnTransducer(3, 2);; gap> IsCoreTransducer(T); true
generated by GAPDoc2HTML