Please use this identifier to cite or link to this item: https://doi.org/10.1080/10236190500376326
Title: Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier-Szpankowski method
Authors: Kong, Y. 
Keywords: Correlation polynomials
Frequency of pattern occurrences
Generating functions
Goulden-Jackson cluster method
Matrix inversion
Issue Date: Dec-2005
Citation: Kong, Y. (2005-12). Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier-Szpankowski method. Journal of Difference Equations and Applications 11 (15) : 1265-1271. ScholarBank@NUS Repository. https://doi.org/10.1080/10236190500376326
Abstract: The Goulden-Jackson cluster method is a powerful method to find generating functions of pattern occurrences in random sequences [1]. The method is clearly explained, extended and implemented by Noonan and Zeilberger [2]. In this paper, we elaborate on one of the several extensions in [2], namely the extension from symmetrical Bernoulli sequences where the occurrences of each symbol have equal probability, to asymmetrical Bernoulli sequences with different probabilities of symbol generations. An explicit formula is derived for the extension, which is implicitly embedded in the treatment of [2]. The extended result is then compared with the method of Régnier-Szpankowski [3], a method which was developed independently to tackle the same problem. By manipulating some matrix inversions, we show that the Régnier-Szpankowski method can be simplified to the extended Goulden-Jackson method.
Source Title: Journal of Difference Equations and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/103256
ISSN: 10236198
DOI: 10.1080/10236190500376326
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Aug 17, 2018

WEB OF SCIENCETM
Citations

4
checked on Jul 9, 2018

Page view(s)

39
checked on Jun 8, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.