On 07/12/16 01:01, Waldek Hebisch wrote:
About your proposal: note that notion of permutation
group is closely related to notion of subgroup (and
at categorical level with final object of a category).
Finitely presented groups are related to quotients
(and first object of a category). As a little remark
note that in both cases we natuarally get semigroup
first, in case of permutations semigroup of all mappings
from a set to itself, in case of free group we get
free semigroup. Then we "correct" deficiency, in
case of permutations taking subsemigroup of
invertible maps, in case of free group taking
quotient (declaring some generators of free semigroup
as inverses of group generators).
Now, one natural thing would be a way to produce group
given group presentation. There is very strong
obstacle to this due to unsolvability of word problem.
IMO the right way to go forward it to look at cases
when word problem is solvable. This happens if
we know something special about groups, for example
for abelian groups word problem is solvable. This
happens if presentation has special form, like
for result of Knuth-Bendix completition. We could
try postpone solving hard problems and require that
to create finitely presented group the user has
to provide solver for word problem
Concerning structure on Type: currently this is done by
declaring specific categories/domains. Union represets
/implements sum. There is Product domain. There is
Subdomian. Each are very special I do not see how
to "generalize" them at computational level. In principle
we could try to add "quotient" constructor. Namely,
to get quotient we need equvalence relation and we could
have something like:
Quitient(S : Type, = : (S, S) -> Boolean) : ....
but that would be of limited use, because for products
there are important features which are preserved, while
for quotients everything depends on equivalence relation.
Existing algebra cheats in some cases, uncoditionaly
declaring features which are valid only if special
conditions are satisfied. For quotient I do not
think cheats are appropriate -- we can not even claim
that features are preserved "in most interesting cases".
And I would like to get rid of cheating.
Orbits need extra structure for example semigroup structure.
Orbits of group actions have specific properties, so
they probably should be studied separately from more
general notions of orbits. And efficient computations
with orbits are possible only in some specific situations.
So no, I think that currently it is not possible to put
more _useful_ general structure on Type.
Waldek,
Thank you very much for this reply, it is very clear.
So we need to keep the groupPresentation domain because we can't add the
functionality to FinitelyPresentedGroup domain. Its therefore worth me
taking time to improve the documentation and content of
groupPresentation domain.
To widen the scope a bit, is it worth filling in the gaps in this table
of domains in the FriCAS library?
outer algebra: PermutationGroup GroupPresentation GroupRepresentation
inner algebra: Permutation Word SquareMatrix
It seems to me that there is merit in having a common design pattern for
this sort of thing since it might help users and developers find the
functionality they need, minimise overlaps and make it easier to convert
between them.
In fact why not have a design pattern (as a hint to developers) which
goes beyond groups to any algebra where we need functions on both
elements and functions on the whole '(sub)type'. Perhaps something like
this pseudo code:
Outer Algebra Design Pattern
----------------------------
OuterAlgebra(S : SetCategory) : public == private where
public ==> SetCategory with
.... function signatures which act on whole 'type' go here
.... or in separate category.
private ==> add
Rep := Record(List InnerAlgebra S, constraints : ...)
.... function definitions which act on whole 'type' go here
Note 1) List here is just computationally efficient set.
Note 2) constraints make algebra less free, example relations.
Note 3) The names 'OuterAlgebra' and 'InnerAlgebra' are replaced by the
actual domain names.
Note 4) When I use the word 'type' here I mean whole inner algebra.
Inner Algebra Design Pattern
----------------------------
InnerAlgebra(S : SetCategory) : public == private where
public ==> InnerAlgebra S with
.... function signatures which act on single element go here
.... or in separate category. Such as:
*: (%, %) -> %
1: %
inv: % -> %
private ==> add
-- representation of the object:
Rep := .... representation of single element
.... function definitions which act on single element go here
Martin B
--
You received this message because you are subscribed to the Google Groups "FriCAS -
computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
