Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Elements of Free Monoids
AUTHORS:
- David Kohel (2005-09-29)
Elements of free monoids are represented internally as lists of pairs of integers. """
#***************************************************************************** # Copyright (C) 2005 David Kohel <kohel@maths.usyd.edu> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty # of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. # # See the GNU General Public License for more details; the full text # is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from six import iteritems, integer_types
from sage.rings.integer import Integer from sage.structure.element import MonoidElement
def is_FreeMonoidElement(x): return isinstance(x, FreeMonoidElement)
class FreeMonoidElement(MonoidElement): """ Element of a free monoid.
EXAMPLES::
sage: a = FreeMonoid(5, 'a').gens() sage: x = a[0]*a[1]*a[4]**3 sage: x**3 a0*a1*a4^3*a0*a1*a4^3*a0*a1*a4^3 sage: x**0 1 sage: x**(-1) Traceback (most recent call last): ... TypeError: bad operand type for unary ~: 'FreeMonoid_class_with_category.element_class' """ def __init__(self, F, x, check=True): """ Create the element `x` of the FreeMonoid `F`.
This should typically be called by a FreeMonoid. """ else: raise TypeError("Argument x (= %s) is of the wrong type."%x) raise TypeError("x (= %s) must be a list of 2-tuples or 1."%x) isinstance(v[1], integer_types + (Integer,))): raise TypeError("x (= %s) must be a list of 2-tuples of integers or 1."%x) else: else: self._element_list = list(x) # make copy, so user can't accidentally change monoid.
else: # TODO: should have some other checks here... raise TypeError("Argument x (= %s) is of the wrong type."%x)
def __hash__(self): r""" TESTS::
sage: R.<x,y> = FreeMonoid(2) sage: hash(x) 1914282862589934403 # 64-bit 139098947 # 32-bit sage: hash(y) 2996819001369607946 # 64-bit 13025034 # 32-bit sage: hash(x*y) 7114093379175463612 # 64-bit 2092317372 # 32-bit """
def __iter__(self): """ Returns an iterator which yields tuples of variable and exponent.
EXAMPLES::
sage: a = FreeMonoid(5, 'a').gens() sage: list(a[0]*a[1]*a[4]**3*a[0]) [(a0, 1), (a1, 1), (a4, 3), (a0, 1)] """ for (index, exponent) in self._element_list)
def _repr_(self): else:
def _latex_(self): r""" Return latex representation of self.
EXAMPLES::
sage: F = FreeMonoid(3, 'a') sage: z = F([(0,5),(1,2),(0,10),(0,2),(1,2)]) sage: z._latex_() 'a_{0}^{5}a_{1}^{2}a_{0}^{12}a_{1}^{2}' sage: F.<alpha,beta,gamma> = FreeMonoid(3) sage: latex(alpha*beta*gamma) \alpha\beta\gamma """ else:
def __call__(self, *x, **kwds): """ EXAMPLES::
sage: M.<x,y,z>=FreeMonoid(3) sage: (x*y).subs(x=1,y=2,z=14) 2 sage: (x*y).subs({x:z,y:z}) z^2 sage: M1=MatrixSpace(ZZ,1,2) sage: M2=MatrixSpace(ZZ,2,1) sage: (x*y).subs({x:M1([1,2]),y:M2([3,4])}) [11]
sage: M.<x,y> = FreeMonoid(2) sage: (x*y).substitute(x=1) y
sage: M.<a> = FreeMonoid(1) sage: a.substitute(a=5) 5
AUTHORS:
- Joel B. Mohler (2007-10-27) """ raise ValueError("must not specify both a keyword and positional argument")
x = self.gens() gens_dict = {name: i for i, name in enumerate(P.variable_names())} for key, value in iteritems(kwds): if key in gens_dict: x[gens_dict[key]] = value
raise ValueError("must specify as many values as generators in parent")
# I don't start with 0, because I don't want to preclude evaluation with #arbitrary objects (e.g. matrices) because of funny coercion. # Take further pains to ensure that non-square matrices are not exponentiated. c = replacement ** exponent else: c = one
else:
return one
def _mul_(self, y): """ Multiply two elements ``self`` and ``y`` of the free monoid.
EXAMPLES::
sage: a = FreeMonoid(5, 'a').gens() sage: x = a[0] * a[1] * a[4]**3 sage: y = a[4] * a[0] * a[1] sage: x*y a0*a1*a4^4*a0*a1 """ else: else:
def __len__(self): """ Return the degree of the monoid element ``self``, where each generator of the free monoid is given degree `1`.
For example, the length of the identity is `0`, and the length of `x_0^2x_1` is `3`.
EXAMPLES::
sage: F = FreeMonoid(3, 'a') sage: z = F(1) sage: len(z) 0 sage: a = F.gens() sage: len(a[0]**2 * a[1]) 3 """
def __cmp__(self,y): ## """ ## The comparison operator, defined via x = self: ## x < y <=> x.__cmp__(y) == -1 ## x == y <=> x.__cmp__(y) == 0 ## x > y <=> x.__cmp__(y) == 1 ## It is not possible to use __cmp__ to define a ## non-totally ordered poset. ## Question: How can the operators <, >, ==, !=, ## <=, and >= be defined for a general poset? ## N.B. An equal operator __equal__ may or may not ## have been introduced to define == and != but can ## not be used in conjunction with __cmp__. ## """ #raise TypeError, "Argument y (= %s) is of the wrong type."%y return 1 # x_elt is longer so compare next index else: # y_elt is longer so compare next index else:
def _acted_upon_(self, x, self_on_left): """ Currently, returns the action of the integer 1 on this element.
EXAMPLES::
sage: M.<x,y,z>=FreeMonoid(3) sage: 1*x x """ return None
def to_word(self, alph=None): """ Return ``self`` as a word.
INPUT:
- ``alph`` -- (optional) the alphabet which the result should be specified in
EXAMPLES::
sage: M.<x,y,z> = FreeMonoid(3) sage: a = x * x * y * x sage: w = a.to_word(); w word: xxyx sage: w.to_monoid_element() == a True
.. SEEALSO::
:meth:`to_list` """
def to_list(self, indices=False): """ Return ``self`` as a list of generators.
If ``self`` equals `x_{i_1} x_{i_2} \cdots x_{i_n}`, with `x_{i_1}, x_{i_2}, \ldots, x_{i_n}` being some of the generators of the free monoid, then this method returns the list `[x_{i_1}, x_{i_2}, \ldots, x_{i_n}]`.
If the optional argument ``indices`` is set to ``True``, then the list `[i_1, i_2, \ldots, i_n]` is returned instead.
EXAMPLES::
sage: M.<x,y,z> = FreeMonoid(3) sage: a = x * x * y * x sage: w = a.to_list(); w [x, x, y, x] sage: M.prod(w) == a True sage: w = a.to_list(indices=True); w [0, 0, 1, 0] sage: a = M.one() sage: a.to_list() []
.. SEEALSO::
:meth:`to_word` """
|