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

文章基本信息

  • 标题:Local Patterns
  • 作者:Joel D. Day ; Pamela Fleischmann ; Florin Manea
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:93
  • 页码:24:1-24:14
  • DOI:10.4230/LIPIcs.FSTTCS.2017.24
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A pattern is a word consisting of constants from an alphabet Sigma of terminal symbols and variables from a set X. Given a pattern alpha, the decision-problem whether a given word w may be obtained by substituting the variables in \alpha for words over Sigma is called the matching problem. While this problem is, in general, NP-complete, several classes of patterns for which it can be efficiently solved are already known. We present two new classes of patterns, called k-local, and strongly-nested, and show that the respective matching problems, as well as membership can be solved efficiently for any fixed k.
  • 关键词:Patterns with Variables; Local Patterns; Combinatorial Pattern Matching; Descriptive Patterns
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有