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.
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