Operations

Filter:

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

Arity: 1

Comments:

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

Arity: 1

Comments:

Bifix-freeness - $ L^b $

Arity: 1

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

Comments:

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 \}$

Comments:

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$.

Comments:

Complementation - $ \overline{L} $

Arity: 1

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

Comments:

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 \}$

Comments:

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\}$

Comments:

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$.

Comments:

Factor-freeness - $ L^\sqsubseteq $

Arity: 1

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

Comments:

Identity - $ L $

Arity: 1


Comments:

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 \}$

Comments:

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

Arity: 1

Comments:

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

Arity: 1

Comments:

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 \}$

Comments:

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

Arity: 1

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

Comments:

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$.

Comments:

Plus - $ L^{+} $

Arity: 1

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

Comments:

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\}$

Comments:

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$.

Comments:

Prefix-freeness - $ L^\le $

Arity: 1

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

Comments:

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$

Comments:

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 \}$.

Comments:

Reversal of Catenation - $ (L_1L_2)^R $

Arity: 2


Comments:

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

Arity: 2


Comments:

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

Arity: 2


Comments:

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

Arity: 1

Comments:

Right Ideal Generated - $ L\Sigma^* $

Arity: 1

Comments:

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 \}$

Comments:

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

Arity: 1

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

Comments:

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\}$

Comments:

Simulation - $ sim(L) $

Arity: 1

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

Comments:

Star - $ L^\star $

Arity: 1

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

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*} $$

Comments:

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

Arity: 2


Comments:

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

Arity: 2


Comments:

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

Arity: 1


Comments:

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

Arity: 2

Comments:

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$.

Comments:

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$.

Comments:

Suffix-freeness - $ L^\preceq $

Arity: 1

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

Comments:

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} $$

Comments:

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

Arity: 1

Comments:

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

Arity: 1

Comments:

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 \}$

Comments:

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$.

Comments:

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$

Comments:

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$.

Comments:

Unique Union - $ L_1 \buildrel\circ\over\cup L_2 $

Arity: 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$.

Comments: