首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题:Testing Generalised Freeness of Words
  • 本地全文:下载
  • 作者:Pawel Gawrychowski ; Florin Manea ; Dirk Nowotka
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2014
  • 卷号:25
  • 页码:337-349
  • DOI:10.4230/LIPIcs.STACS.2014.337
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Pseudo-repetitions are a natural generalisation of the classical notion of repetitions in sequences: they are the repeated concatenation of a word and its encoding under a certain morphism or antimorphism (anti-/morphism, for short). We approach the problem of deciding efficiently, for a word w and a literal anti-/morphism f, whether w contains an instance of a given pattern involving a variable x and its image under f, i.e., f(x). Our results generalise both the problem of finding fixed repetitive structures (e.g., squares, cubes) inside a word and the problem of finding palindromic structures inside a word. For instance, we can detect efficiently a factor of the form xx^Rxxx^R, or any other pattern of such type. We also address the problem of testing efficiently, in the same setting, whether the word w contains an arbitrary pseudo-repetition of a given exponent.
  • 关键词:Stringology; Pattern matching; Repetition; Pseudo-repetition
国家哲学社会科学文献中心版权所有