When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.24
URN: urn:nbn:de:0030-drops-84013
URL: http://drops.dagstuhl.de/opus/volltexte/2018/8401/
 Go to the corresponding LIPIcs Volume Portal

### Local Patterns

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{day_et_al:LIPIcs:2018:8401,
author =	{Joel D. Day and Pamela Fleischmann and Florin Manea and Dirk Nowotka},
title =	{{Local Patterns}},
booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages =	{24:1--24:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-055-2},
ISSN =	{1868-8969},
year =	{2018},
volume =	{93},
editor =	{Satya Lokam and R. Ramanujam},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},