Estimating the number of covering relations in a formal concept lattice

dc.contributor.advisor Jennifer Newman Rodriguez, Aaron
dc.contributor.department Mathematics 2018-08-11T15:41:20.000 2020-06-30T02:58:01Z 2020-06-30T02:58:01Z Thu Jan 01 00:00:00 UTC 2015 2001-01-01 2015-01-01
dc.description.abstract <p>Given data organized in a tabular form called a cross table, the multi-dimensional relationships in the data are represented by a directed acyclic graph called a formal concept lattice. For large sets of data, drawing the graph is not reasonable. We focus on quantitative characteristics of the lattice structure that lead to decreased computation time in the determination of nodes and edge sets on large lattices from big data.</p> <p>This work addresses the problem of recovering the covering relations, of a concept lattice, given the set of nodes. We implement one existing algorithm and formally prove that it correctly computes the covering relations of a given concept lattice from its nodes. We also discuss methods for estimating the number of covering relations in a lattice and offer a conjecture for an upper bound for this number. We present experimental results to predict edge frequency distribution for a range of cross table densities. Finally we discuss some open problems.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 5631
dc.identifier.contextkey 8049384
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/14624
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 20:23:43 UTC 2022
dc.subject.disciplines Mathematics
dc.subject.keywords Applied Mathematics
dc.subject.keywords complete lattices
dc.subject.keywords concept lattices
dc.subject.keywords cover relations
dc.subject.keywords FCA
dc.subject.keywords Formal Concept Analysis
dc.subject.keywords posets
dc.title Estimating the number of covering relations in a formal concept lattice
dc.type article
dc.type.genre thesis
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48 thesis Master of Science
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
427.96 KB
Adobe Portable Document Format