Reidenbach_Schmid_Internal_Report_1109_Patterns_with_bounded_treewidth.pdf (405.28 kB)
Download file

Patterns with bounded treewidth [internal report]

Download (405.28 kB)
online resource
posted on 25.07.2012, 13:48 by Daniel ReidenbachDaniel Reidenbach, Markus L. Schmid
A pattern is a string consisting of variables and terminal symbols, and its language is the set of all words that can be obtained by substi- tuting arbitrary words for the variables. The membership problem for pattern languages, i. e., deciding on whether or not a given word is in the pattern language of a given pattern is NP-complete. We show that any parameter of patterns that is an upper bound for the treewidth of appro- priate encodings of patterns as relational structures, if restricted, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify new such parameters.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHMID, M.L., 2012. Patterns with bounded treewidth. Internal Report 1109, Department of Computer Science, Loughborough University

Publisher

Department of Computer Science, Loughborough University

Version

VoR (Version of Record)

Publication date

2012-06

Notes

This internal report is the full version of a paper previously presented at the conference LATA 2012 (available on the Institutional Repository at: https://dspace.lboro.ac.uk/dspace-jspui/handle/2134/9556)

Language

en

Usage metrics

Keywords

Exports