Printer Friendly

On the Hausdorff measure of regular [omega]-languages in cantor space.

Regular [omega]-languages are not only famous because they are definable by finite automata but also because they are the ones definable in Buchi's [Buc62] restricted monadic second order arithmetic (cf. the survey [Tho90] or [PP04]).

Hausdorff dimension and Hausdorff measure for regular [omega]-languages have been proved to be computable (cf. [Ban89, MW88, Edg08] or [MS94, Sta98a]). The computation of the Hausdorff measure of a regular [omega]-language uses several properties which do not hold for larger classes of [omega]-languages (cf. [Sta93, MS94, Sta98b]). These properties show that subsets of the Cantor space definable by finite automata really deserve the name "regular".

For instance, Theorem 21 of [MS94] shows a strong connection of Hausdorff dimension and topological density for regular [omega]-languages closed in Cantor space, and the measure-category-theorem of [Sta98b] shows that this connection can be extended to arbitrary regular [omega]-languages.

Our investigations relate the Hausdorff measure of a subset of the Cantor space to the Hausdorff measure of its closure. The result in Section 4.1 shows that under a certain homogeneity condition the measure of a regular [omega]-language coincides with the measure of its closure. The proof uses the decomposition theorem of [Sta98a] which is based on McNaughton's theorem [McN66] and extends in some sense earlier decompositions of [Arn83], [SW74] and [Wag79] (i). In our paper the decomposition is directed to a partition of the set of final sets (the table) T of a Muller automaton A accepting a given [omega]-language F = [L.sub.[omega]] (A) into the ones contributing to the usdorff measure and the ones not contributing. Crucial for this partition is the fact that only those final sets in T maximal w.r.t. set inclusion can contribute to the Hausdorff measure of the accepted [omega]-language.

Another result (in Section 4.2) is a sufficient condition under which infinite intersections of regular [omega]-languages topologically large relative to its closure have the same Hausdorff measure as their closure. Here, for the case of finite measure, we rely on the measure-category theorem derived in [Sta98b, Theorem 4] (see also [VV06, Section 4.4]). The extension to sets of infinite measure requires the closer inspection of regular [omega]-languages closed in Cantor space as given in Section 3.3.

The paper is organised as follows. After introducing some notation in Section 2 several properties of Hausdorff measure and dimension are listed. Then the third section deals with decompositions of regular [omega]-languages derived from the accepting automata. This concerns the general decomposition as in [Sta98a], a new decomposition according to non-null Hausdorff measure and the decomposition of closed sets mentioned above. Then in Section 4 we derive the results on the coincidence of the Hausdorff measures of [omega]-languages of a certain shape and their closures.

1 Notation

In this section we introduce the notation used throughout the paper. By N = {0,1, 2,...} we denote the set of natural numbers. Its elements will be usually denoted by letters i, ..., n. Let X be an alphabet of cardinality [absolute value of X] = r [greater than or equal to] 2. Then [X.sup.*] is the set of finite words on X, including the empty word e, and [X.sup.[omega]] is the set of infinite strings ([omega]-words) over X. Subsets of [X.sup.*] will be referred to as languages and subsets of [X.sup.[omega]] as [omega]-languages.

For w [member of] [X.sup.*] and [eta] [member of] [X.sup.*] [union] [X.sup.[omega]] let w x [eta] be their concatenation. This concatenation product extends in an obvious way to subsets W [subset or equal to] [X.sup.*] and B [subset or equal to] [X.sup.*] U [X.sup.[omega]]. For a language W let [W.sup.*] := [[universal].sub.i[member of]N] [W.sup.i], and [W.sup.[omega]] := {[w.sub.1] ... [w.sub.i] ... : [w.sub.i] [member of] W \ {e}} be the set of infinite strings formed by concatenating non-empty words in W. Furthermore, [absolute value of w] is the length of the word w [member of] [X.sup.*] and pref(B) is the set of all finite prefixes of strings in B [subset or equal to] [X.sup.*] [union] [X.sup.[omega]]. We shall abbreviate w [member of] pref ({[eta]}) ([eta] [member of] [X.sup.*] [union] [X.sup.[omega]]) by w [??] [eta].

As usual, we consider [X.sup.[omega]] as a topological space (Cantor space). The closure (smallest closed set containing F) of a subset F [subset or equal to] [X.sup.[omega]], C(F), is described as C(F) := {[xi] : pref ({[xi]}) [subset or equal to] pref (F)}. The open sets in Cantor space are the [omega]-languages of the form W x [X.sup.[omega]].

We assume the reader to be familiar with the basic facts of the theory of regular languages and finite automata. We postpone the definition of regularity for [omega]-languages to Section 3. For more details on [omega]-languages and regular [omega]-languages see the book [PP04] or the survey papers [Sta97, Tho90].

2 Hausdorff Dimension and Hausdorff Measure

First, we shall describe briefly the basic formulae needed for the definition of Hausdorff dimension and Hausdorff measure. For more background and motivation see Section 1 of [MS94].

We recall the definition of the Hausdorff measure and Hausdorff dimension (see [Edg08, Fal90]) of a subset of [X.sup.[omega]]. In the setting of languages and [omega]-languages this can be read as follows (see [Sta93, Sta98a]). For F [subset or equal to] [X.sup.[omega]], r = [absolute value of X] [greater than or equal to] 2 and 0 [less than or equal to] [alpha] [less than or equal to] 1 the equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

defines the [alpha]-dimensional metric outer measure on [X.sup.[omega]].

The measure [L.sub.a] satisfies the following properties (see [Edg08, Fal90, MS94]).

Proposition 1 Let F [subset or equal to] [X.sup.[omega]], V [subset or equal to] [X.sup.*] and [alpha] [member of] [0,1].

1. If [L.sub.[alpha]](F) < [infinity] then [L.sub.[alpha]+[epsilon]](F) = 0 for all [epsilon] > 0.

2. If F [subset or equal to] {[xi] : [xi] [member of] [X.sup.[omega]] [omega] pref ([xi]) [subset or equal to] V} and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. It holds the scaling property [L.sub.[alpha]](w x F) = [r.sup.-[alpha] x [absolute value of v] x [L.sub.[alpha]](F).

4. If V is prefix-free then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then the Hausdorff dimension of F is defined as

dim F: = sup{[alpha] : [alpha] = 0 [disjunction] [L.sub.[alpha]] (F) = [infinity]} = inf {[alpha] : [L.sub.[alpha]](F) = 0}.

It should be mentioned that dim is countably stable and invariant under scaling, that is, for [F.sub.i] [subset or equal to] [X.sup.[omega]] we have

dim [[universal].sub.i[member of]n] [F.sub.i] = sup{dim [F.sub.i] : i [member of] N} and dim w x [F.sub.0] = dim [F.sub.0]. (2)

In particular, every at most countable subset E [member of] [X.sup.[omega]] has Hausdorff dimension dim E = 0, and the measure [L.sub.0] is the counting measure, that is, [L.sub.0](E) = [absolute value of E] if E is finite and [L.sub.0](E) = [infinity], otherwise.

Hausdorff dimension and measure need not be distributed uniformly on a set. In order to describe a certain homogeneity we use the following concept (cf. [MS94, Section 4]). We say that an [omega]-language F has locally positive [alpha]-dimensional measure provided [L.sub.[alpha]](F [intersection] w x [X.sup.[omega]]) > 0 for all [omega] [member of] pref (F). Then the following technical result is true.

Proposition 2 Let F [subset or equal to] [X.sup.[omega]] have dim F = [alpha], [L.sub.[alpha]](F) < [infinity] and locally positive [alpha]-dimensional measure. If F' [subset or equal to] F and [L.sub.[alpha]] (F') = [L.sub.[alpha]](F) then pref(F') = pref(F) and, consequently, C(F') = C(F).

Proof: First observe that F' [subset or equal to] [subset or equal to] implies [L.sub.[alpha]] (F' [intersection] w x [X.sup.[omega]]) [less than or equal to] [L.sub.[alpha]] (F [intersection] w v [X.sup.[omega]]) for all w [member of] [X.sup.*]. Then the general identity (see Proposition 1.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the hypothesis [L.sub.[alpha]](F') = [L.sub.[alpha]](F) < [infinity] imply [L.sub.[alpha]](F' [intersection] w x [X.sup.[omega]]) = [L.sub.[alpha]](F [intersection] w x [X.sup.[omega]]).

Obviously, pref (F') [subset or equal to] pref (F). Let now w [member of] pref (F). Then [L.sub.[alpha]](F [intersection] w x [X.sup.[omega]]) > 0 which in view of [L.sub.[alpha]](F' [intersection] w x [X.sup.[omega]]) = [L.sub.[alpha]](F [intersection] w x [X.sup.[omega]]) implies w [member of] pref (F').

We add a further relation of the Hausdorff dimension and the measure [L.sub.[alpha]] for [omega]-languages of a special shape.

Proposition 3 Let [alpha] = dim [W.sup.[omega]]. Then [L.sub.[alpha]]([W.sup.[omega]]) [less than or equal to] 1, and if, moreover, [L.sub.[alpha]]([W.sup.[omega]]) > 0 then [W.sup.[omega]] has locally positive [alpha]-dimensional measure.

Proof: The first part is Proposition 6.6 of [Sta93]. Let w [member of] pref ([W.sup.[omega]]). Then there is a v [member of] [X.sup.*] such that wv [member of] [W.sup.*], and, consequently wv x [W.sup.[omega]] [subset or equal to] [W.sup.[omega]] [intersection] w x [X.sup.[omega]]. Now Proposition 1.3 yields 0 < [L.sub.[alpha]](wv x [W.sup.[omega]]) [less than or equal to] [L.sup.[alpha]]([W.sup.[omega]] [intersection] w x [X.sup.[omega]]).

3 Decomposition of Regular [omega]-languages

As usual we call a language W [subset or equal to] [X.sup.*] regular if there is a finite (deterministic) automaton A = (X; S; [s.sub.0]; [delta]), where S is the finite set of states, [s.sub.0] [member of] S is the initial state and [delta] : S x X [right arrow] S is the transition function (ii), such that W = {w : [delta]([s.sub.0]; w) [member of] S'} for some fixed set S' [subset or equal] S.

An [omega]-language F [subset or equal to] [X.sup.[omega]] is called regular provided there are a finite (deterministic) automaton A = (X; S; [s.sub.0]; [delta]) and a table T [subset or equal to] {S' : S' [subset or equal to] S} such that for [xi] [member of] [X.sup.[omega]] it holds [xi] [member of] F if and only if Inf (A; [xi]) [member of] [tau] where Inf(A; [xi]) is the set of all states s [member of] S through which the automaton A runs infinitely often when reading the input [xi]. Observe that S' = Inf(A; [xi]) holds for a subset S' [subset or equal to] S if and only if

1. there is a word u [member of] [X.sup.*] such that [delta]([s.sub.0]; u) [member of] S', and

2. for all s, s' g S' there are non-empty words w, v g [X.sup.*] such that [delta](s, w) = s' and [delta](s', v) = s.

Such sets were referred to as essential sets [Wag79] or loops [Sta97, Section 5.1].

Thus, to ease our notation, unless stated otherwise in the sequel we will assume all automata to be initially connected, that is, S = {[delta]([s.sub.0]; w) : w [member of] [X.sup.*]} and the tables T to be contained in the set of loops {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]}.

The [omega]-language F = {[xi] : Inf(A; [xi]) [member of] T} is the disjoint union of all sets [F.sub.S'] = {[xi] : Inf(A; [xi]) = S'} where S' [member of] T.

We are going to split F into smaller mutually disjoint parts. Let A = (X; S; [s.sub.0]; [delta]) be fixed. We refer to a word v [member of] [X.sup.*] as (s; S')-loop completing if and only if

1. v is not the empty word,

2. [delta](s, v) = s and {[delta](s, v') : v' [??] v} = S', and

3. {[delta](s, v') : v' [??] v"} c S' for all proper prefixes v" [??] v with [delta](s, v") = s. and we call a word w [member of] [X.sup.*] (s; S')-loop entering provided

1. [delta]([s.sub.0]; w) = s and

2. if w = w' x x for some x [member of] X then [delta]([s.sub.0]; w') [not member of] S'.

3.1 The general case

Denote by [V.sub.(s;S')] the set of all (s; S')-loop completing words and by [W.sub.(s;S')] the set of all (s; S')-loop entering words. Both languages are regular and constructible from the finite automaton A = (X; S; [s.sub.0]; [delta]). Moreover, [V.sub.(s;S')] is prefix-free, whereas [W.sub.(s;S')] need not be so. Nevertheless, every [xi] [member of] [F.sub.S'] has a unique representation [xi] = w x [v.sub.1] ... v ... where w [member of] [W.sub.(s;S')] and [v.sub.i] [member of] [V.sub.(s;S')]. Here the state s [member of] S' is uniquely determined as the state succeeding the last state [??] [not member of] S' in the sequence [([delta]([s.sub.0]; u)).sub.u[??][xi]]. Thus we obtain the following (see [Sta98a, Lemma 3]).

Lemma 4 (Decomposition Lemma) Let A = (X; S; [s.sub.0]; [delta]) be a finite automaton, T [subset or equal to] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]} be a table and let F = {[xi] : Inf(A; [xi]) [member of] T}. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

and the sets w x [V.sup.[omega].sub.(s;S')] are pairwise disjoint.

As an immediate consequence of the Decomposition Lemma we obtain that every regular [omega]-language has the form [[universal].sup.n.sub.i=1] [W.sub.i] x [V.sup.[omega].sub.i] where [W.sub.i], [V.sub.i] are regular languages (see [Buc62, PP04, Sta97] or [Tho90]). The converse is also true, that is, if W [subset or equal to] [X.sup.*] and F, E [subset or equal to] [X.sup.[omega]] are regular then also [W.sup.[omega]], W x E and E [union] F are regular [omega]- languages. Note, however, that the representation of Eq. (3) is much finer, since it splits a regular [omega]-language F = [[universal].sup.n.sub.i=1] [W.sub.i] x [V.sup.[omega].sub.i] into mutually disjoint parts w x [V.sup.w.sub.i], w [member of] [W.sub.i], i [member of] {1, ..., n}, where, additionally, the languages [V.sub.i] are prefix-free.

3.2 Decomposition according to Hausdorff measure

Next we are going to construct, depending on the automaton A = (X; S; [s.sub.0]; [delta]), a subset F' of the set F in Eq. (3) on which the Hausdorff measure [L.sub.[alpha]] is concentrated. To this end we need some properties of the measure [L.sub.[alpha]] for regular [omega]-languages.

Since regular [omega]-languages are Borel sets in Cantor space (cf. [Sta97, Tho90]), [L.sub.[alpha]] is not only an outer measure but a measure on the class of regular [omega]-languages. Thus we have the following (cf. [Fal86]).

Propositions If [([F.sub.i]).sub.i[member of]N] is a family of mutually disjoint regular [omega]-languages then [L.sub.[alpha]]([[universal].sub.i[member of]N] [F.sub.i]) = [[summation].sub.i[member of]N] [L.sub.[alpha]]([F.sub.i]).

Moreover, the following are shown in [Sta93] and [MS94].

Proposition 6 ([Sta93, Theorem 4.7]) If F [subset or equal to] [X.sup.[omega]] is a non-empty regular [omega]-language and [alpha] = dim F then [L.sub.[alpha]](F) > 0.

Proposition 7 ([Sta93, Theorem 4.6],[MS94, Theorem 6]) Let V [subset or equal to] [X.sup.*] be regular and prefix-free. Then [L.sub.[alpha]]([V.sup.[omega]])= [L.sub.[alpha]](C ([V.sup.[omega]])).

From Eq. (3), Proposition 5 and Proposition 1.3 we obtain a formula for the Hausdorff measure [L.sub.[alpha]] (F) of F:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

The following lemma shows that several of the sets w x [V.sup.[omega].sub.s;S']) do not contribute to the measure [L.sub.[alpha]](F) of F.

Proposition 8 Let A = (X; S; [s.sub.0]; [delta]) be a finite automaton and [V.sub.(s;S')] [not equal to] 0. Then S" [subset] S' implies [V.sup.[omega].sub.(s;S")] [subset or equal to] C([V.sup.[omega].sub.(s;S')]).

Moreover, we have [L.sub.[alpha]] ([V.sup.[omega].sub.(s;S")]) = 0 for [alpha] = dim ([V.sup.[omega].sub.(s;S')]).

Proof: To prove the first assertion it suffices to show pref ([V.sup.[omega].sub.(s;S")]) [subset or equal to] pref ([V.sup.[omega].sub.(s;S')]).

Let [A.sub.s] := (X; S; s; [delta]). Then [zeta] [member of] [V.sup.[omega].sub.(s;S')]) if and only if Inf ([A.sub.S]; [zeta]) = S' and {[delta](s, u) : u [??] [xi]} [subset or equal to] S'. Consequently, for v [member of] [V.sup.[omega].sub.(s;S')] and [xi] [member of] [V.sup.[omega].sub.(s;S')] we have Inf([A.sub.S]; v x [xi]) = S' whence [V.sup.*.sub.(s;S")] x [V.sup.*.sub.(s;S')] = [V.sup.*.sub.(s;S')] and thus Pref ([V.sup.*.sub.(s;S")]) [subset or equal to] Pref([V.sup.*.sub.(s;S')]).

As [V.sup.[omega].sub.(s;S")] and [V.sup.[omega].sub.(s;S')] are disjoint subsets of C([V.sup.*.sub.(s;S")]) the second assertion follows from the first one and Proposition 7.

Proposition 8 shows that for an [omega]-language F accepted by an automaton A = (X; S; [s.sub.0]; [delta]) and a table T [subset or equal to] {Inf (A; [epsilon]) : [xi] [member of] [X.sup.[omega]]} the measure [L.sub.[alpha]] (F) for [alpha] = dim F is concentrated only on subsets w x [V.sup.[omega].sub.(s;S')] for which S' is maximal w.r.t. set inclusion in T.

If [alpha] = dim F and we choose among the maximal sets S' [member of] T those for which [L.sub.[alpha]] (w x [V.sup.[omega].sub.(s;S')]) > 0 we eliminate all sets w x [V.sup.[omega].sub.(s;S')] with [L.sub.[alpha]](w x [V.sup.[omega].sub.(s;S')]) = 0 in Eq. (3) and obtain the following.

Theorem 9 Let A = (X; S; [s.sub.0]; [delta]) be a finite automaton, T [subset or equal to] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]} be a table, F = {[xi] : Inf (A; [xi]) [member of] T} and [alpha] = dim F.

If S := {S' : S' [member of] T [conjunction] [there exists]s (s [member of] S' [disjunction] [L.sub.[alpha]] ([V.sup.[omega].sub.(s;S')]) > 0)} the [omega]-language F' = {[xi] : Inf(A; [xi]) [member of] S} satisfies F' [subset or equal to] [subset or equal to] F and [L.sub.[alpha]](F) = [L.sub.[alpha]](F').

Moreover, the [omega]-language F' has a decomposition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

where [L.sub.[alpha]] (w x [V.sup.[omega].sub.(s;S')]) > 0 for all w x [V.sup.[omega].sub.(s;S')].

3.3 The case of closed [omega]-languages

In [SW74, Wag79] it was observed that the tables T of finite automata A = (X; S; [s.sub.0]; [delta]) accepting regular [omega]-languages closed in Cantor topology have the following simple structure.

Lemma 10 Let A = (X; S; [s.sub.0]; [delta]) be an initially connected finite automaton and let T [subset or equal to] {Inf(A; [xi]): [xi] [member of] [X.sup.[omega]]} be a table such that the [omega]-language F = {[xi] : Inf(A; [xi]) [member of] T} is closed. Then T satisfies the following properties.

1. If S' [member of] T, S" [member of] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]} and S' [intersection] S" [not equal to] 0 then S' U S" [member of] T.

2. If S' [member of] T, S" [member of] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]} and [delta](s", v) [member of] S' for some s" [member of] S" and v [member of] [X.sup.*] then S" [member of] T.

Informally speaking, Condition 1 of Lemma 10 shows that the table T is fully determined by the automaton A and its strongly connected components (SCCs), that is, subsets S' [member of] T satisfying the condition [for all]s [for all]s' (s, s' [member of] S' [right arrow] [there exists]w [there exists]v(w [not equal to] e [not equal to] v [conjunction] [delta](s', w) = s' [conjunction] [delta](s', v) = s)). In connection with Proposition 8 one observes that strongly connected components are maximal sets in {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]}.

Condition 2 implies that we can partition the set of states into an accepting part [S.sub.+] := {s : [there exists]S' [there exists]v(S' [member of] T [conjunction] v [member of] [X.sup.*] [conjunction] [delta](s, v) [member of] S')} and a rejecting part [S.sub.-] := S \ [S.sub.+] such that F = {[xi] : Inf(A; [xi]) [subset or equal to] [S.sub.+]}.

As we shall see in the following theorem among the strongly connected components S' [subset or equal to] [S.sub.+] the terminal ones play a special role. A similar observation was made in [MS94, Section 3] in connection with the calculation of the Hausdorff measure of closed regular [omega]-languages. Here we call a strongly connected component S' [member of] T terminal in T provided [delta](s,v) [member of] S' or [delta](s, v) [member of] [S.sub._] for s [member of] S' and arbitrary v [member of] [X.sup.*].

Theorem 11 Let A = (X; S; [s.sub.0]; [delta]) be an initially connected finite automaton and let T [subset or equal to] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]]} be a table such that the u-language F = {[xi] : Inf(A; [xi]) [member of] T} is closed. Let [??] [subset or equal to] T be the set of all strongly connected components terminal in T and F' = {[xi] : Inf(A; [xi]) [member of] [??]}.

Then F' [subset or equal to] [[universal].sub.S'[member of][??]] [[universal].sub.s[member]S'] [W.sub.(s;s')] x C([V.sup.[omega].sub.(s;S')) [subset or equal to] F = C(F').

Moreover, if s = [delta]([s.sub.0], w) [member of] S', for some S' [member of] [??], then w x [X.sup.[omega]] [intersection] F = w x C([V.sup.[omega].sub.(s;S')).

Proof: Obviously, F' [subset or equal to] F. First we show that F [subset or equal to] C(F'). Let [xi] [member of] F. Then S" = Inf(A; [xi]) [member of] T. Choose some s" G S". Since the automaton is finite, there are a terminal strongly connected component S' [member of] [??], a state s' [member of] S' and a v [member of] [X.sup.*] such that [delta](s", v) = s'. Consider the set pref([xi]; s") := {u : u [??] [xi] [conjunction] [delta]([s.sub.0], u) = s"}. Then pref (pref([xi]; s")) = pref([xi]).

Let w [member of] [X.sup.*] \ {e} satisfy [delta](s', w) = s' and {[delta](s', w') : w' [??] w} = S'. Then Inf(A; [uvw.sup.[omega]]) = S' for every u [member of] pref([xi]; s"), that is, pref ([xi]) [subset or equal to] pref (F').

Next observe that in view of Lemma 4 we have F' = [[universal].sub.S'[member of][??]] [[universal].sub.s[member of]s'] [W.sub.(s;S')] x [V.sup.[omega].sub.(s;S')]. Then the inclusion relations follow from F' [subset or equal to] [subset or equal to] and the fact that F is closed.

For the proof of second assertion it suffices to show w x [V.sup.[omega].sub.(s;S')] [subset or equal to] F [intersection] w x [X.sup.[omega]] [subset or equal to] w x C([V.sup.[omega].sub.(s;S')]). If [xi] [member of] w x [V.sup.[omega].sub.(s;S')] then Inf (A; [xi]) = S' whence [xi] [member of] F [intersection] w x [X.sup.[omega]].

Let [xi] [member of] F [intersection] w x [X.sup.[omega]]. Since s = [delta]([s.sub.0], w) [member of] S' and S' is a terminal strongly connected component, Inf (A; [xi]) [subset or equal to] [S.sub.+] implies {[delta]([s.sub.0], w x u) : w x u [??] [xi]} [subset or equal to] S'. As S' is a strongly connected component, for every u, w x u [??] [xi], there is a u' such that [delta]([s.sub.0], w x u x u') = [delta]([s.sub.0], w) = s and {[delta]([s.sub.0], w x u") : u" [??] u x u'} = S'. This shows pref([xi]) [subset or equal to] pref(w x [V.sup.[omega].sub.(s;S')]), that is, [xi] [member of] C(w x [V.sup.[omega].sub.(s;S')]) = w x C([V.sup.[omega].sub.(s;S')]).

4 Results on Hausdorff Measure

4.1 Sets of locally positive measure

Theorem 12 If F [subset or equal to] [X.sup.[omega]] is a regular [omega]-language, [alpha] = dim F, F has locally positive [alpha]-dimensional measure then [L.sub.[alpha]](C(F)) = [L.sub.[alpha]](F).

If, moreover, [alpha] = dim F = dim C(F) then [subset or equal to] (F) has locally positive [alpha]-dimensional measure.

Proof: It suffices to show that [L.sub.[alpha]](C(F)) > [L.sub.[alpha]](F) implies [L.sub.[alpha]](F) = [infinity].

From Theorem 9 we know that F contains a regular [omega]-language F' = [[universal].sup.n.sub.i=1] [W.sub.i] x [V.sup.[omega].sub.i] with [L.sub.[alpha]] (F) = [L.sub.[alpha]](F') where the sets [W.sub.i], [V.sub.i] are regular, the [V.sub.i] are prefix-free with [L.sub.[alpha]]([V.sup.[omega].sub.i]) > 0, and the sets w x [V.sup.[omega].sub.i], w [member of] [W.sub.i], i [member of] {1, ..., n}, are mutually disjoint.

Assume [infinity] [greater than or equal to] [L.sub.[alpha]](C(F)) > [L.sub.[alpha]](F). Since F has locally positive [alpha]-dimensional measure, by Proposition 2 pref(F') = pref(F) whence C(F') = C(F).

If pref ([xi]) [subset or equal to] pref ([W.sub.i] x [V.sup.[omega].sub.i]) then there is a w [member of] [W.sub.i] such that pref ([xi]) [subset] pref ([W.sub.i]) [subset or equal to] w x pref ([V.sub.[omega].sub.i]) or pref ([xi]) [subset or equal to] pref ([W.sub.i]). This shows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [L.sub.[alpha]](w x C([V.sup.[omega].sub.i])) = [L.sub.[alpha]](w x [V.sup.[omega].sub.i]) the assumption [L.sub.[alpha]](C(F)) > [L.sub.[alpha]](F) implies that [L.sub.[alpha]]({[xi] : pref ([xi]) C pref ([w.sub.i])}) > 0 for some i [member of] {1, ..., n} which in view of Proposition 1.2 yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [W.sub.i] is regular, there is a k [member of] N such that for every v [member of] pref ([W.sub.i]) there is a w [member of] [W.sub.i] with v [??] w and [absolute value of w] - [absolute value of v] [less than or equal to] k. Thus [??] and we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The additional assertion follows from 0 < [L.sub.[alpha]] F [intersection] w x [X.sup.[omega]] [greater than or equal to] [L.sub.[alpha]](C(F) [intersection] w x [X.sup.[omega]]) for w [member of] pref (F).

The following example shows that the additional assertion need not be true for dim F < dimC(F).

Example 1 Let X = {0,1}, [F.sub.1] = [{0,1}.sup.*] x [0.sup.[omega]] and [F.sub.2] := [0.sup.[omega]] [union] 1 x [{0,1}.sup.*] x [0.sup.[omega]]. Then C([F.sub.1]) = [{0,1}.sup.[omega]] and [subset or equal to] ([F.sub.2]) = [0.sup.[omega]] [union] 1 x [{0,1}.sup.[omega]]. Then 0 = dim [F.sub.i] < dim C ([F.sub.i]) = 1 for i = 1,2, C([F.sub.1]) has locally positive 1-dimensional measure whereas, since [L.sub.1]([F.sub.2] [intersection] 0 x [{0,1}.sup.*]) = 0, C([F.sub.2]) has not.

As an immediate consequence we obtain the following.

Corollary 13 If F [subset or equal to] [X.sup.[omega]] is a regular [omega]-language, [alpha] := dim F, F has locally positive [alpha]-dimensional measure and [L.sub.[alpha]](C(F) \ F) > 0 then [L.sub.[alpha]](F) = [infinity].

In case [L.sub.[alpha]](F) = [infinity] the measure of the difference [L.sub.[alpha]](C(F) \ F) may be finite or infinite.

Example 2 Let X = {0,1} and [F.sub.1] := [0.sup.*] x [1.sup.[omega]] and [F.sub.2] := [0.sup.*] x [1.sup.*] x [0.sup.[omega]]. Both sets are countable, thus dim [F.sub.1] = dim [F.sub.2] = 0. We have C([F.sub.1]) = [0.sup.[omega]] [union] [0.sup.*] x [1.sup.[omega]] and C([F.sub.2]) = [0.sup.*] x [1.sup.[omega]] [subset] [0.sup.*] x [1.sup.*] x [0.sup.[omega]], and, consequently, [L.sub.0](C([F.sub.1]) \ [F.sub.1]) = [L.sub.0]([0.sup.[omega]]) = 1 and [L.sub.0] (C([F.sub.2]) \ [F.sub.2]) = [L.sub.0]([0.sup.*] x [1.sup.[omega]]) = [infinity].

In Theorem 12 the hypothesis that F has locally positive [alpha]-dimensional measure is essential. We give an example.

Example 3 Let X = {0,1} and F := [F.sub.1] [union] [F.sub.2] where [F.sub.1] = [(0 x {0, 1}).sup.[omega]] is a closed set and [F.sub.2] = [(1 x {0,1}).sup.[omega]] x [(10).sup.[omega]].

Then [L.sub.[alpha]](F [intersection] 1 x [{0,1}.sup.[omega]]) = 0 for [alpha] > 0, since [F.sub.2] is countable. Moreover, C(F) = [(0 x {0,1}).sup.[omega]] [union] [(1 x {0,1}).sup.[omega]] and one easily calculates dim F = dimC(F) = 1/2, [L.sub.1/2](F) = 1/[square root of 2] > 0 and [L.sub.1/2](C(F)) = 2 x [L.sub.1/2](F) = [square root of 2].

From Proposition 3 and Theorem 12 we obtain the following relationship for the Hausdorff measure of regular [omega]-power languages.

Corollary 14 Let W [subset or equal to] [X.sup.*]. If [W.sup.[omega]] is a regular [omega]-language and a = dim [W.sup.[omega]] then

[L.sub.[alpha]](C([W.sup.[omega]])) = [L.sub.[alpha]](C([W.sup.[omega]]) .

Corollary 14 and, consequently, Theorem 12 are not valid for non-regular [omega]-languages. In [Sta05, Section 3.3] examples of prefix-free non-regular languages W fulfilling various relationships between [L.sub.[alpha]]([W.sup.[omega]]) and [L.sub.[alpha]](C ([W.sup.[omega]])) are given.

As a further application of Theorem 12 we derive a result which is in some sense a converse to Proposition 2. It shows that for special closed regular [omega]-languages F we can find a subset of the form of Eq. (5) having the same measure and the same closure as F. Here we use the approach of Theorem 11.

Proposition 15 Let A = (X; S; [s.sub.0]; [delta]) be an initially connected finite automaton and let T [subset or equal to] {Inf(A; [xi]) : [xi] [member of] [X.sup.[omega]] } be a table such that the [omega]-language F' = {[xi] : Inf(A; [xi]) G T} is closed. Let T [subset or equal to] T be the set of all strongly connected components terminal in T and F = {[xi] : Inf(A; [xi]) [member of] [??]}.

If dim F' = [alpha] and F' has locally positive [alpha]-dimensional measure then F' = C(F) and [L.sub.[alpha]](F') = [L.sub.[alpha]](F).

Proof: The first assertion was already proved in Theorem 11. Then, in view of Theorem 12, it suffices to show that F has locally positive [alpha]-dimensional measure, that is, [L.sub.[alpha]](F [intersection] w x [X.sup.[omega]]) > 0 for all w [member of] pref (F') = pref (F).

Let v [member of] pref (F) and consider the identity F = [[universal].sub.S'[member of][??]] [[universal].sub.s[member of]S'] [W.sub.(s;S')] x [V.sup.[omega].sub.(s-S')] derived in the proof of Theorem 11.

Then there are an S' [member of] [??] and an s [member of] S' such that v [member of] pref ([W.sub.(s;S')]) or v [member of] [W.sub.(s;S')] x pref ([V.sup.*.sub.(s;S')]).

In both cases v x u [member of] [W.sub.(s;S')] x [V.sup.*.sub.(s;S')] for some u [member of] [X.sup.*], in particular s = [delta]([s.sub.0], v x u).

By Theorem 11 we have F'[intersection] v x u x [X.sup.[omega]] = v x u x C([V.sup.[omega].sub.(s;S')]) and, since v x u x [V.sup.*.sub.(s;S')] [subset or equal to], with Proposition 8 we obtain 0 < [L.sub.[alpha]](F' [intersection] v x u x [X.sup.[omega]]) = [L.sub.[alpha]](v x u x V(";S')) < [L.sub.[alpha]](F [intersection] v x [X.sup.[omega]]). Thus Theorem 12 proves the assertion.

4.2 The measure of sets residual in its closure

This last part shows that an [omega]-language having a regular closure and which is topologically large in its closure has the same measure as its closure.

Before we proceed to the presentation of the results we have to introduce some necessary prerequisites concerning the topology of the Cantor space.

As usual, a countable intersection of open sets is referred to as a [G.sub.[delta]]-set. Moreover, we call a set F nowhere dense in E provided C(E\C(F)) = C(E), that is, if C(F) does not contain a nonempty subset of the form E [intersection] w x [X.sup.[omega]], and a subset F is referred to as of first Baire category in E if F is a countable union of sets nowhere dense in E. If E is closed and F is of first Baire category in E then E \ F is referred to as residual in E. In particular, [G.sub.[delta]]-sets E in Cantor space are residual in C(E).

The following lemma shows a connection between Hausdorff dimension and relative density of regular [omega]-language.

Lemma 16 ([Sta98b, Theorem 8]) Let E [subset or equal to] [X.sup.[omega]] be a regular [omega]-language which is closed in Cantor space, [alpha] = dim E and let E have finite and locally positive [alpha]-dimensional measure.

Then every regular [omega]-language F [subset or equal to] E is of first Baire category in E if and only if [L.sub.[alpha]](F) = 0.

This much preparatory apparatus leads to the following result.

Theorem 17 Let E [subset or equal to] [X.sup.[omega]] be an [omega]-language which is a countable intersection of regular [omega]-languages, residual in C(E) and let C(E) be regular. If [alpha] = dim C(E), [L.sub.[alpha]](C(E)) < [infinity], and C(E) has locally positive [alpha]-dimensional measure then [L.sub.[alpha]] (C(E)) = [L.sub.[alpha]](E).

Proof: Observe that C(E) is a regular [omega]-language. Since E is supposed to be residual in C(E), C(E) \ E is of first Baire category in C(E), and, since E is a countable intersection of regular [omega]-languages, say E = [[??].sub.i[member of]N] [F.sub.i], the difference C(E) \ E = [[universal].sub.i[member of]N](C(E) \ [F.sub.i]) is a countable union of regular [omega]-languages C(E) \ [F.sub.i], each of which is of first Baire category in C(E). Then according to Lemma 16 [L.sub.[alpha]](C(E)\[F.sub.i]) = 0, and the assertion follows.

Using Proposition 15 we can drop the requirement [L.sub.[alpha]](C(E)) < [infinity] in Theorem 17.

Theorem 18 Let E [subset or equal to] [X.sup.[omega]] be an [omega]-language which is a countable intersection of regular [omega]-languages, residual in C(E) and let C(E) be regular. If [alpha] = dim C(E) and [subset or equal to] (E) has locally positive [alpha]-dimensional measure then [L.sub.[alpha]](C(E)) = [L.sub.[alpha]](E).

Proof: The case [L.sub.[alpha]](C(E)) < [infinity] is proved in Theorem 17. Let [L.sub.[alpha]](C(E)) = to.

Proposition 15 shows that [L.sub.[alpha]](E') = [infinity] for the set E' = [[universal].sub.S'[member][??]] [[universal].sub.s[member of]S'] [W.sub.(s;S')] x [V.sup.w.sub.(s;S')] derived via Theorem 11 from a finite automaton accepting C(E). Then, similarly as in the proof of Theorem 12 one finds a set [W.sub.(s;S')] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Again, using Theorem 11 one has [W.sub.(s;S')] x C([V.sup.w.sub.(s;S')]) [subset or equal to] C(E), and, moreover, w x C([V.sup.[omega].sub.(s;S')]) = C(E) [intersection] w x [X.sup.[omega]] for w [member of][sub.W(s;S")].

Now, Propositions 3 and 7 show [L.sub.[alpha]] (C(E) [intersection] w ? [X.sup.[omega]]) < [infinity] and we can apply Theorem 17. This yields [L.sub.[alpha]](C(E) [intersection] w x [X.sup.[omega]]) = [L.sub.[alpha]] (E [intersection] w x [X.sup.[omega]]) = [r.sup.-[alpha] x [absolute value of w]] x [L.sub.[alpha]]([V.sup.[omega].sub.(s;S')]). Summing over w [member of] [W.sub.(s;S')] and taking into account that [L.sub.[alpha]]([V.sup.[omega].sub.(s;S')]) > 0 we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The Theorems 17 and 18 can be applied also to non-regular [omega]-languages. We give a simple example.

Example 4 Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the set of all [omega]-words which contain every word as an infix. Those [omega]-words are referred to as disjunctive [JST83] or rich [Sta98b]. E is [G.sub. [delta]]- set in Cantor space, hence residual in C(E) = [X.sup.[omega]].

We have dim C(E) = 1 and obtain [L.sub.1](C(E)) = Li(E) = 1.

The condition that E be residual in C(E) is really essential as the following example shows.

Example 5 Let X = {0,1} and E = [{0,1}.sup.*] x [0.sup.[omega]] = [[??].sub.n[member of]N] [{0,1}.sup.*] x [{[0.sup.n]1, 0}.sup.[omega]] which is an intersection of regular [omega]-languages [{0,1}.sup.*] x [{[0.sup.n]1, 0}.sup."].

Then C(E) = [{0,1}.sup.[omega]] and [alpha] = dimC(E) = 1, [L.sub.1](C(E) [intersection] w x [{0,1}.sup.[omega]]) > 0 for all w [member of] [{0,1}.sup.*] but, as E is countable, dim E = 0 and hence [L.sub.1] (E) = 0.

Acknowledgements

The author would like nto thank Klaus W. Wagner and the two referees for several helpful comments.

References

[Arn83] Andre Arnold. Rational u-languages are nonambiguous. Theoret. Comput. Sci., 26(1-2):221-223, 1983.

[Ban89] Christoph Bandt. Self-similar sets. III. Constructions with sofic systems. Monatsh. Math., 108(2-3):89-102, 1989.

[Buc62] J. Richard Buchi. On a decision method in restricted second order arithmetic. In Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr .), pages 1-11. Stanford Univ. Press, Stanford, Calif., 1962.

[Edg08] Gerald Edgar. Measure, topology, and fractal geometry. Undergraduate Texts in Mathematics. Springer, New York, second edition, 2008.

[Fal86] Kenneth Falconer. The geometry of fractal sets, volume 85 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1986.

[Fal90] Kenneth Falconer. Fractal geometry. John Wiley & Sons Ltd., Chichester, 1990.

[JST83] Helmut Jiirgensen, Huei Jan Shyr, and Gabriel Thierrin. Disjunctive u-languages. Elektron. Informationsverarb. Kybernet., 19(6):267-278, 1983.

[McN66] Robert McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, 9:521-530, 1966.

[MS94] Wolfgang Merzenich and Ludwig Staiger. Fractals, dimension, and formal languages. RAIRO Inform. Theor. Appl., 28(3-4):361-386, 1994.

[MW88] R. Daniel Mauldin and Stanley C. Williams. Hausdorff dimension in graph directed constructions. Trans. Amer. Math. Soc., 309(2):811-829, 1988.

[PP04] Dominique Perrin and Jean-Eric Pin. Infinite Words, volume 141 of Pure and Applied Mathematics. Elsevier, Amsterdam, 2004. ISBN 0-12-532111-2.

[Sta93] Ludwig Staiger. Kolmogorov complexity and Hausdorff dimension. Inform. and Comput., 103(2):159-194, 1993.

[Sta97] Ludwig Staiger. [omega]-languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal [L.sub.[alpha]]nguages, volume 3, pages 339-387. Springer-Verlag, Berlin, 1997. Beyond words.

[Sta98a] Ludwig Staiger. The Hausdorff measure of regular [omega]-languages is computable. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (66):178-182, 1998.

[Sta98b] Ludwig Staiger. Rich [omega]-words and monadic second-order arithmetic. In Mogens Nielsen and Wolfgang Thomas, editors, Computer science logic (Aarhus, 1997), volume 1414 of Lecture Notes in Computer Science, pages 478-490. Springer-Verlag, Berlin, 1998. Selected papers from the 11th International Workshop (CSL '97) held at the 6th Annual Conference of the European Association for Computer Science Logic (EACSL) at the University of Aarhus, Aarhus, August 23-29, 1997.

[Sta05] Ludwig Staiger. Infinite iterated function systems in Cantor space and the Hausdorff measure of [omega]-power languages. Internat. J. Found. Comput. Sci., 16(4):787-802, 2005.

[Sta14] Ludwig Staiger. Two theorems on the Hausdorff measure of regular [omega]-languages. In Vasco Brattka, Hannes Diener, and Dieter Spreen, editors, Logic, Computation, Hierarchies, volume 4 of Ontos Mathematical Logic, pages 383-392. de Gruyter, Boston, Mass., 2014.

[SW74] Ludwig Staiger and Klaus Wagner. Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regularer Folgenmengen. Elektron. Informationsverarb. Kybernetik, 10(7):379-392, 1974.

[Tho90] Wolfgang Thomas. Automata on infinite objects. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 133-192. North Holland, Amsterdam, 1990.

[VV06] Daniele Varacca and Hagen Volzer. Temporal logics and model checking for fairly correct systems. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 389-398. IEEE Computer Society, 2006.

[Wag79] Klaus Wagner. On w-regular sets. Inform. and Control, 43(2):123-177, 1979.

Ludwig Staiger

Institut fur Informatik, Martin-Luther-Universitat Halle-Wittenberg, Germany

* The results of this paper were presented at the Dagstuhl-Seminar "Topological and Game-Theoretic Aspects of Infinite Computations", Schloss Dagstuhl, 29.06.-04.07.2008. A preliminary version appeared in [Sta14].

(i) See also a more recent algebraic decomposition in [PP04, Chapter II, Theorem 9.3].

(ii) We use the same symbol S to denote the usual extension of the function S to S x [X.sup.*].

received 14th Apr. 2014, revised 1st Apr. 2015, 5th May 2015, accepted 5th May 2015.
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Staiger, Ludwig
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Jan 1, 2015
Words:7224
Previous Article:A note on a recent attempt to improve the Pin-Frankl bound.
Next Article:Classification of skew translation generalized quadrangles, I.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters