Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Self-Correlation and Maximum Independence in Finite Relations
KTH, Skolan för datavetenskap och kommunikation (CSC).ORCID-id: 0000-0002-0074-8786
2015 (Engelska)Ingår i: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, nr 191, s. 60-74Artikel i tidskrift (Refereegranskat) Published
Resurstyp
Text
Abstract [en]

We consider relations with no order on their attributes as in Database Theory. An independent partition of the set of attributes S of a finite relation R is any partition (sic) of S such that the join of the projections of R over the elements of (sic) yields R. Identifying independent partitions has many applications and corresponds conceptually to revealing orthogonality between sets of dimensions in multidimensional point spaces. A subset of S is termed self-correlated if there is a value of each of its attributes such that no tuple of R contains all those values. This paper uncovers a connection between independence and self-correlation, showing that the maximum independent partition is the least fixed point of a certain inflationary transformer alpha that operates on the finite lattice of partitions of S. alpha is defined via the minimal self-correlated subsets of S. We use some additional properties of alpha to show the said fixed point is still the limit of the standard approximation sequence, just as in Kleene's well-known fixed point theorem for continuous functions.

Ort, förlag, år, upplaga, sidor
2015. nr 191, s. 60-74
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-181011DOI: 10.4204/EPTCS.191.7ISI: 000367340500006Scopus ID: 2-s2.0-84975726357OAI: oai:DiVA.org:kth-181011DiVA, id: diva2:897765
Anmärkning

QC 20160126

Tillgänglig från: 2016-01-26 Skapad: 2016-01-26 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Gurov, Dilian

Sök vidare i DiVA

Av författaren/redaktören
Gurov, Dilian
Av organisationen
Skolan för datavetenskap och kommunikation (CSC)
I samma tidskrift
Electronic Proceedings in Theoretical Computer Science
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 64 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf