freegroup (version 1.1-0)

cycred: Cyclic reductions of a word

Description

Functionality to cyclically reduce words and detect conjugacy

Usage

is.cyclically_reduced(a)
is.cyclically_reduced2(a)
as.cyclically_reduced(a)
cyclically_reduce(a)
cyclically_reduce_tietze(p)
is.conjugate_single(u,v)
x %~% y
# S3 method for free
is.conjugate(x,y)
allconj(x)

Arguments

a,x,y

An object of class free

p,u,v

Integer vector corresponding to Tietze form of a word

Details

A free object is cyclically reduced iff every cyclic permutation of the word is reduced. A reduced word is cyclically reduced iff the first letter is not the inverse of the last one. A reduced word is cyclically reduced if the first and last symbol differ (irrespective of power) or, if identical, have powers of opposite sign. For example, abac and abca are cyclically reduced but abca^{-1} is not. Function is.cyclically_reduced() tests for this. Function is.cyclically_reduced2() gives identical output; it uses slicker but marginally slower R idiom.

Function as.cyclically_reduced() takes a vector of free objects and returns the elementwise cyclically reduced equivalents. Function cyclically_reduce() is a synonym with better (English) grammar.

The identity is cyclically reduced: it cannot be shortened by a combination of cyclic permutation followed by reduction. This ensures that is.cyclically_reduced(as.cyclically_reduced(x)) is always TRUE. Also, it is clear that the identity should be conjugate to itself.

Two words \(a,b\) are conjugate if there exists a \(x\) such that \(ax=xb\) (or equivalently \(a=x^{-1}bx\)). This is detected by function is.conjugate(). Functions is_conjugate_single() and cyclically_reduce_tietze() are lower-level helper functions.

Function allconj() returns all cyclically reduced words conjugate to its argument.

See Also

reduce

Examples

# NOT RUN {
 as.cyclically_reduced(abc(1:9) - abc(9:1))

 a <- rfree(1000,3)
 all(size(as.cyclically_reduced(a)) <= size(a))
 all(total(as.cyclically_reduced(a)) <= total(a))
 all(number(as.cyclically_reduced(a)) <= number(a))



 x <- rfree(1000,2)
 y <- as.free('ab')
 table(conjugate = (x%~%y), equal = (x==y))  # note zero at top right

 allconj(as.free('aaaaab'))
 allconj(sum(abc(seq_len(3))))



 x <- rfree(1,10,8,8)
 all(is.id(allconj(x) + allconj(-x)[shift(rev(seq_len(total(x))))]))



# }

Run the code above in your browser using DataCamp Workspace