Langage de Łukasiewicz

Pour un alphabet ${\displaystyle \Sigma =\{x_{0},x_{1},...,x_{m}\}}$, muni de la fonction de taille ${\displaystyle \delta (x_{i})=i-1}$. Intuitivement, la lettre ${\displaystyle x_{i}}$ est un opérateur d'arité ${\displaystyle i}$. Les mots de Łukasiewicz sont les mots ${\displaystyle w_{1}\dots w_{\ell }}$ où ${\displaystyle w_{j}}$ est une lettre de l'alphabet ${\displaystyle \Sigma }$ tel que :

Pour tout ${\displaystyle \ell '<\ell }$, ${\displaystyle \sum _{j=1}^{\ell '}\delta (w_{j})\geq 0}$ et ${\displaystyle \sum _{j=1}^{\ell }\delta (w_{j})=-1}$.

Par exemple, un mot comme +1+23 s'écrit ${\displaystyle x_{2}x_{0}x_{2}x_{0}x_{0}}$. Comme

${\displaystyle {\begin{array}{ll}\delta (x_{2})&=1\geq 0,\\\delta (x_{2}x_{0})&=1-1\geq 0,\\\delta (x_{2}x_{0}x_{2})&=1-1+1\geq 0,\\\delta (x_{2}x_{0}x_{2}x_{0})&=1-1+1-1\geq 0,\\\delta (x_{2}x_{0}x_{2}x_{0}x_{0})&=1-1+1-1-1=-1\end{array}}}$

le mot ${\displaystyle x_{2}x_{0}x_{2}x_{0}x_{0}}$ est un mot de Łukasiewicz.

Ces mots codent les arbres plans[1].

En théorie des langages, le langage de Łukasiewicz est engendré par une grammaire algébrique[2]. Commencons par l'exemple du langage de Łukasiewicz avec deux lettres : (${\displaystyle x_{0}}$ d'arité 0 et ${\displaystyle x_{2}}$ d'arité 2). Il est engendré par la grammaire formelle suivante :

${\displaystyle S\to x_{2}SS\mid x_{0}}$

On rencontre souvent l'écriture plus simple:

${\displaystyle S\to aSS\mid b}$,

avec ${\displaystyle a=x_{2}}$ et ${\displaystyle b=x_{0}}$. Plus généralement, la grammaire

${\displaystyle S\to x_{n}S^{n}\mid x_{n-1}S^{n-1}\mid \cdots \mid x_{2}S^{2}\mid x_{1}S\mid x_{0}}$

correspond au langage de Łukasiewicz donné plus haut où la lettre ${\displaystyle x_{i}}$ est un opérateur d'arité ${\displaystyle i}$. On peut aussi ne choisir qu'une partie des symboles ${\displaystyle x_{1},\ldots ,x_{n}}$, comme dans la première définition par grammaire où seulement ${\displaystyle x_{2}}$ et ${\displaystyle x_{0}}$ interviennent. On a alors la version la plus générale : soit ${\displaystyle I}$ un sous-ensemble non vide de ${\displaystyle \{1,\ldots ,n\}}$. Alors le langage est donné par la grammaire

${\displaystyle S\to \sum _{i\in I}x_{i}S^{i}\mid x_{0}}$.

Il y a un lien étroit entre le langage de Łukasiewicz et le langage de Dyck.