Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.24
URN: urn:nbn:de:0030-drops-84013
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8401/
Day, Joel D. ; Fleischmann, Pamela ; Manea, Florin ; Nowotka, Dirk
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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8401},
URN = {urn:nbn:de:0030-drops-84013},
doi = {10.4230/LIPIcs.FSTTCS.2017.24},
annote = {Keywords: Patterns with Variables, Local Patterns, Combinatorial Pattern Matching, Descriptive Patterns}
}
| Keywords: | Patterns with Variables, Local Patterns, Combinatorial Pattern Matching, Descriptive Patterns | |
| Seminar: | 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) | |
| Issue date: | 2018 | |
| Date of publication: | 12.02.2018 |
