[GAP Forum] Algorithmic question

[Asst. Prof. Dmitrii (Dima) Pasechnik]

Dear Kasper,
as far as I can see, a necessary condition is that the cone C
generated by M is simplicial (i.e. has exactly as many extreme rays as
the dimension of the span of M in R^n, say n'), so one should be able
to
compute these rays efficiently, using linear programming (as you do
not need to enumerate all the rays of C,
which can be exponential in running time, but stop as soon as you have
exactly  n' rays, and no more)

So if  C is not simplcial, M is not free.
If C is simplicial, then one has to find out whether the extreme rays
of C generate M, or not.
The latter is probably some kind of volume computation, which again
can be done efficiently.

Please let me know whether you need more details,
Dmitrii

On 3 February 2011 20:56, Kasper Andersen <kksa at math.ku.dk> wrote:
> Dear forum,
>
> This is strictly speaking not a GAP question but hopefully someone on the
> list knows something about this....
>
> Suppose A is a subgroup of Z^n. The M=A\cap N_0^n is a finitely generated
> monoid. How does one test effectively decide whether M is a free monoid?
>
> One could of course first find a minimal generating set of M and check if
> this set is linearly independent -- however I dont know efficient
> algorithms for finding a minimal generating set.
>
> Furthermore one could hope that one could decide freeness without
> computing a minimal generating set....
>
> thanks in advance,
>
> Kasper Andersen
> University of Copenhagen
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>



--
Dmitrii Pasechnik
-----
DISCLAIMER: Any text following this sentence does not constitute a
part of this message, and was added automatically during transmission.

CONFIDENTIALITY: This email is intended solely for the person(s) named and may be confidential and/or privileged. If you are not the intended recipient, please delete it, notify us and do not copy, use, or disclose its content. Thank you.

Towards A Sustainable Earth: Print Only When Necessary