## Operations

Filter:

All-Sided Ideal From Minimal Generator - $MinGen \shuffle \Sigma^\star$

Arity: 1

All-Sided Ideal Generated - $L\shuffle \Sigma^\star$

Arity: 1

Bifix-freeness - $L^b$

Arity: 1

$L^b = L^\le \cap L^\preceq$

Catenation - $L_1L_2$

Arity: 2

For words $x$ and $y$ over an alphabet $\Sigma$, the catenation of $x$ and $y$ is denoted by $xy$ and it is the word obtained by attaching $y$ to the end of $x$.

Catenation is associative and the length of the new word $xy$ is the sum of the length of $x$ and the length of $y$.

For a language $L_1$ and a language $L_2$ over an alphabet $\Sigma$, the catenation of $L_1$ and $L_2$ is denoted by $L_1L_2$ and is defined by $L_1L_2 = \{ xy\mid x \in L_1, y \in L_2 \}$

Closure - $_\unlhd L$

Arity: 1

Let $\unlhd$ be a partial order on $\Sigma^*$; the $\unlhd$-closure of a language $L$ is the language $_\unlhd L = \lbrace x \in \Sigma^\star \ |\ x \unlhd w$ for some $w \in L \rbrace$.

Complementation - $\overline{L}$

Arity: 1

$\overline{L}= \Sigma^\star\setminus L$

Cyclic Shift - $L^{CS}$

Arity: 1

The cyclic shift of a language $L$ is defined as $L^{CS} = \{vu \in \Sigma^\star \mid uv \in L \}$

Difference - $L_1 \setminus L_2$

Arity: 2

$L_1 \setminus L_2 = \{ x \in \Sigma^\star \mid x\in L_1 \text{ and } x \notin L_2\}$

Factor-closure - $_\sqsubseteq L$

Arity: 1

The factor-closure of a language $L$ is the language $_\sqsubseteq L = \lbrace x \in \Sigma^\star \ |\ x \sqsubseteq w$ for some $w \in L \rbrace$.

Note that $x \sqsubseteq w$ means that $x$ is a factor of $w$.

Factor-freeness - $L^\sqsubseteq$

Arity: 1

$L^\sqsubseteq = L - (\Sigma^+ L \Sigma^\star \cup \Sigma^\star L \Sigma^+)$

Identity - $L$

Arity: 1

Intersection - $L_1\cap L_2$

Arity: 2

The intersection between two languages $L_1$ and $L_2$ can be defined as follows:

$\{ x \in \Sigma^\star | x \in L_1$ and $x \in L_2 \}$

Left Ideal From Minimal Generator - $\Sigma^\star MinGen$

Arity: 1

Left Ideal Generated - $\Sigma^\star L$

Arity: 1

Left quotient - $L_1^{-1} L_2$

Arity: 2

Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. Then the left quotient of $L_2$ by $L_1$, denoted by $L_1^{-1} L_2$, is the language $\{ y\in \Sigma^\star \mid xy \in L_2$ and $x \in L_1 \}$

Left quotient by a word - $w^{-1}L$

Arity: 1

$w^{-1}L = \{ x\in \Sigma^\star \mid wx \in L\}$

Orthogonal Catenation - $L_1 \odot_\perp L_2$

Arity: 2

A language L is the orthogonal catenation of $L_1$ and $L_2$, and denoted by $L = L_1 \odot_\perp L_2$, if every word $w$ of $L$ can be obtained in just one way as a catenation of a word of $L_1$ and a word of $L_2$.

Plus - $L^{+}$

Arity: 1

$L^+ = L^\star \setminus \{\varepsilon\}$

Power - $L^i$

Arity: 1

Given a language $L$ and $i\geq 2$,

$L^i = \{ w_1\ldots w_i\mid w_j \in L \ , 1\leq j \leq i\}$

Prefix-closure - $_\le L$

Arity: 1

The prefix-closure of a language $L$ is the language $_\le L = \lbrace x \in \Sigma^* \ |\ x \le w$ for some $w \in L \rbrace$.

Note that $x \le w$ means that $x$ is a prefix of $w$.

Prefix-freeness - $L^\le$

Arity: 1

$L^\le = L - L\Sigma^+$

Proportional removals for identity relation - $\frac {1}{2} (L)$

Arity: 1

$\frac {1}{2} (L) = \lbrace x \in \Sigma^* \mid \exists y \in \Sigma^*$ with $\vert x \vert = \vert y \vert$ and $xy \in L \rbrace$

Reversal - $L^R$

Arity: 1

For a word $x$ over an alphabet $\Sigma$, the reversal of $x$ is denoted by $x^R$ and it is recursively defined by:

$\epsilon^R=\epsilon$, and $(ay)^R=y^Ra$ where $a\in \Sigma$ and $y\in \Sigma^\star$.

By definition, if $x = a_1\dots a_n$, where $n \ge 1$ and $a_1,\dots , a_n$ and are letters in $\Sigma$, the $x^R = a_n\dots a_1$.

For a language $L$ over an alphabet $\Sigma$, the reversal of $L$ is denoted by $L^R$ and is defined by $L^R = \{x^R \mid x \in L \}$.

Reversal of Catenation - $(L_1L_2)^R$

Arity: 2

Reversal of Intersection - $(L_1 \cap L_2)^R$

Arity: 2

Reversal of Union - $(L_1 \cup L_2)^R$

Arity: 2

Right Ideal From Minimal Generator - $MinGen\Sigma^*$

Arity: 1

Right Ideal Generated - $L\Sigma^*$

Arity: 1

Right quotient - $L_2L_1^{-1}$

Arity: 2

Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. Then the right quotient of $L_2$ by $L_1$, denoted by $L_2L_1^{-1}$, is the language $\{ x\in \Sigma^\star \mid xy \in L_2$ and $y \in L_1 \}$

Right quotient by a word - $L w^{-1}$

Arity: 1

$Lw^{-1} = \{ x \in \Sigma^\star \mid xw \in L\}$

Shuffle - $L_1 \shuffle L_2$

Arity: 2

The shuffle operation  of two words $w_1,w_2\in \Sigma^\star$ is
defined by

$w_1\shuffle w_2$=$\{u_1 v_1\ldots u_mv_m\mid u_i,v_i\in\Sigma^\star, i \in[1,m],$
$w_1=u_1\ldots u_m \text{ and } w_2=v_1\ldots v_m \}$

The shuffle of two languages is then defined by:

$L_1 \shuffle L_2 = \{ w_1 \shuffle w_2 \mid w_1\in L \text{ and }w_2\in L_2\}$

Simulation - $sim(L)$

Arity: 1

The  language of the operation $sim(L)$ is $L$, but  the model used to represent it is changed.

Star - $L^\star$

Arity: 1

The Kleene star ( also know as Kleene operator or Kleene closure) of a language $L$ can be defined as:

• $L^\star = \{x_1x_2...x_n \mid n \geq 0$ and $x_i \in L, 1 \leq i \leq n \}$

Given $A$ and $B$ languages, the following properties hold for the Kleene star operation.

$$\begin{eqnarray*} A^\star A^\star & = & A^\star \\ (A^\star )^\star & = & A^\star \\ (\{ \epsilon \} \cup A)^\star & = & A^\star \\ \{ \epsilon \} \cup AA^\star & = & A^\star \\ \{ \epsilon \} \cup A^\star A & = & A^\star \\ (A^\star B^\star )^\star & = & (A\cup B)^\star \\ A(BA)^\star & = & (AB)^\star A \\ (A^\star B)^\star A^\star & = & (A\cup B)^\star \\ \emptyset ^\star & = & \{ \epsilon \} \end{eqnarray*}$$

Star of Catenation - $(L_1 L_2)^\star$

Arity: 2

Star of Intersection - $(L_1 \cap L_2)^\star$

Arity: 2

Star of Reversal - $(L^R)^\star$

Arity: 1

Star of Union - $(L_1\cup L_2)^\star$

Arity: 2

Subword-closure - $_\Subset L$

Arity: 1

The subword-closure of a language $L$ is the language $_\Subset L = \lbrace x \in \Sigma^* \ |\ x \Subset w$ for some $w \in L \rbrace$.

Note that $x \Subset w$ means that $x$ is a subword of $w$.

Suffix-closure - $_\preceq L$

Arity: 1

The suffix-closure of a language $L$ is the language $_\preceq L = \lbrace x \in \Sigma^* \ |\ x \preceq w$ for some $w \in L \rbrace$.

Note that $x \preceq w$ means that $x$ is a suffix of $w$.

Suffix-freeness - $L^\preceq$

Arity: 1

$L^\preceq = L - \Sigma^+L$

Symmetric Difference - $L_1\oplus L_2$

Arity: 2

$$\begin{eqnarray} L_1 \oplus L_2 & =& \{x \mid (x\in L_1 \wedge x\notin L_2) \cap (x\in L_2 \wedge x\notin L_1)\} \\ &=& (L_1\cup L_2) \setminus (L_1\cap L_2) \end{eqnarray}$$

Two-Sided Ideal From Minimal Generator - $\Sigma^\star MinGen \Sigma^\star$

Arity: 1

Two-Sided Ideal Generated - $\Sigma^\star L \Sigma^\star$

Arity: 1

Union - $L_1\cup L_2$

Arity: 2

The union operation between two languages $L_1$ and $L_2$ can be defined as follows:

$\{ x \in \Sigma^\star | x \in L_1$ or $x \in L_2 \}$

Unique Catenation - $L_1 \circ L_2$

Arity: 2

Let $L_1$, $L_2$ be languages over $\Sigma$. By unique catenation of $L_1$ and $L_2$, denoted as $L_1 \circ L_2$, we understand the set

$L_1 \circ L_2 = \lbrace w\ |\ w = uv, u \in L_1, v \in L_2$, and this factorization is unique$\rbrace$.

Unique Square - $L^{\circ2}$

Arity: 1

Let $L$ be a language over $\Sigma$. By unique square of $L$, denoted as $L^{\circ2}$, we understand the set

$L^{\circ2} = L \circ L$

Unique Star - $L^\circ$

Arity: 1

Let $L$ be a language over $\Sigma$. By unique star of $L$, denoted as $L^\circ$, we understand the set

$L^\circ = \lbrace e \rbrace \cup \lbrace w\ |\ w = u1 ... un,\ n \in N,\ ui \in L \backslash \lbrace e \rbrace\ \forall 1 \le i \le n$; and this factorization is unique$\rbrace$.

Unique Union - $L_1 \buildrel\circ\over\cup L_2$
Let $L_1$, $L_2$ be languages over $\Sigma$. By unique union of $L_1$ and $L_2$, denoted as $L_1 \buildrel\circ\over\cup L_2$, we understand the set
$L_1 \buildrel\circ\over\cup L_2 = (L_1 \backslash L_2) \cup (L_2 \backslash L_1)$,
in other words, the symmetric difference of $L_1$ and $L_2$.