In this chapter we decribe the methods that are available in the aaa package to perform operations on aaa transducers. These methods are implementations of the algorithms introduced in [GNS00].
The following are the methods that can be used to analyze aaa transducers.
‣ InverseTransducer( T ) | ( operation ) |
Returns: A transducer.
For an invertible transducer T whose first state is a homeomorphism state, the operation InverseTransducer(T) returns the inverse of T. Please note that it is the user's responsibility to ensure that the transducer T is both invertible and that its first state is a homeomorphism state.
gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], [1]], > [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]);; gap> g := InverseTransducer(f);; gap> w := TransducerFunction(f, [0, 1], 1)[1]; [ 2, 0 ] gap> TransducerFunction(g, w, 1)[1]; [ 0, 1 ]
‣ TransducerProduct( T, P ) | ( operation ) |
Returns: A transducer.
For two transducers T and P, the operation TransducerProduct(T, P) returns the product of the transducers T and P. The product command can also be run with *. Moreover, if n is an integer, then the T^n returns the product of T with itself n times (n may only be negative if T is invertible). If T is invertible, then the product T^-1*P*T can be input as P^T.
gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], [1]], > [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 3 states.> gap> ff := TransducerProduct(f, f); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 9 states.>
‣ RemoveStatesWithIncompleteResponse( T ) | ( operation ) |
Returns: A transducer.
For a transducer T that has states with incomplete response, the operation RemoveStatesWithIncompleteResponse(T) returns a transducer P that has one more state than T(acting as the new initial state) and which has no states with incomplete response. State s of the transducer T is state s + 1 of the transducer P.
gap> t := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], []], > [[1, 0, 0], [1], [1]], [[0, 2], [2], [0]]]); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 3 states.> gap> p := RemoveStatesWithIncompleteResponse(t); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 4 states.> gap> TransducerFunction(t, [2], 1)[1]; TransducerFunction(t, [1], 2)[1]; [ ] [ 1 ] gap> TransducerFunction(p, [2], 2)[1]; [ 1 ]
‣ RemoveInaccessibleStates( T ) | ( operation ) |
Returns: A transducer.
For a transducer T, the operation RemoveInaccessibleStates(T) returns the transducer that is obtained by removing the states that are not accesssible from state 1.
gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], [1]], > [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 3 states.> gap> ff := TransducerProduct(f, f); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 9 states.> gap> m := RemoveInaccessibleStates(ff); <transducer with input alphabet on 3 symbols, output alphabet on 3 symbols, and 6 states.>
‣ CombineEquivalentStates( T ) | ( operation ) |
Returns: A transducer.
For a transducer T, the operation CombineEquivalentStates(T) returns the transducer that is obtained by identifying states from which all finite words write the same word.
gap> T := Transducer(2, 2, [[1, 3], [2, 1], [1, 1], [1, 3]], [[[0], [0]], > [[1, 1], [0]], [[0], [0, 1]], [[0], [0]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 4 states.> gap> T2 := CombineEquivalentStates(T); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 3 states.> gap> OutputFunction(T); [ [ [ 0 ], [ 0 ] ], [ [ 1, 1 ], [ 0 ] ], [ [ 0 ], [ 0, 1 ] ], [ [ 0 ], [ 0 ] ] ] gap> TransitionFunction(T); [ [ 1, 3 ], [ 2, 1 ], [ 1, 1 ], [ 1, 3 ] ]
‣ MinimalTransducer( T ) | ( operation ) |
Returns: A transducer.
Every transducer has a minimal omega-equivalent form (this transducer produces the same outputs on all infinite length inputs as the original). One arrives at this form by first removing inaccessible states, then removing incomplete response from all states, and finally combining equivalent states. Those three operations are described above. For a transducer T, the operation MinimalTransducer(T) returns the transducer's minimal omega-equivalent form.
gap> T := Transducer(2, 2, [[1, 3], [2, 1], [1, 1], [1, 3]], [[[0], [0]], > [[1, 1], [0]], [[0], [0, 1]], [[0], [0]]]); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 4 states.> gap> M := MinimalTransducer(T); <transducer with input alphabet on 2 symbols, output alphabet on 2 symbols, and 3 states.> gap> OutputFunction(M); [ [ [ 0, 0, 0 ], [ 0, 0 ] ], [ [ 0 ], [ ] ], [ [ 0, 0 ], [ 1, 0, 0 ] ] ] gap> TransitionFunction(M); [ [ 2, 3 ], [ 2, 3 ], [ 2, 2 ] ]
‣ CopyTransducerWithInitialState( T, m ) | ( operation ) |
Returns: A transducer.
For a transducer T and a positive integer m, the operation CopyTransducerWithInitialState(T, m) returns the transducer that is obtained by relabeling the states of T such that state m becomes state 1, but is otherwise equivalent to T.
gap> f := Transducer(3, 3, [[1, 1, 2], [1, 3, 2], [1, 1, 2]], [[[2], [0], [1]], > [[0, 0], [], [1]], [[0, 2], [2], [0, 1]]]);; gap> p := CopyTransducerWithInitialState(f, 3);; gap> TransducerFunction(f, [0, 1, 0], 3); [ [ 0, 2, 0, 2 ], 1 ] gap> TransducerFunction(p, [0, 1, 0], 1); [ [ 0, 2, 0, 2 ], 2 ]
‣ TransducerConstantStateOutputs( T ) | ( operation ) |
Returns: A list.
If the transducer T is degenerate, then this operation returns fail. A state of a trasducer is called constant if it induces a constant map from the space of infinite words in its input alphabet the the space of infinite words in its output alphabet. For a non-degenerate transducer T, the operation TransducerConstantStateOutputs(T) returns a list containing two lists. The first is a list of the constant states of T. The second is a list of the values taken by those states. Such a value is represented as a string "v(w)*" where v and w are finite strings in the output alphabet of T. The string "v(w)*" represents the infinite word vwwwwww... (v and w are always chosen to be as short as possible).
gap> T := Transducer(2, 2, [[1, 2], [2, 2]], [[[1], [1, 1]], [[1], [1, 1]]]);; gap> TransducerConstantStateOutputs(T); [ [ 1, 2 ], [ "(1)*", "(1)*" ] ] gap> T := Transducer(2, 3, [[2, 3], [2, 3], [2, 3]], [[[2, 0], [2]], > [[1, 1, 0], [1, 1]], [[0], [0, 1, 1]]]);; gap> T := Transducer(2, 2, [[1, 2], [2, 2]], [[[0], [1, 1]], [[1], [1, 1]]]);; gap> TransducerConstantStateOutputs(T); [ [ 2 ], [ "(1)*" ] ] gap> TransducerConstantStateOutputs(T); [ [ 1, 2, 3 ], [ "2(011)*", "(110)*", "(011)*" ] ] gap> T := Transducer(2, 2, [[3, 3], [1, 1], [2, 1]], [[[1], []], > [[0, 1, 1, 1], [0]], [[0], [1]]]);; gap> TransducerConstantStateOutputs(T); [ [ ], [ ] ]
generated by GAPDoc2HTML