Avoiding cross-bifix-free binary words
- PDF / 747,246 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 182 Views
Avoiding cross-bifix-free binary words Stefano Bilotta · Elisabetta Grazzini · Elisa Pergola · Renzo Pinzani
Received: 20 December 2011 / Accepted: 7 January 2013 / Published online: 25 January 2013 © Springer-Verlag Berlin Heidelberg 2013
Abstract In this paper we study the construction and the enumeration of binary words in {0, 1}∗ having more 1’s than 0’s and avoiding a set of cross-bifix-free patterns. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words having more 1’s than 0’s and then kills those containing the forbidden patterns. Finally, we give the generating function of such words according to the number of ones.
1 Introduction Let F ⊂ {0, 1}∗ be the set of binary words ω such that |ω|0 ≤ |ω|1 , for any ω ∈ F, |ω|0 and |ω|1 corresponding to the number of 0’s and 1’s in the word ω, respectively. A word ω = ω1 ω2 , . . . , ωk contains a pattern p = p0 , . . . , p−1 ∈ {0, 1} of length if there is an index i such that ωi ωi+1 , . . . , ωi+−1 = p0 p1 , . . . , p−1 . Otherwise, we say that ω avoids the pattern p, or that p is a forbidden pattern for ω. The problem of determining the appearance of a fixed pattern in long sequences of observation is interesting in many scientific problems.
S. Bilotta · E. Grazzini (B) · E. Pergola · R. Pinzani Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Viale G.B. Morgagni 65, 50134 Firenze, Italy e-mail: [email protected] S. Bilotta e-mail: [email protected] E. Pergola e-mail: [email protected] R. Pinzani e-mail: [email protected]
123
158
S. Bilotta et al.
For example, in the area of computer network security, the detection of intrusions, which are becoming increasingly frequent, is very important. Intrusion detection is primarily concerned with the detection of illegal activities and acquisitions of privileges that cannot be detected with information flow and access control models. There are several approaches to intrusion detection, but recently this subject has been studied in relation to pattern matching (see [1,14,19]). Moreover, in the area of computational biology it could be interesting to detect the occurrences of a particular pattern in a genomic sequence over the alphabet {A, G, C, T }, see for instance [23,25]. These kinds of applications are interested in the study concerning both the enumeration and the construction of particular words avoiding a given pattern over an alphabet Σ. If we consider the set of binary words without any restriction then the binary words avoiding a fixed pattern p = p0 , . . . , ph−1 ∈ {0, 1}h constitute a regular language and can be enumerated by using classical results obtaining rational generating functions (see, e.g., [15,16,18,24]). When the restriction to words with no more 0’s than 1’s is valid, the la
Data Loading...
