A pattern is a string with terminals and variables (which can be uniformly replaced by terminal words). Given a class C of patterns (with variables), we say a pattern a is a C-(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 C. We introduce a large class of patterns which generalises several known classes such as the k-local and bounded scope coincidence degree patterns, and show that for this class, C-(pseudo-)repetitions can be matched in polynomial time. We also show that for most classes C, the class of C-(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.
展开▼
