File Download
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.4230/LIPIcs.ISAAC.2016.39
 Find via
Supplementary

Citations:
 Appears in Collections:
Conference Paper: Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach
Title  Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach 

Authors  
Issue Date  2016 
Publisher  Schloss Dagstuhl  LeibnizZentrum fuer Informatik GmbH, Dagstuhl Publishing. The Proceedings' web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/ 
Citation  27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, 1214 December 2016. In SeokHee Hong (ed.), LIPICS  Leibniz International Proceedings in Informatics, 2016, v. 64, article no. 39, p. 39:139:12 How to Cite? 
Abstract  We revisit the waiting time of patterns in repeated independent experiments. We show that the most intuitive approach for computing the waiting time, which reduces it to computing the stopping time of a Markov chain, is optimum from the perspective of computational complexity. For the single pattern case, this approach requires us to solve a system of m linear equations, where m denotes the length of the pattern. We show that this system can be solved in O(m + n) time, where n denotes the number of possible outcomes of each single experiment. The main procedure only costs O(m) time, while a preprocessing rocedure costs O(m + n) time. For the multiple pattern case, our approach is as efficient as the one given by Li [Ann. Prob., 1980]. Our method has several advantages over other methods. First, it extends to compute the variance or even higher moment of the waiting time for the single pattern case. Second, it is more intuitive and does not entail tedious mathematics and heavy probability theory. Our main result (Theorem 2) might be of independent interest to the theory of linear equations. 
Description  Session 8B: Pattern Matching/String Algorithm 
Persistent Identifier  http://hdl.handle.net/10722/247692 
ISBN  
ISSN 
DC Field  Value  Language 

dc.contributor.author  Jin, K   
dc.date.accessioned  20171018T08:31:07Z   
dc.date.available  20171018T08:31:07Z   
dc.date.issued  2016   
dc.identifier.citation  27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, 1214 December 2016. In SeokHee Hong (ed.), LIPICS  Leibniz International Proceedings in Informatics, 2016, v. 64, article no. 39, p. 39:139:12   
dc.identifier.isbn  9783959770262   
dc.identifier.issn  18688969   
dc.identifier.uri  http://hdl.handle.net/10722/247692   
dc.description  Session 8B: Pattern Matching/String Algorithm   
dc.description.abstract  We revisit the waiting time of patterns in repeated independent experiments. We show that the most intuitive approach for computing the waiting time, which reduces it to computing the stopping time of a Markov chain, is optimum from the perspective of computational complexity. For the single pattern case, this approach requires us to solve a system of m linear equations, where m denotes the length of the pattern. We show that this system can be solved in O(m + n) time, where n denotes the number of possible outcomes of each single experiment. The main procedure only costs O(m) time, while a preprocessing rocedure costs O(m + n) time. For the multiple pattern case, our approach is as efficient as the one given by Li [Ann. Prob., 1980]. Our method has several advantages over other methods. First, it extends to compute the variance or even higher moment of the waiting time for the single pattern case. Second, it is more intuitive and does not entail tedious mathematics and heavy probability theory. Our main result (Theorem 2) might be of independent interest to the theory of linear equations.   
dc.language  eng   
dc.publisher  Schloss Dagstuhl  LeibnizZentrum fuer Informatik GmbH, Dagstuhl Publishing. The Proceedings' web site is located at hhttp://www.dagstuhl.de/publikationen/lipics/   
dc.relation.ispartof  LIPICS  Leibniz International Proceedings in Informatics   
dc.title  Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach   
dc.type  Conference_Paper   
dc.identifier.email  Jin, K: cskaijin@hku.hk   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.4230/LIPIcs.ISAAC.2016.39   
dc.identifier.hkuros  282119   
dc.identifier.volume  64   
dc.identifier.spage  39:1   
dc.identifier.epage  39:12   
dc.publisher.place  Saarbrücken/Wadern, Germany   