On pattern frequency occurrences in a Markovian sequence

Author

Régnier, Mireille ; Szpankowski, Wojciech

Author_Institution

Inst. Nat. de Recherche en Inf. et Autom., Le Chesnay, France

fYear

1997

fDate

29 Jun-4 Jul 1997

Firstpage

310

Abstract

Consider a given pattern and a random text generated by a Markovian source of any order. We study the frequency of pattern occurrences in a random text when overlapping copies of the pattern are counted separately. More precisely: we consider two strings, a given pattern string H=h₁h₂....h_m and a random text string T=t₁t₂...t_n of respective lengths equal to m and n over an alphabet S of size V. The results for the Markovian model are summarized in two theorems

Keywords

Markov processes; pattern matching; random processes; sequences; word processing; Markovian model; Markovian sequence; Markovian source; alphabet size; overlapping copies; pattern frequency occurrences; pattern matching; pattern strings; random text string; string lengths; theorems; Autocorrelation; Collaboration; Computer aided software engineering; Computer science; Frequency; Pattern matching; Polynomials; Random variables; Reactive power;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory. 1997. Proceedings., 1997 IEEE International Symposium on

Conference_Location

Ulm

Print_ISBN

0-7803-3956-8

Type

conf

DOI

10.1109/ISIT.1997.613234

Filename

613234

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3050524