Detecting One-variable Patterns

Dmitry Kosolobov, Florin Manea, Dirk Nowotka

Given a pattern $p=s_1{x}_1{s}_2{x}_2\cdots s_{r-1}{x}_{r-1}{s}_r$ such that $x_1,x_2,\dots ,x_{r-1}\in \{x,\overleftarrow{x}\}$, where $x$ is a variable and $\overset{{}_{\lefta…