A unifying approach to picture grammarsA preliminary version is [2]. Work partially supported by PRIN Project “Mathematical aspects and emerging applications of automata and formal languages”, ESF Programme Automata: from Mathematics to Applications (AutoMathA), and CNR RSTL Project 760 Grammatiche 2D per la descrizione di immagini.

Definition 1

Let $\Sigma$ be a finite alphabet. A two-dimensional array of elements of $\Sigma$ is a picture over $\Sigma$ . The set of all pictures over $\Sigma$ is $\Sigma^{++}$ . A picture language is a subset of $\Sigma^{++}$ .

For $h,k\geq 1$ , $\Sigma^{(h,k)}$ denotes the set of pictures of size $(h,k)$ (we will use the notation $|p|=(h,k),|p|_{row}=h,|p|_{col}=k$ ). # $\notin\Sigma$ is used when needed as a boundary symbol ; $\hat{p}$ refers to the bordered version of picture $p$ . That is, for $p\in\Sigma^{(h,k)}$ , it is

p=\begin{array}[]{ccc}p(1,1)&\ldots&p(1,k)\\ \vdots&\ddots&\vdots\\ p(h,1)&\ldots&p(h,k)\end{array}\;\;\;\;\;\hat{p}=\begin{array}[]{ccccc}\#&\#&% \ldots&\#&\#\\ \#&p(1,1)&\ldots&p(1,k)&\#\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ \#&p(h,1)&\ldots&p(h,k)&\#\\ \#&\#&\ldots&\#&\#\\ \end{array}

A pixel is an element $p(i,j)$ of $p$ . If all pixels are identical to $C\in\Sigma$ the picture is called $C$ - homogeneous or $C$ -picture.

Row and column concatenations are denoted $\ominus$ and $\obar$ , respectively. $p\ominus q$ is defined iff $p$ and $q$ have the same number of columns; the resulting picture is the vertical juxtaposition of $p$ over $q$ . $p^{k\ominus}$ is the vertical juxtaposition of $k$ copies of $p$ ; $p^{+\ominus}$ is the corresponding closure. $\obar,^{k\obar},^{+\obar}$ are the column analogous.

Definition 3.10 .

Let $(\alpha,\beta,\gamma)\in\mathbb{F}_{q}^{3}$ . We say that $(\alpha,\beta,\gamma)$ is singular if

\alpha^{2}+\beta^{2}+\gamma^{2}-\alpha\beta\gamma=4.

Let $l=\mathcal{O}rd(\alpha)$ , $m=\mathcal{O}rd(\beta)$ and $n=\mathcal{O}rd(\gamma)$ . We say that $(\alpha,\beta,\gamma)$ is small if at least two of $l,m,n$ are equal to $2$ or if $2\leq l,m,n\leq 5$ .

Definition 3 .

Let ${\mathcal{Z}}$ be the ${\mathbb{Q}}$ -algebra generated by convergent polyzêtas and let ${\mathcal{Z}}^{\prime}$ be the ⁵ ⁵ 5 Here, $\gamma$ stands for the Euler constant $\gamma=.5772156649015328606065120900824024310421593359399235988057672348848677\ldots$ ${\mathbb{Q}}[\gamma]$ -algebra generated by ${\mathcal{Z}}$ .

Definition 1

A rack is a set R with two binary operations, $\rhd$ and $\rhd^{-1}$ , that satisfy for all $x,y,z\in R$ :

(i)

$(x\rhd y)\rhd^{-1}y=x$ and $(x\rhd^{-1}y)\rhd y=x$ , and
(ii)

$(x\rhd y)\rhd z=(x\rhd z)\rhd(y\rhd z)$ .

Definition 3.4 .

Let $\gamma,\eta$ denote two polygons on $S$ . We say that $\eta$ is convergent relative to $\gamma$ if there are no stable partitions of $S$ compatible with both $\gamma$ and $\eta$ :

(3.2)

\chi(\gamma)\cap\chi(\eta)=\emptyset\ .

In other words, there exists no block of $\gamma$ having the same underlying set as a block of $\eta$ . If $\eta$ is a polygon on $S$ , then a block of $\eta$ is said to be a consecutive block if its underlying set corresponds to a block of the polygon with the standard cyclic order $\delta$ . The polygon $\eta$ is said to be convergent if it has no consecutive blocks at all, i.e., if it is convergent relative to $\delta$ . A polygon $\eta\in{\mathcal{P}}_{S\cup\{d\}}$ is said to be convergent if it has no chords partitioning $S\cup\{d\}$ into disjoint subsets $S_{1}\cup S_{2}$ such that $S_{1}$ is a consecutive subset of $S=\{1,\ldots,n\}$ .

Definition 2.2

( [ 18 ] ) An immersed surface in $(G,g[1])$ of the form:

(9)

\varphi(u,v)=\left(\begin{array}[]{cc}1&x(u)\\ 0&1\end{array}\right)\left(\begin{array}[]{cc}\sqrt{v}&0\\ 0&1/\sqrt{v}\end{array}\right)\left(\begin{array}[]{cc}\cos u&\sin u\\ -\sin u&\cos u\end{array}\right)

is called a conoid in $G$ .

Definition 5.1 .

( [ 52 ] ) A (left) PostLie algebra is a $\mathbb{R}$ -vector space $L$ with two bilinear operations $\circ$ and $[,]$ which satisfy the relations:

(59)

[x,y]=-[y,x],

(60)

[[x,y],z]+[[z,x],y]+[[y,z],x]=0,

(61)

z\circ(y\circ x)-y\circ(z\circ x)+(y\circ z)\circ x-(z\circ y)\circ x+[y,z]% \circ x=0,

(62)

z\circ[x,y]-[z\circ x,y]-[x,z\circ y]=0,

for all $x,y\in L$ . Eq. ( 59 ) and Eq. ( 60 ) mean that $L$ is a Lie algebra for the bracket $[,]$ , and we denote it by $(\mathfrak{G}(L),[,])$ . Moreover, we say that $(L,[,],\circ)$ is a PostLie algebra structure on $(\mathfrak{G}(L),[,])$ . On the other hand, it is straightforward to check that $L$ is also a Lie algebra for the operation:

(63)

\{x,y\}\equiv x\circ y-y\circ x+[x,y],\;\;\forall x,y\in L.

We shall denote it by $(\mathcal{G}(L),\{,\})$ and say that $(\mathcal{G}(L),\{,\})$ has a compatible PostLie algebra structure given by $(L,[,],\circ)$ . A homomorphism between two PostLie algebras is defined as a linear map between the two PostLie algebras that preserves the corresponding operations.

Definition 3.2 .

For a smooth embedding $\imath:M\hookrightarrow{\mathbb{R}}^{p+2}$ of a connected, closed, oriented $p$ -dimensional smooth manifold $M$ into ${\mathbb{R}}^{p+2}$ , we define the induced spin structure as:

\imath^{\sharp}(\varsigma^{p+2})=\imath^{*}(\sigma^{\perp}),

where $\sigma^{\perp}$ is as described above.

Definition 2

For $w\in\Sigma^{*}$ , the set of equivalent words is

{\rm eq}(w)=\{w^{\prime}:r(w)=r(w^{\prime})\}

For $L\subseteq\Sigma^{*}$ , the set of equivalent words is

{\rm eq}(L)=\{{\rm eq}(w):w\in L\}

Definition 4.2 (Lattice Coordinates) .

Let $z$ be any integer. The lattice coordinates of $z$ are the unique solutions $(r,c)$ to the equation

(\beta-\alpha)c-\alpha r=z,

(1)

for which $r$ and $c$ are integers and $0\leq r<\beta-\alpha$ . We call $r$ and $c$ the row and column of $z$ respectively.

Definition 2.3 .

A set $\mathcal{M}\subset\mathcal{T}_{\alpha}$ is said to be logically closed if and only if whenever $b\in\mathcal{M},\;c\in\mathcal{M}$ and

\vdash a=b\vee a=c

then $a\in\mathcal{M}$ also. A minimal logically closed set $\overline{\mathcal{M}}\subset\mathcal{T}_{\alpha}$ which includes an arbitrary set $\mathcal{M}\subset\mathcal{T}_{\alpha}$ is said to be its logical closure . If in addition, $\mathcal{N}\subset\mathcal{T}_{\alpha}$ and $\overline{\mathcal{M}}=\overline{\mathcal{N}}$ , we say the two sets $\mathcal{M}$ and $\mathcal{N}$ are logically equivalent and denote this relation as $\mathcal{M}\simeq\mathcal{N}$ .

Definition 1.2 .

[ 11 ] Let $\mathfrak{a}$ be an arbitrary Lie antialgebra.

(1) An LA-module of $\mathfrak{a}$ is a $\mathbb{Z}_{2}$ -graded vector space $V$ together with an even linear map $\rho:\mathfrak{a}\to\textup{End}(V),$ such that the direct sum $\mathfrak{a}\oplus{}V$ equipped with the product

(1.4)

(a+v)\cdot(b+w)=a\cdot{}b\,+\;\left(\rho(a)\,(w)+(-1)^{\bar{b}\bar{v}}\,\rho(b% )\,(v)\right),

where $a,b\in\mathfrak{a}$ and $v,w\in{}V$ are homogeneous elements, is again a Lie antialgebra.

(2) An LA-representation of $\mathfrak{a}$ is a $\mathbb{Z}_{2}$ -graded vector space $V$ together with an even linear map $\rho:\mathfrak{a}\to\textup{End}(V),$ such that

(1.5)

\rho(a\cdot b)=[\rho(a),\rho(b)]_{+},

for all elements $a,b$ in $\mathfrak{a}$ , and

(1.6)

\rho(x)\rho(y)=\rho(y)\rho(x),

for all even elements $x,y$ in $\mathfrak{a}_{0}$ .

Definition 5.1

A $2$ -cocycle (with values in $\mathbb{K}^{*}$ ) on ${\mathbb{Z}}^{n}$ is a map $c:{\mathbb{Z}}^{n}\times{\mathbb{Z}}^{n}\longrightarrow\mathbb{K}^{*}$ such that

c(s,t+u)c(t,u)=c(s,t)c(s+t,u)

for all $s,t,u\in{\mathbb{Z}}^{n}$ .

Definition 2.3 .

For every integer $n\geq 1$ let ‘ $\cdot$ ’ denote the Euclidean scalar product on ${{\mathbb{R}}}^{n}$ . We introduce the Heisenberg algebra ${\mathfrak{h}}_{2n+1}={{\mathbb{R}}}^{n}\times{{\mathbb{R}}}^{n}\times{{% \mathbb{R}}}$ with the bracket

[(q,p,t),(q^{\prime},p^{\prime},t^{\prime})]=[(0,0,p\cdot q^{\prime}-p^{\prime% }\cdot q)].

The Heisenberg group ${\mathbb{H}}_{2n+1}$ is just ${\mathfrak{h}}_{2n+1}$ thought of as a group with the multiplication $\ast$ defined by

X\ast Y=X+Y+\frac{1}{2}[X,Y].

The unit element is $0\in{\mathbb{H}}_{2n+1}$ and the inversion mapping given by $X^{-1}:=-X$ . ∎