Fundamentals of Computing and Discrete Mathematics

Teturo Kamae

Matsuyama University - Japan

May-June 2012

Distinguished Lecture Colloquium

Super-stationary structure of dynamical systems

For a nonempty closed set $\Omega \subset A^{N}$, where A is a finite set with $|A| \geq 2$ and $N= \{0,1,2, \cdots \}$, we discuss its super-stationary factors. For any increasing sequence $S=(s_1,\cdots , s_k) \in N^k$, we define the restriction of $\omega \in A^N$ to S to be $\omega [S] = \omega(s_1) \cdots \omega (s_k) \in A^k$, and the restriction of $\Omega$ to S to be $\Omega [S] = \{\omega [S]; \omega \in \Omega \} \subset A^k $. A k-super-stationary set is a set $\Theta \subset A^N$ such that for any increasing sequence $S=(s_1,\cdots , s_k) \in N^k$, $\Theta[S]$ is independent of S. We call it a super-stationary set if it is closed and k-super-stationary for any k in N. A super-stationary set $\Theta$ is called a super-stationary factor of $\Omega$ at $\chi$, where $\chi$ is a ultrafilter on $\Sigma$, if $\Theta= \Omega[\chi ^ \infty]$ holds, where $\Omega[\chi^\infty]$ is the projective limit of $\Omega[\chi^k]$ as $k \to \infty$, $\chi^k$ is the k-times product of the ultrafilter $\chi$ on $\Sigma$, and $\Omega[\chi^k]$ is the value at the ultrafilter $\chi^k$ of the natural extension of the restriction map from $\Sigma^k$ to the family of subsets of $A^k$ given by $S \mapsto \Omega [S]$ with $S \in \Sigma^k$. We prove that $\Omega[\chi^\infty]$ always exists and is a super-stationary set. Super-stationary factors of underlying spaces of some interesting symbolic dynamical systems are discussed.

TUCS Short Course

Maximal pattern complexity applied to pattern recognition problems

For a family $\Omega$ of sets in $R^2$ and a finite subset S of $R^2$, let $p_\Omega (S)$ be the number of distinct sets of the form $S \cap \omega$ for all $\omega \in \Omega$. The maximum pattern complexity $p^*_\Omega (k)$ is the maximum of $p_\Omega (S)$ among S with $|S|= k$. The S attaining the maximum is considered as the most effective sampling to distinguish the sets in $\Omega$. We obtain the exact values or at least the order of $p^*_\Omega (k)$ in k for carious classes $\Omega$. We also discuss the dual problem in the case that $|\Omega|=\infty$, that is, consider the partition of $R^2$ generated by a finite family $T \subset \Omega$. The number of elements in the partition is written as $p_{R^2}(T)$ and $p_{R^2}^*(T)$ is the maximum of $p_{R^2}(T)$ among T with $|T|= k$. Here, $p_{\Omega}^*(k)=p_{R^2}^*(k)$ does not hold in general. For the general setting that $\Omega$ is an infinite subset of $A^\Sigma$, where A is a finite alphabet, $\Sigma$ is an arbitrary infinite set, and $p_\Omega^*(k)=\max _{|S|=k}\left|\Omega|_S\right|$, we show that the entropy \[ h(\Omega) := \lim_{k\to \infty} \log p_\Omega^* (k)/k \] exists and takes value in $\{\log 1, \log 2, \cdots, \log |A|\}$. Moreover, we prove that the entropy $h(\Sigma)$ of the dual systems coincides with $h(\Omega)$.

Uniform sets and uniform complexity

Let A be a finite set with $|A| \geq 2$. For a nonempty closed subset $\Omega$ of $A^N$, where $N=\{0,1,2,\cdots\}$, let $p_\Omega (S):= |\Omega[S]|$ be the complexity function depending on the nonempty finite sets $S\subset N$, where $\Omega[S]$ is the restriction of $\Omega$ to S, that is \[\Omega[S]=\{\omega(s_1)\omega(s_2)\cdots\omega(s_k) \in A^k; \omega \in \Omega\}, \] with $S=\{s_1 < s_2 < \cdots < s_k\}$. We call $\Omega$ a uniform set if $p_\Omega(S)$ depends only on $|S|=k$ and the complexity function $p_\Omega(k):= p_\Omega (S)$ as a function of $k=\,2,\cdots$ is called the uniform complexity function of $\Omega$. It is proved that any uniform complexity is realized by a super-stationary set. This gives a formula to calculate the uniform complexity functions.

Characterizations of super-stationary sets

Let A be a finite set with $|A| \geq 2$ and $\Omega$ be a nonempty closed subset of $A^N$, where $N=\{0,1,2,\cdots\}$. For an infinite set $\mathcal N = \{n_0 < n_1 < n_2 < \cdots \} \subset N$, $\omega \in A^N$, define $\omega[\mathcal N] \in A^N$ and $\Omega[\mathcal N] \subset A^N$ by \[ \omega [ \mathcal N ] (i) := \omega(n_i) (i \in N) \] and \[ \Omega [\mathcal N] := \{\omega [\mathcal N] \in A^N; \omega \in \Omega\}. \] We call $\Omega$ a super-stationary set if $\Omega[\mathcal N ]=\Omega$ holds for any infinite subset $\mathcal N$ of $N$. We give a characterization of super-stationary set in terms of prohibited word. Super-stationary sets are considered as phenomena which are independent of the time scale, but sensitive only to the direction of time, or dependent just on the order of what happen in time series.

Additional Material

A PDF version of the abstracts can be downloaded here.

Last modified: