On the Algebraic Complexity of Set Equality and Inclusion

Katriel, Irit

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

On the Algebraic Complexity of Set Equality and Inclusion

MPS-Authors

/persons/resource/persons44744

Katriel, Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Katriel, I. (2004). On the Algebraic Complexity of Set Equality and Inclusion. Information Processing Letters, 92, 175-178.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2941-0

Abstract

We present a linear-time algorithm in the algebraic computation tree model for checking whether two sets of integers are equal. The significance of this result is in the fact that it shows that set equality testing is computationally easier when the elements of the sets are restricted to be integers. In addition, we show a linear-time algorithm for checking set inclusion in a slightly extended computational model.