Counting subwords and regular languages

作     者：Colbourn, Charles J. Dougherty, Ryan E. Lidbetter, Thomas Finn Shallit, Jeffrey 

作者机构：Computing Informatics and Decision Systems Engineering Arizona State University P.O. Box 878809 TempeAZ85287-8809 United States School of Computer Science University of Waterloo WaterlooONN2L3G1 Canada 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2018年

核心收录：

摘      要：Let x and y be words. We consider the languages whose words z are those for which the numbers of occurrences of x and y, as subwords of z, are the same (resp., the number of x s is less than the number of y s, resp., is less than or equal). We give a necessary and sufficient condition on x and y for these languages to be regular, and we show how to check this condition efficiently. Copyright © 2018, The Authors. All rights reserved.