A tree-partitioning technique with applications to expression evaluation and term matching

S. Rao Kosaraju; Arthur L. Delcher

A tree-partitioning technique with applications to expression evaluation and term matching

S. Rao Kosaraju, Arthur L. Delcher

School of Medicine

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

Abstract

A tree-partitioning technique is proposed and applied to expression evaluation and term matching. It was shown recently that the problem of evaluating an arithmetic expression is in NC¹, and an O(log N)-depth, O(N²log N)-size circuit for this problem was described. The size is reduced here to O(N log^k N) while O(log N) depth is maintained. An O(log N)-time, O(N)-processor CREW (concurrent read, exclusive write) algorithm for term matching, which improves the previous O(log N)-time, N²-processor algorithm, is also presented.

Original language	English (US)
Pages (from-to)	163-172
Number of pages	10
Journal	IEEE Transactions on Industry Applications
Volume	27
Issue number	1 pt 1
State	Published - Jan 1 1991
Event	1989 Industry Applications Society Annual Meeting - San Diego, CA, USA Duration: Oct 1 1989 → Oct 5 1989

ASJC Scopus subject areas

Control and Systems Engineering
Industrial and Manufacturing Engineering
Electrical and Electronic Engineering

Cite this

@article{f26b14a83c0f4f12a03fd7fe8f88324a,

title = "A tree-partitioning technique with applications to expression evaluation and term matching",

abstract = "A tree-partitioning technique is proposed and applied to expression evaluation and term matching. It was shown recently that the problem of evaluating an arithmetic expression is in NC1, and an O(log N)-depth, O(N2log N)-size circuit for this problem was described. The size is reduced here to O(N logk N) while O(log N) depth is maintained. An O(log N)-time, O(N)-processor CREW (concurrent read, exclusive write) algorithm for term matching, which improves the previous O(log N)-time, N2-processor algorithm, is also presented.",

author = "Kosaraju, {S. Rao} and Delcher, {Arthur L.}",

year = "1991",

month = jan,

day = "1",

language = "English (US)",

volume = "27",

pages = "163--172",

journal = "IEEE Transactions on Industry Applications",

issn = "0093-9994",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1 pt 1",

note = "1989 Industry Applications Society Annual Meeting ; Conference date: 01-10-1989 Through 05-10-1989",

}

TY - JOUR

T1 - A tree-partitioning technique with applications to expression evaluation and term matching

AU - Kosaraju, S. Rao

AU - Delcher, Arthur L.

PY - 1991/1/1

Y1 - 1991/1/1

N2 - A tree-partitioning technique is proposed and applied to expression evaluation and term matching. It was shown recently that the problem of evaluating an arithmetic expression is in NC1, and an O(log N)-depth, O(N2log N)-size circuit for this problem was described. The size is reduced here to O(N logk N) while O(log N) depth is maintained. An O(log N)-time, O(N)-processor CREW (concurrent read, exclusive write) algorithm for term matching, which improves the previous O(log N)-time, N2-processor algorithm, is also presented.

AB - A tree-partitioning technique is proposed and applied to expression evaluation and term matching. It was shown recently that the problem of evaluating an arithmetic expression is in NC1, and an O(log N)-depth, O(N2log N)-size circuit for this problem was described. The size is reduced here to O(N logk N) while O(log N) depth is maintained. An O(log N)-time, O(N)-processor CREW (concurrent read, exclusive write) algorithm for term matching, which improves the previous O(log N)-time, N2-processor algorithm, is also presented.

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

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

M3 - Conference article

AN - SCOPUS:0025839537

SN - 0093-9994

VL - 27

SP - 163

EP - 172

JO - IEEE Transactions on Industry Applications

JF - IEEE Transactions on Industry Applications

IS - 1 pt 1

T2 - 1989 Industry Applications Society Annual Meeting

Y2 - 1 October 1989 through 5 October 1989

ER -

A tree-partitioning technique with applications to expression evaluation and term matching

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this