首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Enumerating words with forbidden factors
Institution:Heilbronn Institute, Bristol;Department of Electronics, Computing and Mathematics, University of Derby, Markeaton Street, Derby, DE22 3AW, United Kingdom;Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Str. Mihail Kogalniceanu Nr. 1, 400084 Cluj-Napoca, Romania;Department of Electronics, Computing and Mathematics, University of Derby, Kedleston Road, Derby, DE22 1GB, United Kingdom;Department of Mathematics, University of Patras, Patras, GR 265-00, Greece;Department of Computer & Informatics Engineering, Technological Educational Institute of Western Greece, Antirrio, GR 263-34, Greece;Global Academy of Agriculture and Food Security, University of Edinburgh, Scotland;Computing and Information Science, University of Strathclyde, Scotland;Department of Mathematical Sciences, Binghamton University (State University of New York), Binghamton, NY 13902-6000, U.S.A;Department of Applied Mathematics, Tunghai University, Taichung, Taiwan, PR China;Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan, PR China
Abstract:This presentation is an exposition of an application of the theory of recurrence relations to enumerating strings over an alphabet with a forbidden factor (consecutive substring). As an illustration we examine the case of binary strings with a forbidden factor of k consecutive symbols 1 for given k, using generating function techniques that deserve to be better known.This allows us to derive a known upper bound for the number of prefix normal binary words: words with the property that no factor has more occurrences of the symbol 1 than the prefix of the same length. Such words arise in the context of indexed binary jumbled pattern matching.
Keywords:prefix normal word  forbidden factor  recurrence relation  power series
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号