Some contributions to the minimum representation problem of key systems

Katona, Gyula and Tichler, Krisztián (2006) Some contributions to the minimum representation problem of key systems. LECTURE NOTES IN COMPUTER SCIENCE, 3861 L. pp. 240-257. ISSN 0302-9743


Download (19MB) | Preview


Some new and improved results on the minimum representation problem for key systems will be presented. By improving a lemma of the second author we obtain better or new results on badly representable key systems, such as showing the most badly representable key system known, namely of size 2 n(1-c.log log n/ log n) where n is the number of attributes. We also make an observation on a theorem of J. Demetrovics, Z. Füredi and the first author and give some new well representable key systems as well.

Item Type: Article
Additional Information: 4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006; 14 February 2006 through 17 February 2006, Budapest
Uncontrolled Keywords: Computer systems; Key systems; Trees (mathematics); Theorem proving; Problem solving; Matrix algebra; Mathematical models; Computational methods; relational database; MINIMUM MATRIX REPRESENTATION; Labelled directed tree; Extremal problems
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 30 Jan 2015 11:06
Last Modified: 30 Jan 2015 11:58

Actions (login required)

Edit Item Edit Item