Blind Counter Automata on ω-words - PDF

Description
Fundamenta Informaticae XX (2007) IOS Press Blind Counter Automata on ω-words Henning Fernau Fachbereich IV, Abteilung Informatik, Universität Trier, D Trier, Germany Ralf

Please download to get full document.

View again

of 14
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Speeches

Publish on:

Views: 13 | Pages: 14

Extension: PDF | Download: 0

Share
Transcript
Fundamenta Informaticae XX (2007) IOS Press Blind Counter Automata on ω-words Henning Fernau Fachbereich IV, Abteilung Informatik, Universität Trier, D Trier, Germany Ralf Stiebe Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg PF-4120, D Magdeburg, Germany Abstract. This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on ω-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of ω-languages of the form L = 1 i k U ivi ω, where U i, V i are finitary blind multicounter languages. Keywords: blind counter machines, ω-languages, closure properties 1. Introduction In this paper, we give some results concerning blind counter automata when used as acceptors for ω-languages. This is interesting, since such devices are in many respects similar to the regular case, which has found many nice applications in the case of ω-languages, as well. While automata equipped with partially blind counters (a little bit confusingly under the name of blind counters) have been examined as acceptors for ω-languages in the fundamental study of Engelfriet and Hoogeboom [2], as well as in topology-oriented research [1, 10], this has not been the case with blind counters, since the empty storage acceptance condition does not fit into their framework. We distinguish two ways of accepting ω-words by multicounter automata, depending on whether or not we expect the counters to be all synchronized upon reaching a final state. We derive complete, dense, infinite hierarchies (parameterized by the number of counters) in both cases. Furthermore, 2 H. Fernau, R. Stiebe / Blind Counter Automata on ω-words we study representations of the form L = 1 i k U iv ω i, where the U i and V i are finitary blind multicounter languages, i.e., the ω-kleene closure of blind multicounter languages. We also compare these hierarchies inter alia. In a separate section, we discuss (Boolean) closure properties of all the ω-language families. 2. Definitions and Examples For basics in automata theory, we refer the reader to [12, 16]. The theory of ω-languages is nicely covered in [19]. X is the free monoid over X, e X denotes the empty word, X ω is the set of ω-words over X. denotes the prefix relation in X, where the right-hand side might also refer to an ω-word. Let x a denote that number of occurrences of a in x. For some tuple t, π j (t) denotes the projection of t on its jth component. 0 is a multidimensional all-zero-vector; e i is the unit-vector whose ith component is one, i.e., π i ( e j ) = 1 if and only if i = j. The number of dimensions of 0 and of e i will be seen from the context. Since definitions of counter automata are not standardized in the literature, we have to make the notions we use precise below, mostly following [11]. A blind k-counter machine M = (Q, X, δ, q 0, Q f, k) consists of a finite set Q of states, a designated initial state q 0, a designated subset Q f of final or accepting states, a finite input alphabet X and a finite transition relation δ Q (X {e}) Q Z k. Intuitively, this means that δ describes what M should do when being in a specific state q Q, when reading the current input symbol x X (or ignoring the input if x = e). The last two components of that product describe the reaction of M on the observed input; namely, M would then go (in the next step) into a specified successor state and add to the ith counter (1 i k) the integer given by the ith place of the last component. A configuration c of M is a member of Q X X Z k. The set of configurations is denoted by C(M). Especially, c 0 (w) = (q 0, e, w, 0) is the initial configuration for w and C f = Q f {(w, e, 0)} is the set of final configurations. Observe that we require here that all counters are zero at the end of a computation. In fact, this is the only way that such a machine may test the contents of its counters. If (q, a, q, x) δ and c = (q, v, aw, y) is a configuration of M, then we write (q, v, aw, y) M (q, va, w, y + x) =: c and say that a drives M from c into c. If a = e, this is an e-move. M is a relation on Q X X Z k. Its reflexive transitive closure is denoted by M. The language accepted by M is L(M) = {w X : c f C f (c 0 (w) M c f ) }. For c 0 (w) M c, we also say that w drives M into c. A sequence c 0(w) = c 0 M c 2 M M c n C f is called an accepting run of M on w. The family B k contains all languages that can be accepted by blind k-counter machines. When neglecting the number of counters, we get B = k 0 B k. When dealing with ω-words, a configuration has to be a tuple in Q X X ω Z k. Upon feeding an ω-word w = a 1 a 2 a 3 X ω into a blind counter machine, we naturally obtain an infinite H. Fernau, R. Stiebe / Blind Counter Automata on ω-words 3 sequence c 0 c 1 c 2 c 3... of configurations, with c 0 being the initial configuration and a i driving the automaton from configuration c i 1 into configuration c i. There are a number of ways to obtain ω-languages from a blind counter automaton M. In the following, we will discuss two modes of acceptance, combining the Büchi-condition for finite automata with blind counters. L ω (M): Accept all ω-words that drive M infinitely often through a particular final state, having all counters equal zero at the same time. This mode is called synchronous acceptance, since all acceptance conditions have to be met at the same time. The associated family of ω-languages accepted by blind k-counter automata will be denoted by B ω k. L ω,a (M): Accept all ω-words that drive M infinitely often through a particular final state, having each counter equal zero infinitely often. This mode is called asynchronous acceptance, since the acceptance conditions could be met independently of each other. The associated family of ω-languages asynchronously accepted by blind k-counter automata will be denoted by B ω,a k. More formally, an ω-word w = a 1 a 2 X ω, with a i X {e} is accepted by the blind k-counter machine M = (Q, X, δ, q 0, Q f, k) iff there exists a sequence of states q 0, q 1,... and a sequence of vectors y 0, y 1,... with y i Z k, such that for c 0 = c 0 (w) and such that c i 1 M c i for i 1, and c i = (q i 1, a 1... a i 1, a i a i+1..., y i ), i 1 1. in the synchronous acceptance mode, we find an infinite set J of natural numbers (indices) and a final state q f, such that: for all j J, (1) π 1 (c j ) = q f, and (2) π 4 (c j ) = 0, i.e., 1 κ k : π κ (π 4 (c j )) = 0; 2. in the asynchronous acceptance mode, we find infinite subsets J 0,..., J k, such that: (1) j J 0 : π 1 (c j ) is final, and (2) 1 κ k j J κ : π κ (π 4 (c j )) = 0. Often related is a representation via ω-powers: An ω-language L is said to be in K k iff we find blind k-counter languages V i and W i such that L = n i=1 V i Wi ω. In other words, K k is just the ω-kleene closure of B k. If we neglect the number of counters that are used, we arrive at the classes B ω, B ω,a and K. Example 2.1. For k 1, let X k = {a 1, a 2,..., a k, b 1, b 2,..., b k }. Consider the blind k-counter automaton M = ({q 0 }, X k, {(q 0, a i, q 0, e i ), (q 0, b i, q 0, e i ) : 1 i k}, q 0, {q 0 }). The languages and ω-languages accepted by M are L(M) = {w X k : w ai = w bi, for 1 i k}, L ω (M) = {w X ω k : {p w : p ai = p bi, for 1 i k} = }, L ω,a (M) = {w X ω k : {p w : p ai = p bi } =, for some 1 i k}. 4 H. Fernau, R. Stiebe / Blind Counter Automata on ω-words We close this section by showing how an accepting run on some word w can be turned into an accepting run on another word w. This technique will often be used to show that some language or ω-language cannot be accepted by blind multicounter automata. Consider an accepting run of a blind multicounter automaton on w. Let p = p 1 p 2 p 3 be a finite word such that w = pt, and after reading each of the prefixes p 1, p 1 p 2 and p 1 p 2 p 3, the automaton reaches the state z and the vectors x 1, x 1 + x 2 and x 1 + x 2 + x 3. Then there is an accepting run on w = p t with p = p 1 p 3 p 2 : Omit the transitions for p 2 and append them after p 3. The automaton reaches state z and vector x 1 + x 2 + x 3 after reading p, and then continues as in the run on w. We say that the loop (z, p 2, z, x 2 ) is deleted after p 1 and inserted after p 1 p 3. When dealing with ω-words, this insertion/deletion process is sometimes repeated infinitely often. 3. Hierarchy results The definitions of ω-languages by blind counter automata imply three natural hierarchies B ω 0 B ω 1 B ω 2, B ω,a 0 B ω,a 1 B ω,a 2, K 0 K 1 K 2. We will show that all these hierarchies are proper, that B ω and B ω,a are incomparable, and that Bi ω K i, for i 1. Notice that the properness of the corresponding finitary language hierarchy is well-known, see [11, 22]. In the case of regular ω-languages, that correspond to the case that k = 0, we can state as a wellknown result: Lemma 3.1. B ω 0 = B ω,a 0 = K 0. A slight modification of published proofs [19] (also in [16]) for the mentioned regular case exhibits: Lemma 3.2. k 0(B ω k K k). Let M = (Q, X, δ, q 0, Q f, k) be a k-counter-automaton that accepts the ω-language L = L ω (M). Derive from M the blind multicounter automata M q p = (Q, X, δ, p, {q}, k) accepting L q p X. We can show that L = q Q f L q q 0 (L q q) ω Namely, any ω-word w L drives M infinitely often through a specific final state q with all counters zero and can be hence decomposed as w = uv 1 v 2..., where u is taking M from its initial state into q, with all counters zero, and v j is taking M from q into q, all counters zero at the begining and at the end. Therefore, u L q q 0 and v j L q q for all j. Conversely, consider an ω-word w = uv 1 v 2... with u L q q 0 and v j L q q for all j, where q Q f is fixed. By definition of the Büchi acceptance condition, w L, since it drives M infinitely often into a final configuration. Hence, L K k. Lemma 3.3. L 1 = {a n b n n 1} ω / B ω. H. Fernau, R. Stiebe / Blind Counter Automata on ω-words 5 Assume to the contrary that there is a blind multicounter machine M with N states accepting L 1. Consider an accepting run on w = (a N b N ) ω. After reading the prefix p N+1 = (a N b N ) N+1, M has reached some configuration (z, x). Let B i be the i-th block of a s in p N+1, for 1 i N + 1. For any 1 i N + 1, the machine performs a loop reading a non-empty sequence a li in B i, moving from state z i to itself, and adding x i to the counters. By the pidgeonhole principle, there have to be indices 1 j k N + 1 such that z j = z k. Deleting the loop in block B j and inserting it in block B k, we reach the configuration (z, x) after reading the prefix p N+1 = (a N b N ) j 1 a N lj b N (a N b N ) k j 1 a N+lj b N (a N b N ) N+1 k. Thus, there is an accepting run for the omega-word p N+1 (an b N ) ω / L 1, contradicting our assumption. With a similar argument it can be shown that the ω-language L = {w {a, b} ω : p(p w p a p b )} cannot be accepted by any blind multicounter machine. Note that L is accepted by a deterministic partially blind 1-counter automaton. We can summarize our findings as follows: Theorem 3.1. k 0(B ω k K k). The inclusion turns into equality if and only if k = 0. Notice that this result contrasts not only to what is known about regular ω-languages, but also to what is known about context-free ω-languages [19]. It is well known (see, e.g., [21]) that any non-empty regular ω-language contains an ultimately periodic ω-word, and that the emptiness problem is decidable for finite Büchi automata. This can be directly transferred to the class K (and thus to B ω ). Theorem 3.2. Any non-empty ω-language in K contains an ω-word of the form st ω, where s and t are (finite) strings. Let L = n i=1 U ivi ω, for some n N and U i, V i being (finitary) blind k-counter languages. If L is non-empty, there has to be some i such that U i and V i are non-empty. Choose some s U i, t V i. Then, st ω L. Theorem 3.3. Given a blind multicounter automaton M, it is decidable whether L ω (M) is empty. Let M be a blind k-counter automaton. According to the proof of Lemma 3.2, we can effectively find blind k-counter automata M i, M i, such that L ω (M) = n L(M i) [L(M i )] ω. i=1 6 H. Fernau, R. Stiebe / Blind Counter Automata on ω-words Now, L ω (M) if and only if we can find an index i, 1 i n, such that L(M i ) and L(M i ) / {, {e}}. It is well-known that blind finitary k-counter languages have a decidable emptiness problem (based on their containment in partically blind finitary k-counter languages and the relation of the latter family to Petri net languages as exhibited in [11]). The second property can be reduced to this problem, as well, by noting that L = L(M i ) / {, {e}} for L X if and only if L X +, employing that blind k-counter languages are effectively closed under intersection with regular sets. Next, we discuss the relations between the acceptance modes. It will turn out that they are equivalent for one counter and incomparable for more than one counter. Lemma 3.4. B ω,a 1 B ω 1. Let M = (Q, X, δ, q 0, Q f, 1) be some blind 1-counter automaton, which accepts an ω-language L in asynchronous mode. A blind 1-counter automaton M = (Q {0, 1, 2}, X, δ, (q 0, 0), Q {1}, 1) synchronously accepting L is constructed in the following. To shorten our notations, for any ζ = (z, a, z, x) δ and any 0 i, j 2, let ζ i,j denote the transition ((z, i), a, (z, j), x). For such ζ, put ζ 0,0, ζ 0,1, and ζ 1,2 into δ. Moreover, if z / Q f, then ζ 2,2 δ, and if z Q f, then ζ 2,0 δ. Now consider an accepting run of M on some ω-word w. An accepting run of M starts with (q 0, 0) and proceeds as follows depending on the second component of the state. (z, 0): If M uses the transition ζ = (z, a, z, x), M applies ζ 0,0, if the counter does not reach the value 0; otherwise it applies ζ 0,1. (z, 1): If M uses the transition ζ = (z, a, z, x), M applies ζ 1,2. (z, 2): If M uses the transition ζ = (z, a, z, x), M applies ζ 2,2 if z is not accepting; otherwise it applies ζ 2,0. If M reaches infinitely often an empty counter and an accepting state, then M reaches infinitely often an accepting configuration. On the other hand, if we get from an accepting configuration in M to another accepting one, we have to pass an accepting state and a counter of zero in the corresponding run of M. Lemma 3.5. B ω 1 B ω,a 1. Let M = (Q, X, δ, q 0, Q f, 1) be some blind 1-counter automaton, which accepts an ω-language L (in synchronous mode). Without loss of generality assume q 0 Q f. A blind 1-counter automaton M = (Q, X, δ, q 0, Q f, 1) accepting L asynchronously is constructed as follows. For any transition (z, a, z, x) δ, δ contains the transition (z, a, z, 2x + d), where d is 0, if z Q f and z Q f, or z / Q f and z / Q f ; 1, if z Q f and z / Q f ; 1, if z / Q f and z Q f. H. Fernau, R. Stiebe / Blind Counter Automata on ω-words 7 Obviously, in a run of M, one reaches state z and counter contents 2x + y with y = 0 if z Q f and y = 1 if z / Q f, iff a run of M reaches state z and counter contents x. Remark 3.1. The reader might have wondered why we also admitted non-synchronization between reaching a final state and an empty counter in our definition of the asynchronous acceptance mode. So, she might have expected in our definition the following lines:... in the asynchronous acceptance mode, we find infinite subsets J 1,..., J k, such that: 1 κ k j J κ : π κ (π 4 (c j )) = 0 and π 1 (c j ) is final. The idea of having a sort of odd / even mode within the counters (as employed in the proof of the preceding lemma) proves that both definitions yield the same family of ω-languages. For more than one counter, the acceptance modes are incomparable. The first part of this relation is a consequence of the following remarkable result. Lemma 3.6. There is a non-empty language L B ω,a 2 such that L does not contain an ω-word of the form st ω. An example is the ω-language L = {w {a, b} ω : {p : p w p a = p b } = {p : p w p a = 2 p b } = }. Clearly, L is non-empty. Consider the blind 2-counter automaton M = ({q 0 }, {a, b}, δ, q 0, {q 0 }, 2) with δ = {(q 0, a, q 0, (1, 1)), (q 0, b, q 0, ( 1, 2))}. After reading a prefix p, the first counter is zero iff p a = p b, while the second counter is zero iff p a = 2 p b, i.e., L ω,a (M) = L. Now, suppose for contradiction that L contains some ω-word st ω. Set s = m, t = n, t a = n a, t b = n b. Assume that n a n b, and let N 0 = n a + m + 1. Any prefix of length at least m + n N 0 has the form st N t, where N N 0 and t is a prefix of t. By the chain of inequations st N t a t N a t N b + N t N b + n b + m st N t b it follows that p a = p b holds only for finitely many prefixes p. Similarly, if n a n b it can be shown that p a = 2 p b holds only finitely often. As an immediate consequence, we obtain Theorem 3.4. B ω,a 2 K (and B ω,a 2 B ω ). On the other hand, there are ω-languages that can be accepted synchronously, nut not asynchronously. Theorem 3.5. B ω 2 B ω,a. Consider the ω-language L = {w {a 1, b 1, a 2, b 2 } ω : {p : p w p a1 = p b1 p a2 = p b2 } = }. 8 H. Fernau, R. Stiebe / Blind Counter Automata on ω-words Obviously, L B ω 2. Now assume that L = L ω,a (M), for some blind k-counter machine M. Let N be the number of states of M. Consider an accepting run of M on w = (a N 1 a N 2 b N 1 b N 2 ) ω L. The basic idea is again to delete/insert loops in the accepting run on w to obtain an accepting run on some w / L. For the sake of simplicity, assume for the time being that this run does not contain a loop reading the empty word. (We shall show at the end of the proof how to deal with loops on the empty word.) For every block a N 1 and every block a N 2, the accepting run contains a loop. There are loops loop 1 = (z 1, a l1 1, z 1, x) and loop 2 = (z 2, a l2 2, z 2, y) that appear in infinitely many blocks. Let x = (x 1, x 2,..., x k ), y = (y 1, y 2,..., y k ). For 1 i k, there are integers (r i, s i ) (0, 0) such that r i x i + s i y i = 0 and r i 0 or (r i = 0 and s i 0). Let us first discuss the case r 1 0. When z 1 appears for the first time in a block of a 1 s, insert r 1 copies of loop 1. Continue the run as on w. If s 1 0, insert s 1 copies of loop 2 at the first appearance of z 2 in a block of a 2 s. Otherwise, remove the first s 1 appearances of loop 2, and continue as in the original run, until the next block of b 2 s is read. If r 1 = 0, insert s 1 copies of loop 2 the first time z 2 appears in a block of a 2 and continue as in the original run, until the next block of b 2 s is read. In either case, let p 0 be the prefix of w discussed so far, while p 0 is the prefix obtained from p 0 by the insertions/deletions. Starting with p 0 and p 0, we will construct inductively infinite sequences p 0 p 1 p 2 p j w and p 0 p 1 p 2 p j (the latter sequence defines w ) which satisfy the following conditions: If the accepting run on w reaches after reading p j the state z and counters contents (c 1,..., c k ), then for the derived run on p j, one finds: 1. p j a 1 = p j b 1 + r (j mod k)+1 l 1, p j a 2 = p b2 + s (j mod k)+1 l 2, 2. The state after reading p j is z. 3. The contents of the i-th counter is c i = c i + r (j mod k)+1 x i + s (j mod k)+1 y i ; in particular, c (j mod k)+1 = c (j mod k) For any q with p j q p j+1, holds q a1 q b1 or q a2 q b2. It is easy to verify that the claims are true for j = 0. Now assume that we have transformed a run on prefix p j to a run on p j such that the above conditions are satisfied. First of all, the run after p j is continued as the original run on w after p j, until an accepting state has been passed and counter (j mod k) + 1 has reached the value 0. As the original run on w is accepting, this is guaranteed to happen. Next, with d r,j
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks