Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2018) | last year (2017) | two years ago (2016) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Katriel, Irit

dblp



BibTeX cite key*:

Katriel2004b

Title

Title*:

On the Algebraic Complexity of Set Equality and Inclusion

Journal

Journal Title*:

Information Processing Letters

Journal's URL:


Download URL
for the article:

http://www.mpi-sb.mpg.de/~irit/pub/sets.ps

Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

92

Number:

4

Publishing Date:

2004

Pages*:

175-178

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

Computational complexity, algebraic computation tree, computational models, set equality

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Katriel2004b,
AUTHOR = {Katriel, Irit},
TITLE = {On the Algebraic Complexity of Set Equality and Inclusion},
JOURNAL = {Information Processing Letters},
YEAR = {2004},
NUMBER = {4},
VOLUME = {92},
PAGES = {175--178},
}


Entry last modified by Uwe Brahm, 02/15/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Irit Katriel
Created
01/12/2005 01:35:56 PM
Revision
1.
0.


Editor
Uwe Brahm
Irit Katriel


Edit Date
02/15/2005 09:15:19 PM
12.01.2005 13:35:56