%
% file:         userguide.tex
% created:      pasha jan 15-16,29 from OCR of the ancient (version 3.0) userguide.pdf
% modified:     pasha feb 12 2023
% modification: minor English fix
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt,a4paper,oneside]{amsart}
%\input{pasha-inc.tex}
\usepackage[a4paper]{geometry}
\geometry{hmargin=1.8cm,top=2cm,bottom=2.5cm}

\usepackage{fouriernc}
\usepackage{enumerate,fancyvrb,perpage,supertabular}
\usepackage[colorlinks=false]{hyperref}

\pagestyle{plain}

\def\thefootnote{\fnsymbol{footnote}}
\MakePerPage[2]{footnote}

\DeclareMathOperator{\GF}{\mathsf{GF}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\begin{center}
{\Huge
Albert User's Guide
} 

\vskip 1cm

Written on February 7, 1996 for Albert version 3.0 by
\\ 
David Pokrass Jacobs, Sekhar V. Muddana, A. Jefferson Offutt, Kurti Prabhu, 
David Lee,
\\
Trent Whiteley 
\\
(Department of Computer Science, Clemson University)

\bigskip

In 2019 (last minor revision February 12, 2023) adapted for Albert version 
4.0M7, and merged with former online help by \\
Pasha Zusmanovich
\\
\texttt{pasha.zusmanovich@gmail.com}
\end{center}

\bigskip


\section{Introduction}

Albert is an interactive research tool to assist the specialist in the study of
nonassociative algebras. This document serves as a technical guide to Albert. We
refer the reader to \cite{jmo} for a more casual tutorial\footnote{
Valid for version 3.0, largely valid for the current version.
}. 
The main problem addressed by Albert is the recognition of polynomial 
identities. Roughly, Albert works in the following way. Suppose a user wishes to
study alternative algebras. These are algebras defined by the two polynomial 
identities $(yx)x- y(xx)$ and $(xx)y- x(xy)$, known respectively as the right 
and left alternative laws. In particular, the user wishes to know if, in the 
presence of the right and left alternative laws, $(a,b,c) \circ [a,b]$ is also 
an identity. Here $(a,b,c)$ denotes $(ab)c - a(bc)$, $[a,b]$ denotes $ab - ba$,
and $x \circ y$ denotes $xy + yx$. The user first supplies Albert with the right
and left alternative laws, using the \textbf{identity} command. Next, the user 
supplies the \emph{problem type}. This refers to the number and degree of 
letters in the target polynomial. For example, in this problem, each term of the
target polynomial has two $a$'s, two $b$', and one $c$, and so the problem type
is $2a2b1c$. This is entered using the \textbf{generators} command. It may be 
that over certain fields of scalars the polynomial is an identity, but over 
others it is not an identity. Albert allows the user to supply the field of 
scalars, but currently the user must select either a Galois field $\GF(p)$ in 
which $p$ is a prime less than $2^{63} - 1$, or the field of rational numbers 
$\mathbb Q$\footnote{
With a little programming effort, Albert can use any field as long as it has a 
computer implementation with a C/C++ interface.
}.
This is done using the \textbf{field} command. If no field is entered, the 
default field $\GF(251)$ is chosen. 

In deciding whether a given polynomial is an identity or not, Albert internally
constructs a certain homomorphic image of the free algebra. It is not necessary
that the user understand the theory of free algebras, nor is it necessary to 
understand the algorithms Albert employs to create them (which are described in
\cite{hj}). The user need only be aware that Albert builds a multiplication 
table for this free algebra. The user instructs Albert to begin the construction
using the \textbf{build} command. Once this construction has been completed, the user can query whether the 
polynomial $(a,b,c) \circ [a,b]$ is an identity using the \textbf{polynomial} 
command. In fact, the user can ask Albert about any homogeneous polynomial 
$p(a,b,c)$ having most two $a$'s, two $b$'s and one $c$ in each term. For 
example, the polynomial $(a,b,(a,b,c)) + [b,a](a,b,c)$ could also be tested. 
With Albert, polynomials and identities may be entered from the keyboard 
using associators, commutators, and much of the familiar notation used in 
nonassociative ring theory. Since the standard keyboard does not have the symbol
$\circ$, we use $*$ to denote the Jordan product. See the section entitled 
\emph{Polynomial Expression Language} for a complete description of how 
polynomials and identities can be entered in Albert. 

Albert has a small set of commands, and meaningful research can be conducted 
using only the \textbf{identity}, \textbf{generators}, \textbf{build}, and \textbf{polynomial}
commands. These commands, and others, are described in detail in this guide. The
user who wishes to quickly learn the system is advised to first try these 
commands. Thus, the typical user supplies Albert with the following input: 
\begin{itemize}
\item A set $I$ of polynomials whose members are assumed to be identities.
\item A problem type as described above. 
\item A field $F$ of scalars.
\end{itemize}

In this document ``polynomial'' always means a nonassociative polynomial. These
objects together implicitly define a fourth object, namely the free 
nonassociative algebra. In this document we refer to these four objects 
collectively as a \emph{configuration}. Various commands may alter or delete 
certain objects of a configuration. Typically, Albert spends much of its time 
constructing a multiplication table. But once a table has been constructed, 
Albert can quickly decide if a polynomial or group of polynomials are 
identities.

\emph{All polynomials and defining identities must be homogeneous}. That is, 
each must be expressible as a linear combination of words each having the same 
degree in each variable. This restriction is not very severe, since any 
nonhomogeneous polynomial can be replaced by its homogeneous parts. This 
replacement will not affect the results given a sufficiently high 
characteristic for the field. Albert internally linearizes any defining identity
that is not multilinear. Thus the right alternative identity is always 
interpreted as $(yx)z - y(xz) + (yz)x - y(zx)$. 

However, if a defining identity is not multilinear, the user is advised 
\emph{not} to linearize it before entering it, but rather enter it in its 
non-multilinear form. In most cases, this allows Albert to treat it more 
efficiently, since the identity's symmetry can be exploited. In general, the 
larger the degree of the problem type, the more memory Albert requires. Given 
two problems involving the same degree and the same defining identities, Albert
will cope best with the one having fewer letters. The defining identities 
influence the problem, too. Defining identities such as the commutative law (as
in the case of Jordan algebras) and the anticommutative law ``drive down'' the 
dimension of the free algebra, thus enabling larger problems to be solved than 
might otherwise be possible. If Albert is unable to complete a problem having 
degree $n$, adding additional identities of degree less than $n$ may allow 
Albert to finish. 

The program owes its name to A.A. Albert whose work was pioneering in 
nonassociative ring theory. It was designed and implemented at Clemson 
University by David P. Jacobs, Sekhar Muddana, and Jeff Offutt. Kurti Prabhu 
also helped during the early design. Subsequent features have been implemented 
by David Lee and Trent Whiteley. The idea of constructing free nonassociative algebras was motivated by
several papers of E. Kleinfeld. Irvin Hentzel has also assisted in the program's
development through helpful discussions.

Finally, a word of caution. Like any program, the possibility is high for 
errors. Please report any suspected bugs or general comments.




\section{Command Language}

The commands available with Albert are: \textbf{identity}, \textbf{remove}, 
\textbf{generators}, \textbf{field}, \textbf{build}, \textbf{display}, 
\textbf{polynomial}, \textbf{xpand}, \textbf{type}, \textbf{view}, 
\textbf{save}, \textbf{quit}.
 
Each command begins with a keyword, and the user can use any initial substring
of the keyword. For example, the \textbf{identity} command can be used by typing
\textbf{i}, \textbf{id}, etc. Every command is terminated by a carriage return.
Some commands (e.g. \textbf{identity}, \textbf{polynomial}) require a polynomial
as an argument. This polynomial may at times exceed the screen-width. In such 
cases, the user can continue on the next line by terminating the preceding line
with a backslash ($\backslash$).

 
\subsection{identity command}
$$
\texttt{identity} \quad polynomial
$$

Examples:
\begin{center}
\begin{BVerbatim}
identity (x,x,[y,x])
i (x,(x,(x,y,x),x),x)
\end{BVerbatim}
\end{center}
 
This command appends the polynomial to the current set of identities. Albert 
assigns a unique number to the entered identity for future use. Entering a new 
identity destroys any existing multiplication table in memory. 

\begin{itemize}
\item
Arguments: \emph{polynomial} as described in the section 
\emph{Polynomial Expression Language}. Names defined in the configuration file
(see the section \emph{Configuration file}) can also be used to enter a polynomial. The entered polynomial must be 
homogeneous. 
\item
Errors: malformed or non-homogeneous polynomial.
\end{itemize}

 

\subsection{remove command}
$$
\texttt{remove} \quad number|*
$$

This command removes one or more identities from the current set of identities.
For example,
$$
\texttt{remove 2}
$$
would remove the identity whose number is $2$. The remaining identities are 
renumbered after deletion of the identity. An asterisk ($*$) can be used in 
place of \emph{number} to remove all existing identities:
$$ 
\texttt{r *}
$$

The \textbf{remove} command will destroy a resident multiplication table, if 
present. 

\begin{itemize}
\item Arguments: the number of the identity, or $*$
\item Errors: invalid number. 
\end{itemize}



\subsection{generators command}
$$
\texttt{generators} \quad \textit{problem\_type}
$$

Before beginning the construction of an algebra, Albert must know what the 
generators will be, and the degrees of the generators. This information is 
referred to as the problem type, and the generators command is used to define 
it. This problem type is stored in the current configuration. Entering a new 
problem type destroys any existing problem type and any multiplication table, if
present. For example, 
\begin{center}
\begin{BVerbatim}
generators aabcc 
gen aabcc 
g 2ab2c 
\end{BVerbatim}
\end{center}

\begin{itemize}
\item 
Arguments: \emph{problem\_type} is a string of lower-case letters indicating the 
generators and degrees used in the problem. For example, \texttt{aabcc} 
indicates that the algebra to be built will be generated by $a$, $b$, and $c$, 
and will be spanned by words in these letters having at most two $a$'s, one $b$,
and two $c$'s. This word must have degree at least two. This can also be entered
in abbreviated form as \texttt{2a1b2c}, \texttt{2ab2c}, \texttt{b2a2c}, etc. 
\end{itemize}



\subsection{field command}
$$
\texttt{field} \quad number|\texttt{Q}
$$
 
This command changes the field of scalars, and this information is stored as 
part of the current configuration. When the field is changed, any resident 
multiplication table is destroyed. For example, 
$$
\texttt{field 17}
$$
will cause subsequent algebras to be constructed over the field $\GF(17)$. When
Albert is first entered, the default field $\GF(251)$ is selected. This field 
remains in effect until the field is changed. 

\begin{itemize}
\item
Arguments: \emph{number} must be a prime $p$ less than $2^{63} - 1$, in which 
case the field is changed to $\GF(p)$; if Q is specified, the field is changed to 
$\mathbb Q$.
\item
Errors: \emph{number} out of range or not prime. 
\end{itemize}




\subsection{build command}
$$
\texttt{build}
$$

This command invokes Albert to begin construction of the algebra defined by the
current configuration. Albert constructs the algebra using the current set of 
identities, problem type, and field stored in the current configuration. Status 
information is printed during the construction. An old multiplication table is 
destroyed. 

\begin{itemize}
\item Arguments: none. 
\item Errors: problem type not defined, or memory overflow during the 
construction.
\end{itemize}
 



\subsection{display command}
$$
\texttt{display}
$$

Typing \texttt{display} causes Albert to display the current set of defining 
identities, field, problem type, and information about the multiplication table,
if present. 




\subsection{polynomial command}
$$
\texttt{polynomial} \quad polynomial
$$

After a multiplication table has been constructed using \textbf{build}, this 
command may be used to test whether the given polynomial is zero in the resident
algebra. For example, typing 
$$
\texttt{p 2((ba)a)a + ((aa)a)b - 3((aa)b)a}
$$
might cause Albert to respond with: 
$$
\texttt{Polynomial is not an identity.}
$$

\begin{itemize}
\item Arguments: \emph{polynomial} has to be homogeneous. 
\item
Errors: invalid or non-homogeneous polynomial, nonexistent table, polynomial 
incompatible with current problem type. 
\end{itemize}




\subsection{xpand command}
$$
\texttt{xpand} \quad polynomial
$$

This command is used to see the expanded form of a nonassociative polynomial. 
For example, typing 
$$
\texttt{xpand (x,y,z)}
$$
would cause Albert to respond with:
$$ 
\texttt{(xy)z - x(yz)}
$$

The command is used for information purposes only and does not affect the 
current configuration. 

\begin{itemize}
\item Arguments: \emph{polynomial} has to be homogeneous.
\item Errors: invalid or non-homogeneous polynomial. 
\end{itemize}




\subsection{type command}
$$
\texttt{type} \quad word
$$

Every nonassociative word has a particular association type. These association 
types are numbered by Albert. For example, the association type of the word 
$((ab)c)d$ is $1$, while the association type of the word $(ab)(cd)$ is 3. Thus,
typing 
$$
\texttt{t (ab)(cd)}
$$ 
would cause Albert to respond with:
$$
\texttt{The association type of the word = 3.}
$$ 

This command prints the number of the association of the argument. Usually this
is not important, unless the user wishes to use the $W$ (artificial word) 
operator (see the section \emph{Polynomial Expression Language}). 

\begin{itemize}
\item 
Arguments: nonassociative \emph{word} like $a((ac)b)$. The letters and their 
order are not important.
\item Errors: invalid \emph{word}. 
\end{itemize}





\subsection{view command}
$$
\texttt{view b|m [gap]}
$$

This command prints the basis table or the multiplication table to the screen, 
provided they exist. The first argument specifies the table to be output 
(\texttt{b} -- basis table, \texttt{m} -- multiplication table). For example, 
typing
$$
\texttt{view b}
$$
will output the current basis table to the screen. 

If the first argument is $\texttt{m}$, and the second, optional, argument is 
specified, the multiplication table will be printed in the GAP format rather 
than in a human-readable format. For example, loading the output of the command
$$
\texttt{view m gap}
$$
to GAP will recreate the algebra constructed by Albert as a GAP object.

\begin{itemize}
\item Arguments: first -- \texttt{b} or \texttt{m}, second (optional) -- 
\texttt{gap}.
\end{itemize}





\subsection{save command}
$$
\texttt{save b|m [gap]}
$$

This command saves the basis table or the multiplication table to a file, 
provided the table already exist. After typing the \textbf{save} command, the 
user will receive the following prompt:
\medskip
\begin{verbatim}
File Name -->
\end{verbatim}
\medskip

The user may enter a directory path along with the file name. If a file name is
entered, it will be written to the current directory. The arguments have the 
same meaning as for the \textbf{view} command. For example, typing
\medskip
\begin{verbatim}
save m
File Name --> Mult.table
\end{verbatim}
\medskip
will cause the multiplication table to be written to \texttt{Mult.table} in the
current directory.

\begin{itemize}
\item Arguments: first -- \texttt{b} or \texttt{m}, second (optional) -- 
\texttt{gap}.
\end{itemize}




\subsection{quit command}
$$
\texttt{quit}
$$

This command exits the user from Albert. Any multiplication table or other 
information is lost.




\subsection{Summary of commands}

\begin{flushleft}
\bigskip
\begin{tabular}{|l|l|}
\hline
\texttt{identity} \textit{polynomial} & enter a defining identity \\ 
\hline
\texttt{remove} \textit{number}|$*$ & remove a defining identity \\ 
\hline 
\texttt{generators} \textit{word} & specify the problem type   \\ 
\hline
\texttt{field} \textit{number}|\texttt{Q} & change the current field of scalars \\ 
\hline
\texttt{build} & build a multiplication table \\ 
\hline
\texttt{display} & display the current configuration \\ 
\hline
\texttt{polynomial} \textit{polynomial} & query if the polynomial is an identity 
\\ 
\hline
\texttt{xpand} \textit{polynomial} & expand the polynomial \\ 
\hline
\texttt{type} \textit{word} & determine the association type \\
\hline 
\texttt{view b|m [gap]} & view basis or multiplication table \\
\hline
\texttt{save b|m [gap]} & save basis or multiplication table \\
\hline
\texttt{quit} & quit from Albert \\
\hline 
\end{tabular}
\bigskip
\end{flushleft}





\section{Basis table and multiplication table}

There are two important structures created by the \textbf{build} command. These
are the basis table and the multiplication table. These tables can be seen using
\textbf{view}, or stored using \textbf{save}. The basis table contains a list of
elements that form a basis in the free algebra that was constructed. Under 
Albert's method, basis elements will always be words in the original generators.
Shown below is the basis table for the $26$-dimensional right alternative 
algebra using $2a$'s and $2b$'s. There are five columns. The first of these is simply 
the number by which the basis element is referred. The second and third columns 
indicate how the basis element factors into a product of two lower degree basis
elements. The fourth columns indicates the type (degrees in each generator) of the element. The fifth 
column shows the basis element as a nonassociative word. For example, the table indicates 
that basis element $\#25$ is the product of element $\#13$ and element $\#2$. It
also indicates that this element has type $22$ (2 $a$'s and $2$ $b$'s), and 
shows the element as $(((ab)a)b)$. Obviously, the element's type is inherent in
the last columns, however this column should make it easier to take a large table and pick out all elements of a certain type. 

\begin{verbatim}
Basis Table: 
1. 0 0 10 a 
2. 0 0 01 b 
3. 2 2 02 (bb) 
4. 2 1 11 (ba) 
5. 1 2 11 (ab) 
6. 1 1 20 (aa) 
7. 2 5 12 (b(ab)) 
8. 3 1 12 ((bb)a) 
9. 4 2 12 ((ba)b) 
1O. 5 2 12 ((ab)b) 
11. 1 5 21 (a(ab)) 
12. 4 1 21 ((ba)a) 
13. 5 1 21 ((ab)a) 
14. 6 2 21 ((aa)b) 
15. 1 10 22 (a((ab)b)) 
16. 2 14 22 (b((aa)b)) 
17. 4 5 22 ((ba)(ab)) 
18. 5 5 22 ((ab)(ab)) 
19. 7 1 22 ((b(ab))a) 
20. 8 1 22 (((bb)a)a) 
21. 9 1 22 (((ba)b)a) 
22. 10 1 22 (((ab)b)a) 
23. 11 2 22 ((a(ab))b) 
24. 12 2 22 (((ba)a)b) 
25. 13 2 22 (((ab)a)b) 
26. 14 2 22 (((aa)b)b) 
\end{verbatim}

A portion of the multiplication table for the same algebra is shown below. The 
table lists only the nonzero products of two basis elements. Coefficients are 
given in terms of the current field. Assuming the default field $\GF(251)$ were
in use, the table below can be interpreted as 
\begin{align*}
b_1 b_1 &= b_6                       \\
b_1 b_2 &= b_5                       \\  
b_1 b_3 &= b_{10}                    \\
b_1 b_4 &= -b_{11} + b_{13} + b_{14} \\
b_1 b_5 &= b_{11}                    \\
b_1 b_7 &= -b_{15} + b_{18} + b_{23} \\
b_1 b_8 &= -b_{15} + b_{22} + b_{26} \\
b_1 b_9 &= b_{25}
\end{align*}

Had we shown the entire multiplication table, we would have seen that 
$b_{13} b_2 = b_{25}$. Hence $b_25$ factors as $b_1 b_9$ and $b_{13} b_2$. This 
merely says that $a((ba)b) = ((ab)a)b$ in a right alternative ring. Recall that
when Albert constructs an algebra in, say, $2a$'s and $2b$'s, products involving
more than $2a$'s or more than $2b$'s will be zero. Other kinds of products, too,
can be zero. 

\begin{verbatim}
Multiplication table: 
(b1)*(b1) 
    1 b6 
(b1)*(b2) 
    1 b5 
(b1)*(b3) 
    1 b10 
(b1)*(b4) 
    250 b11 + 1 b13 + 1 b14 
(b1)*(b5) 
    1 b11
(b1)*(b7) 
    250 b15 + 1 b18 + 1 b23 
(b1)*(b7) 
    250 b15 + 1 b22 + 1 b26 
(b1)*(b9) 
    1 b25 
\end{verbatim}




\section{The configuration file}

The configuration file contains definitions for making it easier to enter 
identities. This file can be edited by the user outside of Albert. Arbitrarily 
many definitions can be given. Long definitions can be continued on another line
by placing a backslash ($\backslash$) at the end of the line. The file can 
include blank lines. Comments begin with \% and extend to the end of a line. A 
typical configuration file might look like this:
\medskip
\begin{verbatim}
rightalt   (x,y,y)              % Right alternative law. 
jordan     ((xx)y)x - (xx)(yx) 
com        [x,y]
doublecom  [[x,y],z]
 
% A strange new identity: 
ident3     (x,[x,y],x) 
\end{verbatim}
\medskip

When Albert is initialized, the configuration file, is specified, is read into 
memory. Definitions occurring within this file can be used in subsequent 
commands, by surrounding the defined entity with \$'s. For example, one now could enter the command: 
$$
\texttt{identity \$jordan\$ - \$ident3\$}
$$

The identity is interpreted as $((xx)y)x - (xx)(yx) - (x,[x,y],x)$. The 
configuration file can make use of definitions occurring elsewhere in the 
file. Moreover, a definition need not occur before its use. For example, one 
might have 
\medskip
\begin{verbatim}
RightAlt       (x,y,y)          % Right alternative law. 
RightAltCom    [w, $RightAlt$]  % Right alternators commute.
\end{verbatim}
\medskip 

This last identity is interpreted as $[w,(x,y,y)]$. Circular definitions will 
cause great problems. 




\section{Invoking Albert}

Albert is invoked on the command line by giving its name followed by one 
optional argument:
\begin{align*}
&\texttt{albert [-f} \quad \textit{filename}\texttt{]} \\
&\texttt{albert -h}
\end{align*}

Here \textit{filename} refers to the (relative of absolute) location of a 
configuration file. For example:
$$
\texttt{albert -f .albert}
$$

If no options are specified, no configuration file will be used. If invoked with
\texttt{-h} option, Albert prints a short help message and quits.




\section{Sample Scenario}

The following example illustrates interaction with Albert. Text appearing after
the \verb|-->| prompt has been printed by the user; all other text has been 
typed by the Albert system. 

\begin{verbatim}
[pasha@max-und-moritz] tmp--> albert -f /usr/local/albert/4.0M6/.albert
Albert version 4.0M6, 2019

Using /usr/local/albert/4.0M6/.albert

-->identity (x,x,y) 

     (xx)y - x(xy) 
Entered as identity 1. 

-->identity (x,y,y) 
    (xy)y - x(yy) 
Entered as identity 2. 

-->generators 2a2blc 

Problem type stored. 

-->display 

Defining identities are: 
1. (x,x,y) 
2. (x,y,y) 
Ground field is GF(251)
Problem type = [2a,2b,c]; Total degree = 5. 
Multiplication table not present. 
-->build 

Building the Multiplication Table.

Build begun at Tue Jan 15 21:55:20 2019

Degree    Current Dimension   Elapsed Time(in seconds)
   1                 3                 0
   2                11                 0
   3                30                 0
   4                64                 0
   5                99                 0
Build completed.
Last Matrix 20.6% dense.

-->v m gap

T := EmptySCTable (99, Zero(GF(251)));
SetEntrySCTable (T, 1, 1, [1, 11]);
SetEntrySCTable (T, 1, 2, [1, 10]);
SetEntrySCTable (T, 1, 3, [1, 8]);
SetEntrySCTable (T, 1, 4, [250, 15, 1, 18, 1, 19]);
\end{verbatim}

\medskip
... (long output suppressed) ...
\medskip

\begin{verbatim}
SetEntrySCTable (T, 64, 3, [1, 99]);
A := AlgebraByStructureConstants (GF(251), T);

-->polynomial (a,b,c)*[a,b] 

Polynomial is an identity. 

-->polynomial (a,b,(a,b,c)) + [b,a](a,b,c)
 
Polynomial is an identity. 

-->polynomial [a,[b,(a,b,c)]]

Polynomial is not an identity. 

-->remove 1

Identity 1 removed. 
Destroyed the Multiplication Table. 

-->generators 4a2b 

Problem type changed. 

-->display 
Defining identities are: 
1. (x,y,y) 
Ground field is GF(251)
Problem type = [4a,2b]; Total degree = 6. 
Multiplication table not present. 
-->build 

Building the Multiplication Table.

Build begun at Tue Jan 15 21:58:25 2019

Degree    Current Dimension   Elapsed Time(in seconds)
   1                 2                 0
   2                 6                 0
   3                15                 0
   4                35                 0
   5                77                 0
   6               146                 0
Build completed.
Last Matrix 7.8% dense.

-->poly (a,a,b)^2 

Polynomial is not an identity. 

-->poly (a,a,b)^3 

Polynomial type not a subtype of Target_type. 

-->quit 
\end{verbatim}

\bigskip

For further examples, and for illustration of a methodology for using Albert, 
see \cite{hj2}, \cite{hjk}, \cite{hjm}, \cite{jacobs}, \cite{albert}, \cite{hp},
\cite{hp2}, \cite{alternative}, and \cite{mock-lie}.





\section{Polynomial Expression Language}

The \textbf{identity}, \textbf{polynomial}, and \textbf{xpand} commands require
a nonassociative polynomial to be entered. This section describes the proper 
syntax of nonassociative polynomials. In Appendix A, a formal grammar is given.
Nonassociative polynomials are described using the following operators. 

\medskip

\begin{itemize}
\setlength{\itemsep}{5pt}

\item
addition: $x + y$. 

\item
subtraction: $x - y$. 

\item
unary minus: $-x$. 

\item
scalar product: $3x$. The scalar is interpreted to be from the ring of integers.
 
\item
juxtaposed product: $xy$.
 
\item
commutator: $[x,y] = xy - yx$.
 
\item
associator: $(x, y, z) = (xy)z - x(yz)$.
 
\item
Jordan product: $x*y = xy + yx$.
 
\item
Jordan associator: $<x,y,z> = (x*y)*z - x*(y*z)$.
 
\item
Jacobi: $J(x,y,z) = (xy)z + (yz)x + (zx)y$.
 
\item
left associated exponential: $x^3 = (xx)x$. Warning: $xy^3$ means 
$((xy)(xy))(xy)$ not $x((yy)y)$.
 
\item
left/right multiplication: the general from of these expressions is 
$\{A y_1 y_2 \dots y_k\}$, where each $y_i$ is of the form $x`$ or $x'$. Here 
$A$ and $x$ can be more complicated expressions. $x`$ denotes left 
multiplication by $x$, and $x'$ denotes right multiplication. A sequence of such
operators are applied from left to right, and surrounded by braces. For example,
$\{xy`z'u'\}$ denotes $((yx)z)u$,  and $\{xy`z'u'(w(ts))`\}$ denotes 
$(w(ts))((yx)z)u$, and $\{xy'z'\} - \{zy`x`\}$ denotes $(xy)z - x(yz)$.

\item
artificial word: $W\{n;a:b:a:c:d\}$. Here $n$ is called an 
\emph{association type}. Often it is cumbersome to type in long parenthesized 
expressions. To simplify the typing, the artificial word construct can be used. $W\{n;a:b:a:c:d\}$ 
represents the word having letters $a,b,a,c,d$ and association type $n$. Albert
places a well-ordering on associations. If two associations $w_1$ and $w_2$ have
different degrees, then $w_1 < w_2$ if $w_1$ has smaller degree. Suppose $w_1$ 
and $w_2$ have the same degree. If this degree is $1$ or $2$, then $w_1 = w_2$.
But if 
\begin{align*}
w_1 &= (l_1)(r_1) \\
w_2 &= (l_2)(r_2)
\end{align*}
then $w_1 < w_2$ if either $r_1 < r_2$, or $r_1 = r_2$ and $l_l < l_2$. Thus, 
the smallest degree $n$ association type is 
$$
(\dots(((xx)x)x)x)\dots)x ,
$$
and the largest degree in association type is
$$
x(\dots(x(x(x(xx))))\dots) . 
$$

The degree $4$ association types, in order, are:
\begin{gather*}
((xx)x)x  \\
(x(xx))x  \\
(xx)(xx)  \\
x((xx)x)  \\
x(x(xx))
\end{gather*}
 
Thus $W\{4;a:a:c:b\}$ means $a((ac)b)$. Note that typing in a number $n$ that 
exceeds the number of degree $n$ association types is an error. The user can 
easily determine the number for an association using the \textbf{type} command 
described in the section \emph{Command Language}. 
\end{itemize}

The operators can be intermixed in any arbitrary fashion. For example, the 
following constructs are allowed:
\begin{gather*}
(x,[x,y],x)        \\
J(x,<x,y,z>,z)     \\
[x^3,(x,x*y,y)]
\end{gather*} 

All variables must be entered lower case letters. The order in which operators 
are applied, is controlled using parenthesis. Thus one may write $(x*y)*z$ or 
$x*(y*z)$. An ambiguous expression such as $x*y*z$ is illegal. Most expressions
have the same common meaning as they do in mathematics. For example, scalar 
multiplication and unary minus ($-$) have higher precedence over addition and 
subtraction, and therefore $3(a,b,c) + (c,b,a)$ means $(3(a,b,c)) + (c,b,a)$. 
However, there are some caveats. When used in the presence of {\textasciicircum}
or $*$, juxtaposition has higher precedence: $xy^3$ means $((xy)(xy))(xy)$ not 
$x(y^2y)$, and $xy * x$ means $(xy) * x$. 




\newpage
\section*{Appendix A: Formal Grammar}

\begin{supertabular}{lcl}
\textit{polynomial} & $\to$ & \textit{term}                 \\
                    & |     & $+$ \textit{term}             \\
                    & |     & $-$ \textit{term}             \\
                    & |     & \textit{polynomial} $+$ term  \\
                    & |     & \textit{polynomial} $-$ term  \\
                    &       &                               \\ 
\textit{term}       & $\to$ & \textit{product}              \\
                    & |     & \texttt{int} \textit{product} \\
                    &       &                               \\
\textit{product}    & $\to$ & \textit{atom\_or\_double\_atom}        \\ 
                    & |     & \textit{atom\_or\_double\_atom} $\uparrow$ \texttt{int} \\
                    & |     & \textit{atom\_or\_double\_atom} $*$ \textit{atom\_or\_double\_atom}                                           \\
                    &       &                               \\
\textit{atom\_or\_double\_atom} & $\to$ & \textit{atom}     \\
                    & |     & \textit{double\_atom}         \\
                    &       &                               \\
\textit{double\_atom} & $\to$ & \textit{atom atom}          \\
                    &       &                               \\
\textit{atom}       & $\to$ & \texttt{small\_letter}        \\ 
                    & |     & \textit{commutator}           \\
                    & |     & \textit{associator}           \\ 
                    & |     & \textit{jacobi}               \\
                    & |     & \textit{jordan\_associator}   \\
                    & |     & \textit{artificial\_word}     \\
                    & |     & \textit{operator\_product}    \\
                    & |     & ( \textit{polynomial} )       \\ 
                    &       &                               \\
\textit{commutator} & $\to$ & [ \textit{polynomial}, \textit{polynomial} ] \\ 
                    &       &                               \\
\textit{associator} & $\to$ & ( \textit{polynomial}, \textit{polynomial}, \textit{polynomial} )                                             \\
                    &       &                               \\
\textit{jacobi}     & $\to$ & J ( \textit{polynomial}, \textit{polynomial}, \textit{polynomial} )                                           \\
                    &       &                               \\
\textit{jordan\_associator} & $\to$ & < \textit{polynomial}, \textit{polynomial}, \textit{polynomial} >                                     \\
                    &       &                               \\
\textit{artifcial\_word} & $\to$ & W \{ \texttt{int}; \textit{letter\_list} \} 
                                                            \\
                    &       &                               \\
\textit{letter\_list} & $\to$ & \texttt{small\_letter}      \\
                    &  |    & \textit{letter\_list} : \texttt{small\_letter} \\
                    &       &                               \\
\textit{operator\_product} & $\to$ & \{ \textit{atom operator\_list} \} \\
                    &       &                               \\
\textit{operator\_list} & $\to$ & \textit{operator}         \\
                    & |     & \textit{operator\_list operator} \\
                    &       &                                \\
\textit{operator}   & $\to$ & \textit{atom}`                 \\
                    & |     & \textit{atom}'                 \\
                    &       &                                \\
\end{supertabular}

\texttt{int}: Positive. Sequence of digits not beginning with $0$. 





\begin{thebibliography}{HJPS}

\bibitem[DZ]{alternative} A. Dzhumadil'daev, P. Zusmanovich,
\emph{The alternative operad is not Koszul},
Experiment. Math. \textbf{20} (2011), no.~2, 138--144; 
Corrigendum: \textbf{21} (2012), no.~4, 418.

\bibitem[JMO]{jmo} D.P. Jacobs, S.V. Muddana, A.J. Offutt, 
\emph{A computer algebra system for nonassociative identities}, 
Hadronic Mechanics and Nonpotential Interactions, Part 1 (ed. H.C. Myung), 
Nova Sci. Publ., 1993, 185--195.

\bibitem[HJ1]{hj} I.R. Hentzel, D.P. Jacobs, 
\emph{A dynamic programming method for building free algebras}, 
Comput. Math. Appl. \textbf{22} (1991), no.12, 61--66. 

\bibitem[HJ2]{hj2} I.R. Hentzel, D.P. Jacobs,
\emph{A condition guaranteeing commutativity},
Intern. J. Algebra Comput. \textbf{2} (1992), no.3, 291--295.

\bibitem[HJK]{hjk} I.R. Hentzel, D.P. Jacobs, E. Kleinfeld,
\emph{Rings with $(a,b,c) = (a,c,b)$ and $(a,[b,c],d) = 0$: a case study using 
Albert},
Intern. J. Comp. Math. \textbf{49} (1993), no.1-2, 19--27.

\bibitem[HJM]{hjm} I.R. Hentzel, D.P. Jacobs, S.V. Muddana,
\emph{Experimenting with the identity $(xy)z = y(zx)$},
J. Symb. Comput. \textbf{16} (1993), no.3, 289-293; 
Erratum: \textbf{17} (1994), no.2, 213.

\bibitem[HJPS]{albert}
I.R. Hentzel, D.P. Jacobs, L.A. Peresi, S.R. Sverchkov,
\emph{Solvability of the ideal of all weight zero elements in Bernstein algebras},
Comm. Algebra \textbf{22} (1994), no.9, 3265--3275.

\bibitem[HP1]{hp} I.R. Hentzel, L.A. Peresi,
\emph{The nucleus of the free alternative algebra},
Experiment. Math. \textbf{15} (2006), no.4, 445--470.

\bibitem[HP2]{hp2} I.R. Hentzel, L.A. Peresi,
\emph{Nuclear elements of degree $6$ in the free alternative algebra},
Experiment. Math. \textbf{17} (2008), no.2, 245--255.

\bibitem[J]{jacobs} D.P. Jacobs, 
\emph{The Albert nonassociative algebra system: a progress report},
ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation, ACM, 1994, 41--44.

\bibitem[Z]{mock-lie} P. Zusmanovich,
\emph{Special and exceptional mock-Lie algebras}, 
Lin. Algebra Appl. \textbf{518} (2017), 79--96.

\end{thebibliography}

\end{document}
