On Automatic Relations
In one of the previous posts we have gone through a concept of regular languages. These languages are quite convenient to work with and have a great deal of good properties, which might be the topic for another post. In this post I would like to focus on automatic relations. This notion tries to extend regularity from unary relation to $k$-ary relations. So instead of asking if $x\in L$ for a given regular language $L$, we ask $(x_1,x_2,\ldots,x_n)\in R$ for a some relation $R$.
Suppose $R\subseteq (\Sigma^*)^n$ be some $n$-ary relation. Our aim is to check a membership of the tuple $(x_1,x_2, \ldots, x_n)$ in $R$. For this we stack or \emph{convolute} these words, so that it might look like this in the case of $n=4$:
\[
\begin{bmatrix}
1 & 0 & 0 & 1 & 1\\
0 & 1 & 1 & & \\
1 & & & &\\
1 & 0 & 0 & &
\end{bmatrix}
\]
Observe that above block is nonuniform in length, so it cannot be generated by the tuples of the form $\Sigma^4$. To improve this situation, we append a special symbol, e.g. $\#$, to make the block uniform. So now the same block looks like:
\[
\begin{bmatrix}
1 & 0 & 0 & 1 & 1\\
0 & 1 & 1 & \# & \#\\
1 & \# & \# & \# & \#\\
1 & 0 & 0 & \# & \#
\end{bmatrix}
\]
These kinds of block form an input space of special kind of finite state machines known as multiple tape finite automata, which are going to be defined below:
Synchronous multi tape finite automata
Synchronous multi tape finite automata or synchronous automata for short read letters across rows one layer at a time or synchronously. A (deterministic) synchronous automaton $M=(Q,\Sigma, \delta, s_0, F)$ is similar to deterministic finite automata, except for the fact that $\delta:Q\times (\Sigma_{\#})^n \to Q$, where $\Sigma_{\#} = \Sigma \cup \#$. An synchronous finite automaton $M$ accepts a block $u$ if it ends at an accepting state when reading $u$. Let $L(M)$ be a collection of all blocks accepted by $M$. Then we say that $M$ recognizes a language $L(M)$. Here comes a main definition:
Automatic relation
A relation $R$ is said to be \emph{automatic} if there is a synchronous finite automaton $M$ recoginizing elements of $R$ written in the block form.
Having defined automatic relations, now we can define a notion of an automatic function.
Automatic function
Let $f$ be a function $f:(\Sigma^*)^n \to (\Sigma^*)^m$. We say that $f$ is an \emph{automatic function} if its graph $graph(f) = \{(x,f(x)):x\in (\Sigma^*)^n\}$ forms an automatic relation. Now we are ready to state famous result on the closure of automatic relations over first order logical definitions due to Nerode and Khoussainov:
Closure under first-order definition
Let a relation $R$ be first order definable from relations $(R_i)_{i=1}^n$ and functions $(f_j)_{j=1}^m$. If each of $R_i$ and $f_j$ happens to be automatic, then $R$ is automatic as well.
What are the examples of automatic relations? Let us give a few.
Length Comparison:
Let $R = \{(x,y):\vert x \vert < \vert y \vert \}$ be a pairs of words with the first word being strictly shorter. There is a multi-tape automaton recognizing this relation.
Lexicographic order:
Suppose we work with an alphabet $\Sigma = \{0,1 \}$. Suppose there is an initial order $0<1$. This order induces a lexicographic order in the collection of all words. To identify if $x<_{lex}y$ we compare corresponding symbols until they differ, and the word with $0$ symbol is set to be smaller. So, we have
$01111 \,<\, 10$
$0001 \,<\, 00100$
Again, one could construct a multitape automaton recognizing this relation.
Shortlex or length-lexicographic order:
The given order first compares lengths of two strings $x,y$ to identify a smaller element. If lengths are happened to be equal, then it uses lexicographic order to identify a smaller element. Observe that this relation can be defined by first order logical formula from previous relations:
\[
x<_{ll}y \Leftrightarrow \vert x \vert < \vert y \vert \text{ or }(\vert x \vert = \vert y \vert \text{ and }x<_{lex}y)
\]
By the first-order definability property, we have that length-lexicographic order is also automatic.
This seems to be all I want to say about automatic relations. Next times I hope to say something about finite automata recognizable groups.
Suppose $R\subseteq (\Sigma^*)^n$ be some $n$-ary relation. Our aim is to check a membership of the tuple $(x_1,x_2, \ldots, x_n)$ in $R$. For this we stack or \emph{convolute} these words, so that it might look like this in the case of $n=4$:
\[
\begin{bmatrix}
1 & 0 & 0 & 1 & 1\\
0 & 1 & 1 & & \\
1 & & & &\\
1 & 0 & 0 & &
\end{bmatrix}
\]
Observe that above block is nonuniform in length, so it cannot be generated by the tuples of the form $\Sigma^4$. To improve this situation, we append a special symbol, e.g. $\#$, to make the block uniform. So now the same block looks like:
\[
\begin{bmatrix}
1 & 0 & 0 & 1 & 1\\
0 & 1 & 1 & \# & \#\\
1 & \# & \# & \# & \#\\
1 & 0 & 0 & \# & \#
\end{bmatrix}
\]
These kinds of block form an input space of special kind of finite state machines known as multiple tape finite automata, which are going to be defined below:
Synchronous multi tape finite automata
Synchronous multi tape finite automata or synchronous automata for short read letters across rows one layer at a time or synchronously. A (deterministic) synchronous automaton $M=(Q,\Sigma, \delta, s_0, F)$ is similar to deterministic finite automata, except for the fact that $\delta:Q\times (\Sigma_{\#})^n \to Q$, where $\Sigma_{\#} = \Sigma \cup \#$. An synchronous finite automaton $M$ accepts a block $u$ if it ends at an accepting state when reading $u$. Let $L(M)$ be a collection of all blocks accepted by $M$. Then we say that $M$ recognizes a language $L(M)$. Here comes a main definition:
Automatic relation
A relation $R$ is said to be \emph{automatic} if there is a synchronous finite automaton $M$ recoginizing elements of $R$ written in the block form.
Having defined automatic relations, now we can define a notion of an automatic function.
Automatic function
Let $f$ be a function $f:(\Sigma^*)^n \to (\Sigma^*)^m$. We say that $f$ is an \emph{automatic function} if its graph $graph(f) = \{(x,f(x)):x\in (\Sigma^*)^n\}$ forms an automatic relation. Now we are ready to state famous result on the closure of automatic relations over first order logical definitions due to Nerode and Khoussainov:
Closure under first-order definition
Let a relation $R$ be first order definable from relations $(R_i)_{i=1}^n$ and functions $(f_j)_{j=1}^m$. If each of $R_i$ and $f_j$ happens to be automatic, then $R$ is automatic as well.
What are the examples of automatic relations? Let us give a few.
Length Comparison:
Let $R = \{(x,y):\vert x \vert < \vert y \vert \}$ be a pairs of words with the first word being strictly shorter. There is a multi-tape automaton recognizing this relation.
Lexicographic order:
Suppose we work with an alphabet $\Sigma = \{0,1 \}$. Suppose there is an initial order $0<1$. This order induces a lexicographic order in the collection of all words. To identify if $x<_{lex}y$ we compare corresponding symbols until they differ, and the word with $0$ symbol is set to be smaller. So, we have
$01111 \,<\, 10$
$0001 \,<\, 00100$
Again, one could construct a multitape automaton recognizing this relation.
Shortlex or length-lexicographic order:
The given order first compares lengths of two strings $x,y$ to identify a smaller element. If lengths are happened to be equal, then it uses lexicographic order to identify a smaller element. Observe that this relation can be defined by first order logical formula from previous relations:
\[
x<_{ll}y \Leftrightarrow \vert x \vert < \vert y \vert \text{ or }(\vert x \vert = \vert y \vert \text{ and }x<_{lex}y)
\]
By the first-order definability property, we have that length-lexicographic order is also automatic.
This seems to be all I want to say about automatic relations. Next times I hope to say something about finite automata recognizable groups.
Comments
Post a Comment