\documentstyle{article}

\newtheorem{theorem}[subsection]{Theorem}
\newtheorem{definition}[subsection]{Definition}
\newtheorem{notation}[subsection]{Notation}
\newtheorem{proposition}[subsection]{Proposition}
\newtheorem{lemma}[subsection]{Lemma}
\newtheorem{remark}[subsection]{Remark}

\newcommand\thmpar[1]{\begin{theorem}#1\end{theorem}}
\newcommand\dfnpar[2]{\begin{definition}\bf({#1})\rm{#2}\end{definition}}
\newcommand\notpar[1]{\begin{notation}\rm#1\end{notation}}
\newcommand\proppar[1]{\begin{proposition}#1\end{proposition}}
\newcommand\lempar[1]{\begin{lemma}#1\end{lemma}}
\newcommand\rempar[1]{\begin{remark}\rm#1\end{remark}}
\newcommand\prfpar[1]{\par\noindent{\bf Proof.}#1\hfill\rule{.3em}{1.5ex}}
\newcommand\abspar[1]{\begin{quote}{\bf Abstract.}{#1}\end{quote}}

\mathchardef\Sigma="0106

\newcommand\naka{\noindent\hfil}
\newcommand\ma{\noindent\qquad\qquad}
\newcommand\noi\noindent
\newcommand\inters\cap
\newcommand\union\cup
\newcommand\trans[1]{\begin{array}[b]{@{\,}c@{\,}}#1\\[-1.5ex]\to\end{array}}
\newcommand\transh[1]{\begin{array}[b]{@{\,}c@{\,}}#1\\[-1ex]\to\end{array}}
\newcommand{\Union}[1]{\begin{array}[t]{@{}c@{}}\bigcup\\[-.8ex]\mbox{\scriptsize$#1$}\end{array}}
\newcommand\SS{{\cal S}}
\newcommand\Sum[1]{\begin{array}[t]{@{}c@{}}\sum\\[-.8ex]\mbox{\scriptsize$#1$}\end{array}}
\newcommand\plng{{\mbox{\scriptsize\rm length}}}
\newcommand\kuu{{\rm\O}}
\newcommand\eps\epsilon
\newcommand\bunsuu[2]{\begin{array}{@{}c@{}}#1\\\hline#2\end{array}}
\newcommand\lng{{\mbox{\rm length}}}
\newcommand\maru*

\def\acc{\mathrel{\begin{array}[b]{@{}c@{}}*\;\\[-1.5ex]\to\end{array}}}
\def\tate{\mathrel{|}}

\newcommand\xref\ref
\newcommand\xlabel\label
\newcommand\vv\vspace

%%% --- %%% --- %%% --- %%% --- %%% --- %%%

\begin{document}

\noindent{\Large\bf
The measure of an omega regular language is
\\
rational
}\vspace{1.5ex}

\noindent{\bf
Takeuti Izumi
}

\noindent
Graduate School of Informatics, Kyoto Univ. 606-8501, JAPAN.
\\
{\tt takeuti@kuis.kyoto-u.ac.jp}

\ 

\abspar
	{
An omega regular language is the omega language
which is recognised by a Buchi automaton.
It has been known that
the measure of an omega regular language
recognised by a deterministic Buchi automaton
is a rational number.
This paper shows the measure of every omega regular language
is a rational number.
	}

\section{Introduction}

An omega regular language is the omega language
which is recognised by a Buchi automaton.
Many studies on omega regular languages and Buchi automata appear
in the literatures \cite{staiger,thomas},
which contain the proofs of most propositions in Sections 2 of this paper.
An important property is that
the recognising power of non-deterministic Buchi automata is
properly stronger than that of deterministic Buchi automata.

Yen Hsu-Chun and Lin Yih-Kai showed that
the measure of an omega regular language
recognised by a deterministic Buchi automaton
is a rational number \cite{ly}.
Unfortunately, their method cannot be applied
to non-deterministic Buchi automata.
Therefore, the characterisation on the general omega regular language
remained open.

The main result of this paper is
that the measure of every omega regular language is a rational number.
In order to prove this theorem,
we will introduce two new notions, which are irreducibility and sparseness.
The definition of irreducibility is the following:
An omega regular language \(X\subset\Sigma^\omega\) is irreducible iff
for each word \(v\in\Sigma^*\) there is a word \(w\in\Sigma^*\)
such that \(x\in X\) iff \(v\cdot w\cdot x\in X\) for any \(x\in\Sigma^\omega\).
The definition of sparseness is the following:
An omega regular language \(X\) is sparse iff
for a word \(w\in\Sigma^*\) and
an irreducible set \(Y\subset\Sigma^\omega\), if it holds that
\(x\in Y\) iff \(w\cdot x\in X\) for any \(x\in\Sigma^\omega\),
then \(Y\) is empty.
The purpose of these notions is to show the detachment lemma (\xref{detach}).
The detachment lemma states that an omega regular language
can be divided into a sparse set and some other subsets
each of which are the concatenation of a finite regular language and an irreducible set.
We will show some other lemmata on the measures.
Lemma \xref{irr-m} states that the measure of an irreducible set is 1 or 0.
Lemma \xref{sparse} states that the measure of a sparse set is 0.
These three lemmata are crucial.
And then, we will show the lemma such that
the measure of each finite-state set is a rational number.
The main lemma is proved with these lemmata above and the theorem by Lin and Yen.
Our main result is an immediate consequence of this main lemma,
for an omega regular language is finite-state.

\section{Buchi Automaton}
\dfnpar{Buchi Automaton}
	{
A {\em Buchi automaton} is defined
by five components \((\Sigma,S,T,s_0,F)\),
where each component has the following meaning:% zzz
\vv{1ex}

\naka
\begin{tabular}{l@{ }l}
\(\Sigma\)	& : alphabet, the set of symbols \\
\(S\)		& : the set of states \\
\(T\subset S\times\Sigma\times S\)
		& : transition relation \\
\(s_0\in S\)	& : the initial state \\
\(F\)		& : the set of final states
\end{tabular}
%
\vv{2ex}

\noi
Actually, final states are not final, but are
to be visited infinitely many times.
We call them final states only because of the traditional reason.

Let \(B\) be a Buchi automaton such as \(B=(\Sigma,S,T,s_0,F)\).
Then \(L(B)\) is a subset of \(\Sigma^\omega\) which defined as the following.
For \((\sigma_1,\sigma_2,...)\in\Sigma^\omega\),
\(
(\sigma_1,\sigma_2,...)\in L(B)
\)
iff there is \((s_1,s_2,...)\in S^\omega\) such that
\((s_{i-1},\sigma_i,s_i)\in T\) for each \(i=1,2,...\),
and that there are infinitely many \(i\)'s such that \(s_i\in F\).
%The set \(L(B)\) is called the {\em language} of \(B\).
We say that the Buchi automaton \(B\) {\em recognises} the set \(L(B)\)
	}
\dfnpar{Regularity}
	{
A set \(X\subset\Sigma^\omega\) is {\em regular}
iff \(X=L(B)\) for some Buchi automaton \(B\).
	}
\notpar
	{
A subset of \(\Sigma^\omega\) is called an {\em omega language},
and a regular subset of \(\Sigma^\omega\) is called an {\em omega regular language}.
However, we call a omega language a set.
Thus, an omega regular language is called a regular set.
Note that what is called a set not always an omega language.
	}
\rempar
	{
We call a subset of \(\Sigma^*\) a {\em language}.
We use the notion of {\em regular languages} as the ordinal definition,
which is defined with ordinal finite automata.
	}
\proppar
	{{\bf(Buchi '60)}\xlabel{reg-fsd}
A regular set is an \(F\sigma\delta\)-set.
	}
\prfpar
	{
By Buchi \cite{buchi},
or also by Remark 3.4 on Page 354 in the literature \cite{staiger}.
	}
\proppar
	{\xlabel{reg-det}
If \(W\subset\Sigma^*\) is a regular language.
Then \(W\cdot\Sigma^\omega\) is recognised by a deterministic Buchi automaton.
	}
\prfpar
	{
By Proposition 3.4 on Page 355 with Theorem 3.1 on Page 354 in the literature \cite{staiger}.
	}
\notpar
	{
For \(w=(w_1,w_2,...,w_m)\in\Sigma^*\)
and \(x=(x_1,x_2,...,x_n)\in\Sigma^*\) or \(X=(x_1,x_2,...)
\) \( % zzz a4 12pt
\in\Sigma^\omega\),
we write \(w\cdot x\) or \(wx\) for the concatenation of \(w\) and \(x\)
which is \((w_1,...,w_m,x_1,...x_n)\) or \((w_1,...,w_m,x_1,...)\).
For a set \(X\subset\Sigma^\omega\), \(w\cdot X=\{w\cdot x\tate x\in X\}\).
For sets \(W\subset\Sigma^*\) and \(X\subset\Sigma^\omega\),
\(W\cdot X=\{w\cdot X\tate w\in W\}\).
	}
\dfnpar{States}
	{
For \(X\subset\Sigma^\omega\) and \(w\in\Sigma^*\),
we write \(X/w\) for \(\{x\in\Sigma^\omega\tate w\cdot x\in X\}\),
and \(\SS(X)\) for \(\{Y\subset\Sigma^\omega\tate w\in\Sigma^*,Y=X/w\}\).
We call a set in \(\SS(X)\) {\em States}.
	}
\rempar
	{
\((X-Y)/w=X/w-Y/w\)
	}
\dfnpar{Finite-state sets}
	{
A set \(X\subset\Sigma^\omega\) is {\em finite-state} iff \(\SS(X)\) is finite.
	}
\proppar
	{\xlabel{finite}
Each regular set is finite-state.
	}
\prfpar
	{
In \cite{thomas}.
	}
\proppar
	{\xlabel{regular}
For a finite-state set \(X\subset\Sigma^\omega\) and a set \(Y\subset\Sigma^\omega\),
the set of words \(\{w\in\Sigma^*\tate X/w=Y\}\) is a regular language.
	}
\prfpar{ Easy. }
\section{Irreducible set}
\dfnpar{Accessibility}
	{
For \(X,Y\in\Sigma^\omega\), the relation \(X\acc Y\) holds
iff \(Y\in\SS(X)\), that is, there is \(w\in\Sigma^*\) such that \(Y=X/w\).
This relation \(\acc\) is called {\em accessibility}.
%We say that \(Y\) is {\em accessible} from \(X\) when \(X\acc Y\).
	}
\rempar
	{\xlabel{preorder}
Accessibility is reflexive and transitive.
	}
\proppar
	{\xlabel{maximal}
Let \(D\) be a non-empty finite set,
and a relation \(\leq\) be preorder, that is,
a reflexive transitive relation.
Then, for each \(d\in D\) there is a maximal element \(e\) in \(D\)
with respect to the preorder \(\leq\) such that \(d\leq e\).
	}
\prfpar
	{
Induction on the number of the elements of \(D\).
	}
\dfnpar{Irreducibility}
	{
A finite-state set \(X\in\Sigma^\omega\) is {\em irreducible}
iff \(Y\acc X\) for each \(Y\in\SS(X)\)
	}
\proppar
	{\xlabel{irr-ex}
For a finite-state set \(X\subset\Sigma^\omega\),
there exists at least one irreducible set in \(\SS(X)\).
	}
\prfpar
	{
An irreducible set is a maximal element with respect to \(\acc\),
and the domain \(\SS(X)\) is non-empty and finite.
Hence, it exists by Proposition \xref{maximal}.
	}
\dfnpar{Sparseness}
	{
A finite-state set \(X\) is {\em sparse} iff
the only irreducible set in \(\SS(X)\) is \(\O\).
	}
\rempar
	{
There are non-empty sparse sets.
For example, a singleton \(\{0^\omega\}\) is sparse where \(\Sigma=\{0,1\}\).
	}
\dfnpar{\(\maru\)-operation}
	{
For sets \(X,Y\subset\Sigma^\omega\), the set \(X\maru Y\in\Sigma^\omega\)
is defined as:

\noi\ 
\(
X \maru Y = \{ w \cdot x \in X \tate \exists v \in \Sigma^*. \; x \in X/w=Y/v \}
=\union\{w\cdot(X/w)\tate X/w\in\SS(Y)\}
\).
	}
\rempar
	{\xlabel{pref}
Let \(X\) and \(Y\) be subsets of \(\Sigma^\omega\).
Put \(W=\{w\in\Sigma^*\tate X/w\in\SS(Y)\}\).
Then, there is a prefix-free subset \(V\subset W\) such that
for each \(w\in W\) there are \(v\in V\) and \(u\in\Sigma^*\)
such that \(v\cdot u=w\).
Thus it holds that \( X \maru Y = \Union{v\in V} v\cdot(X/v) \)
	}
\rempar
	{\xlabel{pref-reg}
In general, for each \(W\subset\Sigma^*\)
there is a prefix-free subset \(V\subset W\) such that
for each \(w\in W\) there are \(v\in V\) and \(u\in\Sigma^*\)
such that \(v\cdot u=w\).
If \(W\) is a regular language, then so is \(V\).
	}
\proppar
	{\xlabel{aster}
For sets \(X,Y\in\Sigma^\omega\) and a word \(w\in\Sigma^*\),
%\par\naka % zzz
\((X/w)\maru Y=(X\maru Y)/w\).
	}
\prfpar
	{
For \(x\in\Sigma^\omega\), \(x\in(X\maru Y)/w\) iff
\(wx\in X\maru Y\),
which is equivalent to

\naka\(
\exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;wx=uy\;\&\;y\in X/u=Y/v
\).

\noi This is equivalent to

\ma\(
\exists u,u',v\in\Sigma^*.\exists y\in\Sigma^\omega.\;
u=wu'\;\&\;x=u'y\;\&\;y\in X/wu'=Y/v
\)

\ma or

\ma\(
\exists u,w',v\in\Sigma^*.\exists y\in\Sigma^\omega.\;
w=uw'\;\&\;w'x=y\;\&\;y\in X/u=Y/v
\)

The upper case is transformed by deleting the variable \(u\),
then it is equivalent to:

\naka
\(\exists u',v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=u'y\;\&\;y\in X/wu'=Y/v\).

We consider the lower case. Suppose that
\(w=uw'\;\&\;w'x=y\;\&\;y\in X/u=Y/v\).
Then \(x\in X/uw'=X/w=Y/vw'\). This implies

\naka\(
\exists u',v'\in\Sigma^*.\exists y'\in\Sigma^\omega.\;x=u'y'\;\&\;y'\in X/wu'=Y/v'\).

\noi by instantiating \(u'\) with empty word,
\(v'\) with \(vu'\), and \(y'\) with \(x\).

In the formula with disjunction,
the right part of disjunction implies the left part.
Hence, the whole formula is equivalent to the left part.
Thus it is equivalent to:

\naka\(
\exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=uy\;\&\;y\in X/wu=Y/v\).

\noi This is equivalent to

\naka\(
\exists u,v\in\Sigma^*.\exists y\in\Sigma^\omega.\;x=uy\;\&\;y\in(X/w)/u=Y/v
\).

\noi This is equivalent to \(x\in(X/w)\maru Y\).
	}

\lempar
	{{\bf(Detachment lemma)}\xlabel{detach}
For each finite-state set \(X\), there are a sparse set \(Z\),
a finite index set \(I\) and
indexed families \(\{W_i\}_{i\in I}\) and \(\{Y_i\}_{i\in I}\)
such that
%\vv{1ex}

\naka
\( X = Z \union \Union{i\in I} W_i\cdot Y_i \)
%\vv{1ex}

\noi
where each \(W_i\) is a prefix-free regular language,
each \(Y_i\) is an irreducible set,
and \( W_i\cdot Y_i \inters W_j\cdot Y_j = \kuu \)
and \( Z \inters W_j\cdot Y_j = \kuu \) for any \(i\neq j\).

	}
\prfpar
	{
The proof is done by induction on the number of the elements of \(\SS(X)-\{\O\}\).

(Base case)
If  \(\SS(X)-\{\O\}=\O\), then \(X=\O\) and the assertion of this lemma holds.

(Induction step)
We show that the case of \(X\) can be reduced to the case of another \(X'\)
where \(\SS(X')-\{\O\}\) has less elements than \(\SS(X)-\{\O\}\).

By the Proposition \xref{irr-ex}, there is at least one irreducible set in \(\SS(X)\).
If the only irreducible set in \(\SS(X)\) is the empty set, then
\(X\) is sparse, and the assertion of the lemma holds.
Therefore we assume that there are non-empty irreducible set \(Y\in\SS(X)\).
Put \(Y\in\SS(X)\) as such an irreducible set.
Each \(Z\in\SS(Y)\) is also irreducible
by the definition of irreducibility.

If \(\SS(X)=\SS(Y)\), then \(X\) is already irreducible,
and the assertion of the lemma holds,
because \(X=\O\union\{()\}\cdot X\)
where \(\O\) is sparse and the set \(\{()\}\) is the singleton of empty words,
which is a regular language.
Therefore, we assume that \(\SS(X)\neq\SS(Y)\), that is, \(X\not\in\SS(Y)\).

First we will show that \(X\maru Y=\Union{i\in I}W_i\cdot Y_i\)
and it holds that for each \(i\in I\) the set \(W_i\) is a prefix-free regular language,
and \(Y_i\in\SS(Y)\).

Let \(I\) be a index set which has the same number of elements as \(\SS(Y)\) has,
and \(\{Y_i\tate i\in I\}\) be equal to \(\SS(Y)\).
Put \(V_i=\{v\in\Sigma^*\tate X/v=Y_i\}\).
Then \(X\maru Y=\Union{i\in I}V_i\cdot Y_i=\Union{i\in I}\,\Union{v\in V_i}v\cdot(X/v)\).
As Remark \xref{pref}, there is a prefix-free subset \(W\subset\Union{i\in I}V_i\)
such that \(X\maru Y=\Union{w\in W}w\cdot(X/w)\).
Put \(W_i=W\inters V_i\). Then \(W_i\) is prefix-free.

As Proposition \xref{regular}, each \(V_i\) is a regular language,
then so is \(\Union{i\in I}V_i\), for \(I\) is finite.
As Remark \xref{pref-reg}, the subset \(W\) is a regular language,
and then so is \(W_i\).

Therefore we have \(X\maru Y=\Union{i\in I}W_i\cdot Y_i\)
where for each \(i\in I\), \(W_i\) is a prefix-free regular language
and \(Y_i\in\SS(Y)\).
Moreover, each \(V_i\) and \(V_j\) are disjoint for \(i\neq j\).
Therefore each \(W_i\) and \(W_j\) are disjoint.
In addition, \(W_i\union W_j\) is prefix-free.
These facts imply that each \(W_i\cdot Y_i\) and \(W_j\cdot Y_j\) are disjoint.

Next we discuss \(X-X\maru Y\).

The mapping \(Z\mapsto Z-Z\maru Y\) is a function
of \(\SS(X)\) into \(\SS(X-X\maru Y)\).
That is because if \(Z\in\SS(X)\) then \(Z=X/w\) for some \(w\).
Hence \(Z\maru Y=(X\maru Y)/w\) by Proposition \xref{aster},
so \(Z-Z\maru Y=X/w-(X\maru Y)/w=(X-X\maru Y)/w\in\SS(X-X\maru Y)\).
Moreover, the mapping \(Z\mapsto Z-Z\maru Y\) is a surjection.
That is because if \(Z'\in\SS(X-X\maru Y)\)
then for some \(w\), it holds that \(Z'=(X-X\maru Y)/w=(X/w)-(X/w)\maru Y\)
and \(X/w\in\SS(X)\).
Note that this mapping maps \(Y\) into \(Y-Y\maru Y=\O\),
and of cause \(\O-\O\maru Y=\O\).
Hence, the number of elements of \(\SS(X-X\maru Y)-\{\O\}\) is
less than or equal to that of \(\SS(X)-\{\O,Y\}\),
Therefore the number of elements of \(\SS(X-X\maru Y)-\{\O\}\) is
less than that of \(\SS(X)-\{\O\}\).
Thus, induction hypothesis holds for \(\SS(X-X\maru Y)\).

By the induction hypothesis, there are a sparse set \(Z\)
and familys \(\{W'_i\}_{i\in I'}\) and \(\{Y'_i\}_{i\in I'}\)
such that
\( X - X \maru Y = Z \union \Union{i\in I'} W'_i\cdot Y'_i \)
where \(Z\), \(\{W'_i\}={i\in I'}\) and \(\{Y'_i\}={i\in I'}\)
satisfies the disjointness in the assertion of this lemma.

Therefore

\naka\(
X = X \maru Y \union ( X - X \maru Y )
= Z \union \left( \Union{i\in I'} W'_i\cdot Y'_i \right)
\union \left( \Union{i\in I} W_i\cdot Y_i \right) \)
\vv{1ex}

\noi
The disjointness in the assertion holds
because \( X \maru Y \) and \( X - X \maru Y \) are disjoint.
\par\ % zzz
	}

\section{Measure}
\rempar
	{
We fix the alphabet \(\Sigma\) which consists of \(n\) symbols.
	}
\notpar
	{
We use the notations \(U\) and \(U(w)\) as \(U=\Sigma^\omega\)
and \(U(w)=w\cdot\Sigma^\omega\subset\Sigma^\omega\) for \(w\in\Sigma^*\).
	}
\dfnpar{Measure}
	{
For a set \(X\subset\Sigma^\omega\), the measure \(\mu(X)\) is defined as:
%\vv{1ex}

\naka
\( \mu(X)=\inf\left\{\Sum{i\in I}n^{-\plng(w_i)}\left| X\subset\Union{i\in I}U(w_i)\right.\right\} \).
	}
\dfnpar{Measurability}
	{
A set \(X\subset\Sigma^\omega\) is {\em measurable} iff
\(\mu(X)+\mu(U-X)=1\).
	}
\rempar
	{
This \(\mu(X)\) is usually called the outer measure if \(X\) is not neasurable.
	}
\rempar
	{
The following propositions \xref{m-fsd} and \xref{m-pref} are easily seen form the discussion
in the literature \cite{textbook}.
	}
\proppar
	{\xlabel{m-fsd}
If \(X\subset U\) is a \(F\sigma\delta\)-set, then \(X\) is measurable.
	}
\proppar
	{\xlabel{m-pref}
If the set of words \(\{w_i\in\Sigma^*\tate i\in I\}\) is prefix-free,
Then, it holds that

\naka
\(\mu\left(\Union{i\in I}w_i\cdot X_i\right)
=\Sum{i\in I}2^{-\plng(w_i)}\mu(X_i)\).

	}
\lempar
	{
A regular set is measurable.
	}
\prfpar
	{
By Propositions \xref{reg-fsd} and \xref{m-fsd}.
	}
\thmpar
	{{\bf(Lin \& Yen '00)}\xlabel{m-det}
For each deterministic Buchi automaton \(B\),
the measure \(\mu(L(B))\) is rational.
	}
\prfpar
	{
By Lin and Yen \cite{ly}.
	}
\rempar
	{
Lin and Yen proves the theorem above with the property of Markov chains.
A deterministic Buchi automaton is regarded as a Markov chain in their proof.
Unfortunately, their method cannot be applied
to non-deterministic Buchi automata.
	}
\lempar
	{\xlabel{irr-eq}
If \(X\) is irreducible, then for each \(Y\in\SS(X)\), \(\mu(X)=\mu(Y)\).
	}
\prfpar
	{
Because \(\SS(X)\) is finite, then there exists \(m=\max\{\mu(Y)\tate Y\in\SS(X)\}\).
Put \(E=\{Y\in\SS(X)\tate\mu(Y)=m\}\).
Then the assertion of this lemma is equivalent to \(E=\SS(X)\).
We will prove this by reductio ad absurdum.

Suppose that \(\SS(X)-E\) is not empty.
Put \(Y\) and \(Y'\) as \(Y\in E\) and \(Y'\in\SS(X)-E\).
Because \(X\) is irreducible, there is a sequence of sets
\(Y=Y_1,Y_2,...,
%\) \( % zzz
Y_{l-1},Y_l=Y'\) such that
\(Y_i/\sigma_i=Y_{i+1}\) for some \(\sigma_i\in\Sigma\).
Because \(Y_1\in E\) and \(Y_l\not\in E\), there is a pair \((Y_i,Y_{i+1})\)
such that \(Y_i\in E\) and \(Y_{i+1}\not\in E\).
Note that

\naka
\(Y_i=\Union{\sigma\in\Sigma}\sigma\cdot(Y_i/\sigma)\).

\noi
By Proposition \xref{m-pref},

\naka
\(\mu(Y_i)=\bunsuu1n\Sum{\ \sigma\in\Sigma\ }\mu(Y_i/\sigma)\)

\noi
Therefore,

\naka
\(m\leq\bunsuu1n\;\mu(Y_{i+1})+\bunsuu{n-1}n\;m<\bunsuu1n\;m+\bunsuu{n-1}n\;m=m\),

\noi
that is, \( m<m \). This is contradiction.
	}
\lempar
	{\xlabel{irr-m}
For each irreducible set \(X\), \(\mu(X)=1\) or  \(\mu(X)=0\).
	}
\prfpar
	{
We will prove this theorem by reductio ad absurdum.

Put \(m=\mu(X)\). If \(m\) is neither 1 nor 0,
then there is \(\eps\) such that \(0<\eps<m(1-m)\).

As the definition of \(\mu\), there is a set \(\{w_i\tate i\in I\}\) such that
\( X \subset \Union{i\in I} U(w_i) \)
and that

\naka
\( m < \Sum{i\in I} n^{-\plng(w_i)} < m+\eps \).

\noi
Without loss of generousity we can assume that
\(\{w_i\tate i\in I\}\) is prefix-free.

Then, there is a finite subset \(J\subset I\) such that

\naka
\( \bunsuu\eps{1-m} < \Sum{j\in J} n^{-\plng(w_j)} \).

Put \(V=\Union{j\in J}U(w_j)\), \(b=\mu(V)\)
and \(l=\max\{\lng(w_j)\tate j\in J\}\).
The number \(l\) exists because \(J\) is finite.
Note \(b>\bunsuu\eps{1-m}\).
Let \(K\) be the set \(\{v\in\Sigma^l\tate U(v)\not\subset V\}\).
Then \(\Union{v\in K}U(v)=U-V\).
The number of all the elements of \(K\) is \(n^l(1-b)\).

Thus, the following equations hold:
\vv{1ex}

\naka
\(X-V=X\union\left(\Union{v\in K}U(v)\right)=\Union{v\in K}X\inters U(v)
=\Union{v\in K}v\cdot(X/v)\).
\vv{1ex}

\noi
By Lemma \xref{irr-eq}, \(\mu(X/v)=m\), hence by Proposition \xref{m-pref},
\vv{1ex}

\naka
\(\mu(X-V)=\Sum{v\in K}n^{-l}\mu(X/v)=(1-b)\cdot m\).
%\vv{1ex}

\noi
Therefore, 
\vv{1ex}

\naka
\(\mu(X\union V)=\mu(V)+\mu(X-V)=b+m(1-b)=m+b(1-m)>m+\eps\).
\vv{1ex}

On the other hand,
\vv{1ex}

\naka
\(X\subset\Union{i\in I}U(w_i)\) \ and \ \(V\subset\Union{i\in I}U(w_i)\).

\noi
Thus

\naka
\(X\union V\subset\Union{i\in I}U(w_i)\).

\noi
Therefore

\naka
\(\mu(X\union V)\leq\mu\left(\Union{i\in I}U(w_i)\right)<m+\eps\).
\vv{1ex}

Those make contradiction.
	}
\lempar
	{\xlabel{sparse}
The measure of a sparse set is \(0\).
	}
\prfpar
	{
Let \(X\subset U\) be sparse.
By Proposition \xref{maximal}, for each \(Y\in\SS(X)\), \(X\acc\O\),
that is for each \(Y\in\SS(X)\), there is a word \(w\in\Sigma^*\)
such that \(Y/w=\O\).
Put \(Y\in\SS(X)\) as \(\mu(Y)=\max\{\mu(Z)\tate Z\in\SS(X)\}\).
Such \(Y\) exists because \(\SS(X)\) is finite.
Put \(w\in\Sigma^*\) as \(Y/w=\O\) and \(l=\lng(w)\).
Then \(Y=\union\{Y/v\tate v\in\Sigma^*,\lng(v)=l\}\).
Hence

\ma
\(\mu(Y)=\mu(Y/w)+\Sum{\lng(v)=l,v\neq w}\mu(Y/v)
\leq \Sum{\lng(v)=l,v\neq w}\mu(Y)\)

\ma
\(=(1-2^{-l})\mu(Y)\).

\noi
because \(Y/v\in\SS(X)\). Thus, \(\mu(Y)\leq(1-2^{-l})\mu(Y)\),
which implies \(\mu(Y)=0\).

We have \(\mu(X)\leq\mu(Y)\) because of \(X\in\SS(X)\), therefore \(\mu(X)=0\).
	}
\lempar
	{\xlabel{princ}
The measure of a finite-state set is rational.
	}
\prfpar
	{
By the detachment lemma \xref{detach}, \(X=Z\union\Union{i\in I}W_i\cdot Y_i\)
where \(Z\) is sparse, the indexed set \(I\) is finite,
each \(W_i\) is a regular language, each \(Y_i\) is regular,
and all the summands of the union operator are disjoint to each other.

By Proposition \xref{m-pref},
we have \(\mu(W_i\cdot Y_i)=\mu(W_i\cdot U)\cdot\mu(Y)\),
hence
\(\mu(X)=\mu(Z)+\Sum{i\in I}\mu(W_i\cdot U)\cdot\mu(Y_i)\).

By Proposition \xref{sparse},
\(\mu(Z)=0\), therefore, \(\mu(X)=\Sum{i\in I}\mu(W_i\cdot U)\cdot\mu(Y_i)\).

By Lemma \xref{irr-m}, \(\mu(Y)\) is 1 or 0. Put \(J=\{j\in I\tate \mu(Y_j)=1\}\),
Then,  \(\mu(X)=\Sum{j\in J}\mu(W_j\cdot U)\).

This summation is finite.
By Lemma \xref{m-det} and Proposition \xref{reg-det},
each summand \(\mu(W_j\cdot U)\) is rational.
It implies \(\mu(X)\) is finite.
	}
\thmpar
	{
The measure of an omega regular language is rational.
	}
\prfpar
	{
By Proposition \xref{finite} and Lemma \xref{princ}.
	}

\begin{thebibliography}{w}

\bibitem[It\^o]{textbook}
	It\^o, S\^ez\^o.:
	{\it Rub\^egu Sekibun Ny\^umon},
	S\^ugaku Sensyo, Sy\^okab\o, Tokyo, 1963 (in Japanese).

\bibitem[B\"uchi]{buchi}
	B\"uchi, J. Richard.:
	On a Decision Method in Restricted Second Order Arithmetic,
	{\it Proc. of the International Congress
	on Logic, Method and Philosophy of Science,}
	pp. 1--12, Stanford University Press, Stanford, 1962.

\bibitem[Thomas]{thomas}
	Thomas, W.:
	Automata on Infinite Objects,
	{\it Handbook of Theoretical Computer Science,} Vol. B,
	van Leeuwen, J. ed.,
	Elsevier Science B. V.,	1990.

\bibitem[Staiger]{staiger}
	Staiger, L:
	Omega Languages,
	{\it Handbook of Formal Languages},
	Rozenberg, G. \& Salomaa, A. eds.,
	Springer, 1997.

\bibitem[Lin\&Yen]{ly}
	Lin, Yih-Kai \& Yen, Hsu-Chun:
	An omega-automata approach to the compression of bi-level images,
	{\it Proc. of CATS 2000,}
	Electronic Notes in Theoretical Computer Science, Vol. 31, No. 1,
	Elsevier Science B. V.,	2000.

\end{thebibliography}

\section*{Acknowledgement}
I am greatful for Lin Yih-Kai, Yamazaki Hideki, Ito Masami and Takahashi Masako
for discussions and comments.



\end{document}
