Matching Patterns with Variables Under Simon's Congruence

2023/08/16 by Pamela Fleischmann, Fleischmann, Pamela, Sung-Min Kim +11 · 1 citation
Computer Science · #semigroups and automata theory #Data Mining Algorithms and Applications #Advanced Database Systems and Queries

paper · pdf · doi:10.48550/arxiv.2308.08374

Abstract

We introduce and investigate a series of matching problems for patterns with variables under Simon's congruence. Our results provide a thorough picture of these problems' computational complexity.

Cited by

• Jumbled Scattered Factors

Related

• Matching Patterns with Variables
• Pattern Matching in Set Partitions is NP-Complete
• New Variants of Pattern Matching with Constants and Variables
• Pattern Matching in the Cycle Structure of Permutations
• Separating Sets of Strings by Finding Matching Patterns is Almost Always Hard