Tree pattern matching to subset matching in linear time

Richard Cole; Ramesh Hariharan

doi:10.1137/S0097539700382704

Tree pattern matching to subset matching in linear time

Richard Cole, Ramesh Hariharan

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O (n log ² m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.

Original language	English (US)
Pages (from-to)	1056-1066
Number of pages	11
Journal	SIAM Journal on Computing
Volume	32
Issue number	4
DOIs	https://doi.org/10.1137/S0097539700382704
State	Published - Jun 2003

Keywords

Subset matching
Tree pattern matching

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539700382704

Cite this

@article{7cdc9dea38c040f4b8485ec5640ff4ab,

title = "Tree pattern matching to subset matching in linear time",

abstract = "In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O (n log 2 m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.",

keywords = "Subset matching, Tree pattern matching",

author = "Richard Cole and Ramesh Hariharan",

year = "2003",

month = jun,

doi = "10.1137/S0097539700382704",

language = "English (US)",

volume = "32",

pages = "1056--1066",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Tree pattern matching to subset matching in linear time

AU - Cole, Richard

AU - Hariharan, Ramesh

PY - 2003/6

Y1 - 2003/6

N2 - In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O (n log 2 m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.

AB - In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O (n log 2 m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.

KW - Subset matching

KW - Tree pattern matching

UR - http://www.scopus.com/inward/record.url?scp=0141645226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0141645226&partnerID=8YFLogxK

U2 - 10.1137/S0097539700382704

DO - 10.1137/S0097539700382704

M3 - Article

AN - SCOPUS:0141645226

SN - 0097-5397

VL - 32

SP - 1056

EP - 1066

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Tree pattern matching to subset matching in linear time

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this