Pattern matching with variables: Efficient algorithms and complexity results
- Submitting institution
-
Loughborough University
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1980
- Type
- D - Journal article
- DOI
-
10.1145/3369935
- Title of journal
- ACM Transactions on Computation Theory
- Article number
- 6
- First page
- 6:1
- Volume
- 12
- Issue
- 1
- ISSN
- 1942-3454
- Open access status
- Compliant
- Month of publication
- February
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Based on the results of this paper two of the co-authors obtained Deutsche Forschungsgemeinschaft (DFG) grants no 218587403 and 416776735. Specifically, the paper sets the state of the art with respect to the efficiency of matching some simple classes of patterns with variables, or showing their difficulty, through a combination of combinatorics on words, algorithms and complexity reductions.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -