On pattern occurrences in a random text
Φόρτωση...
Ημερομηνία
Συγγραφείς
Fudos, I.
Pitoura, E.
Szpankowski, W.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Information Processing Letters
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Consider a given pattern H and a random text T of length n. We assume that symbols in the text occur independently, and various symbols have different probabilities of occurrence (i.e., the so-called asymmetric Bernoulli model). We are concerned with the probability of exactly r occurrences of H in the text T. We derive the generating function of this probability, and show that asymptotically it behaves as alpha n(r) rho(H)(n-r-1), where alpha is an explicitly computed constant, and rho(H) < 1 is the root of an equation depending on the structure of the pattern. We then extend these findings to random patterns.
Περιγραφή
Λέξεις-κλειδιά
pattern occurrence, bernoulli model, autocorrelation polynomial, generating functions, asymptotic analysis, sequence patterns
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής