On Matching Generalised Repetitive Patterns
On Matching Generalised Repetitive Patterns
复制标题
关于匹配广义重复模式
DOI：
10.1007/978-3-319-98654-8_22
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Markus L. Schmid
中科院分区：
文献类型：
--
作者：
Joel D. Day;Pamela Fleischmann;Florin Manea;Dirk Nowotka;Markus L. Schmid
模式是一个带有终端和变量的字符串（可以统一地用终端字替换）。给定一类模式（带有变量），如果一个模式的骨架（去掉所有的终结符只留下变量的结果）是一个模式的（伪）重复，我们就说这个模式是一个-（伪）重复。我们引入了一个大类的模式，概括了几个已知的类，如thek-本地和有界范围的重合度模式，并表明，对于这个类，-（伪）重复可以在多项式时间内匹配。我们还表明，对于大多数类，类-（伪）重复不具有有界树宽。最后，我们表明，如果重复的概念是放松的，使在每次出现的变量可能会出现在一个不同的顺序，匹配问题是NP完全的，即使在严格限制的情况下。
A pattern is a string with terminals and variables (which can be uniformly replaced by terminal words). Given a classof patterns (with variables), we say a patternis a-(pseudo-)repetition if its skeleton – the result of removing all terminal symbols to leave only the variables – is a (pseudo-)repetition of a pattern from. We introduce a large class of patterns which generalises several known classes such as thek-local and bounded scope coincidence degree patterns, and show that for this class,-(pseudo-)repetitions can be matched in polynomial time. We also show that for most classes, the class of-(pseudo-)repetitions does not have bounded treewidth. Finally, we show that if the notion of repetition is relaxed, so that in each occurrence the variables may occur in a different order, the matching problem is NP-complete, even in severely restricted cases.
登录
查看更多内容
从实证数据探究模式语言的可学习性的发展
DOI：
--
发表时间：
2008
期刊：
Theoretical Computer Science vol.397,no.1-3
影响因子：
--
作者：
Yen Kaow Ng;Takeshi Shinohara
通讯作者：
Takeshi Shinohara
DOI：
10.1007/978-3-662-53132-7_25
发表时间：
2016
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
F. Manea;Dirk Nowotka;Markus L. Schmid
通讯作者：
Markus L. Schmid
影响因子：
1
作者：
H. Fernau;Markus L. Schmid
通讯作者：
Markus L. Schmid
当地模式
DOI：
--
发表时间：
2017
期刊：
Foundations of Software Technology and Theoretical Computer Science
影响因子：
--
作者：
Joel D. Day;Pamela Fleischmann;F. Manea;Dirk Nowotka
通讯作者：
Dirk Nowotka
模式语言中的有限程度的歧义
DOI：
--
发表时间：
1994
期刊：
RAIRO - Theoretical Informatics and Applications
影响因子：
--
作者：
A. Mateescu;A. Salomaa
通讯作者：
A. Salomaa