############################################################################# ## #W selfsimsg.gd automgrp package Yevgen Muntyan #W Dmytro Savchuk ## automgrp v 1.3.1 ## #Y Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk ## ############################################################################# ## #C IsSelfSimSemigroup( ) ## ## Whether semigroup is generated by elements from category IsSelfSim. ## DeclareSynonym("IsSelfSimSemigroup", IsSemigroup and IsSelfSimCollection); ############################################################################# ## #O SelfSimilarSemigroup( [, ] ) #O SelfSimilarSemigroup( [, , ] ) #O SelfSimilarSemigroup( [, ] ) ## ## Creates the semigroup generated by the wreath recursion, described by ## or , or given by the argument . Note, that on the contrary to ## `AutomatonSemigroup' ("AutomatonSemigroup") in some cases the defined semigroup ## may not be self-similar, since the sections of generators may include inverses of ## generators or trivial homomorphisms, not included in the semigroup generated by the ## generators. If one needs to have self-similarity it is always possible to include the ## necessary sections in the generating set. ## ## The argument is a conventional notation of the form ## `name1=(word11,word12,...,word1d)trans1, name2=...' ## where each `name\*' is a name of a state, `word\*' is an associative word ## over the alphabet consisting of all `name\*', and each `trans\*' is either a ## permutation written in {\GAP} notation, or a list defining a transformation ## of the alphabet via `Transformation(trans\*)'. Trivial permutations may be ## omitted. This function ignores whitespace, and states may be separated ## by commas or semicolons. ## ## The argument is a list consisting of $n$ entries corresponding to $n$ generators of the semigroup. ## Each entry is of the form $[a_1,\.\.\.,a_d,p]$, ## where $d \geq 2$ is the size of the alphabet the semigroup acts on, $a_i$ are lists ## acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z', ## then `[1, 1, 2, 3]' will produce `x^2*y*z') ## representing the sections of the corresponding generator at all vertices of the first level of the tree; ## and $p$ is a transformation of the alphabet describing the action of the corresponding ## generator. ## ## The optional arguments and have the same meaning as in `SelfSimilarGroup' (see "SelfSimilarGroup"). ## ## \beginexample ## gap> SelfSimilarSemigroup("a=(a*b,b)[1,1], b=(a,b^2*a)(1,2)"); ## < a, b > ## gap> SelfSimilarSemigroup("a=(b,a,a^3)(2,3), b=(1,a*b,b^-1)(1,2,3)"); ## < a, b > ## gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]"); ## ## gap> SelfSimilarSemigroup(A); ## < f0, f1 > ## \endexample ## In the second form of this operation the definition of the first semigroup ## looks like ## \beginexample ## gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]); ## < a, b > ## \endexample ## DeclareOperation("SelfSimilarSemigroup", [IsList]); DeclareOperation("SelfSimilarSemigroup", [IsList, IsList]); DeclareOperation("SelfSimilarSemigroup", [IsMealyAutomaton]); DeclareOperation("SelfSimilarSemigroup", [IsList, IsBool]); DeclareOperation("SelfSimilarSemigroup", [IsList, IsList, IsBool]); DeclareOperation("SelfSimilarSemigroup", [IsMealyAutomaton, IsBool]); ############################################################################# ## #A UnderlyingSelfSimFamily( ) ## ## Returns the family to which elements of belong. ## DeclareAttribute("UnderlyingSelfSimFamily", IsSelfSimCollection); InstallSubsetMaintenance(UnderlyingSelfSimFamily, IsCollection, IsCollection); ############################################################################# ## #A UnderlyingFreeGenerators() #A UnderlyingFreeMonoid() #A UnderlyingFreeGroup() ## DeclareAttribute("UnderlyingFreeGenerators", IsSelfSimSemigroup, "mutable"); DeclareAttribute("UnderlyingFreeMonoid", IsSelfSimSemigroup); DeclareAttribute("UnderlyingFreeGroup", IsSelfSimSemigroup); ############################################################################### ## #A RecurList() ## ## Returns an internal representation of the wreath recursion of the ## self-similar group (semigroup) containing . ## \beginexample ## gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)"); ## < a, b > ## gap> RecurList(R); ## [ [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ -1 ], [ -2 ], () ], ## [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ 1 ], [ 2 ], () ] ] ## \endexample ## DeclareAttribute("RecurList", IsSelfSimSemigroup, "mutable"); DeclareAttribute("GeneratingRecurList", IsSelfSimSemigroup, "mutable"); ############################################################################# ## #P IsSemigroupOfSelfSimFamily( ) ## ## Whether semigroup is the whole semigroup generated by the automaton used to ## construct elements of . ## DeclareProperty("IsSemigroupOfSelfSimFamily", IsSelfSimSemigroup); InstallTrueMethod(IsSelfSimilar, IsSemigroupOfSelfSimFamily); ############################################################################# ## #P IsSelfSimilarSemigroup () ## ## is `true' if is created using the command `SelfSimilarSemigroup' ("SelfSimilarSemigroup") ## or if generators of coincide with generators of corresponding family, and `false' otherwise. ## To test whether is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. ## DeclareProperty("IsSelfSimilarSemigroup", IsSelfSimSemigroup); InstallTrueMethod(IsSemigroupOfSelfSimFamily, IsSelfSimilarSemigroup); ############################################################################# ## #P IsFiniteState () ## ## For a group or semigroup of homomorphisms of the tree defined using a ## wreath recursion, returns `true' if all ## generators can be represented as finite automata (have finitely many different ## sections). ## It will never stop if the free reduction of words is not sufficient to establish ## the finite-state property or if the group is not finite-state. ## In case is a finite-state group it automatically computes the attributes ## `UnderlyingAutomatonGroup'() ("UnderlyingAutomatonGroup"), ## `IsomorphicAutomGroup'() ("IsomorphicAutomGroup") and ## `MonomorphismToAutomatonGroup'() ("MonomorphismToAutomatonGroup"). ## For a finite-state semigroup it computes the corresponding attributes ## `UnderlyingAutomatonSemigroup'() ("UnderlyingAutomatonSemigroup"), ## `IsomorphicAutomSemigroup'() ("IsomorphicAutomSemigroup") and ## `MonomorphismToAutomatonSemigroup'() ("MonomorphismToAutomatonSemigroup"). ## \beginexample ## gap> W := SelfSimilarGroup("x=(x^-1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)"); ## < x, y, z > ## gap> IsFiniteState(W); ## true ## gap> Size(GeneratorsOfGroup(UnderlyingAutomatonGroup(W))); ## 50 ## \endexample DeclareProperty("IsFiniteState", IsSelfSimSemigroup); ############################################################################# ## #A IsomorphicAutomSemigroup() ## ## In case is finite-state returns a semigroup generated by automata, isomorphic to , ## which is a subsemigroup of `UnderlyingAutomatonSemigroup'() (see "UnderlyingAutomatonSemigroup"). ## The natural isomorphism between and `IsomorphicAutomSemigroup'() is stored in the ## attribute `MonomorphismToAutomatonSemigroup'() ("MonomorphismToAutomatonSemigroup"). ## \beginexample ## gap> R := SelfSimilarSemigroup("a=(1,1)[1,1], b=(a*c,1)(1,2), c=(1,a*b)"); ## < a, b, c > ## gap> UR := UnderlyingAutomatonSemigroup(R); ## < 1, a1, a3, a5, a6 > ## gap> IR := IsomorphicAutomSemigroup(R); ## < a1, a3, a5 > ## gap> hom := MonomorphismToAutomatonSemigroup(R); ## MappingByFunction( < a, b, c >, < a1, a3, a5 >, function( a ) ... end, functio\ ## n( b ) ... end ) ## gap> (a*b)^hom; ## a1*a3 ## gap> PreImagesRepresentative(hom, last); ## a*b ## gap> List(GeneratorsOfSemigroup(UR), x -> PreImagesRepresentative(hom, x)); ## [ 1, a, b, c, a*b ] ## \endexample ## ## All these operations work also for the subsemigroups of semigroups generated by ## `SelfSimilarSemigroup' ("SelfSimilarSemigroup"). ## \beginexample ## gap> T := Semigroup([a*b, b^2]); ## < a*b, b^2 > ## gap> IT := IsomorphicAutomSemigroup(T); ## < a1, a4 > ## \endexample ## Note, that different semigroups have different `UnderlyingAutomSemigroup' attributes. For example, ## the generator `a1' of semigroup `IT' above is different from the generator `a1' of semigroup `IR'. ## DeclareAttribute("IsomorphicAutomSemigroup", IsSelfSimSemigroup, "mutable"); ############################################################################# ## #A UnderlyingAutomatonSemigroup() ## ## In case is finite-state returns a self-similar closure of as a semigroup ## generated by automaton. ## The natural monomorphism from and `UnderlyingAutomatonSemigroup'() is stored in the ## attribute `MonomorphismToAutomatonSemigroup'() ("MonomorphismToAutomatonSemigroup"). If ## is created by `SelfSimilarSemigroup' (see "SelfSimilarSemigroup"), then the self-similar closure ## of coincides with , so one can use `MonomorphismToAutomatonSemigroup'() to ## get preimages of elements of `UnderlyingAutomatonSemigroup'() in . See the example for ## `IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). ## DeclareAttribute("UnderlyingAutomatonSemigroup", IsSelfSimSemigroup, "mutable"); ############################################################################# ## #A MonomorphismToAutomatonSemigroup() ## ## In case is finite-state returns a monomorphism from into `UnderlyingAutomatonSemigroup'() ## (see "UnderlyingAutomatonSemigroup"). If is created by `SelfSimilarSemigroup' ## (see "SelfSimilarSemigroup"), ## then one can use `MonomorphismToAutomatonSemigroup'() to ## get preimages of elements of `UnderlyingAutomatonSemigroup'() in . See the example for ## `IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). ## DeclareAttribute("MonomorphismToAutomatonSemigroup", IsSelfSimSemigroup, "mutable"); ############################################################################# ## #A SemigroupOfSelfSimFamily() ## DeclareAttribute("SemigroupOfSelfSimFamily", IsSelfSimSemigroup); #E