{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:23Z","timestamp":1759638203533},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540781363"},{"type":"electronic","value":"9783540781370"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78137-0_12","type":"book-chapter","created":{"date-parts":[[2008,2,14]],"date-time":"2008-02-14T04:34:46Z","timestamp":1202963686000},"page":"158-168","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Computing Generators of Closed Sets"],"prefix":"10.1007","author":[{"given":"Miki","family":"Hermann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bar\u0131\u015f","family":"Sertkaya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","first-page":"580","volume-title":"Proceedings 6th Information Processing Conference (IFIP 1974)","author":"W.W. Armstrong","year":"1974","unstructured":"Armstrong, W.W.: Dependency structures of data base relationships. In: Rosenfeld, J.L. (ed.) Proceedings 6th Information Processing Conference (IFIP 1974), Stockholm, Sweden, pp. 580\u2013583. North-Holland, Amsterdam (1974)"},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.tcs.2005.03.012","volume":"340","author":"A. Durand","year":"2005","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science\u00a0340(3), 496\u2013513 (2005)","journal-title":"Theoretical Computer Science"},{"key":"12_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/11524564_12","volume-title":"Conceptual Structures: Common Semantics for Sharing Knowledge","author":"C. Frambourg","year":"2005","unstructured":"Frambourg, C., Valtchev, P., Godin, R.: Merge-based computation of minimal generators. In: Dau, F., Mugnier, M.-L., Stumme, G. (eds.) ICCS 2005. LNCS (LNAI), vol.\u00a03596, pp. 181\u2013194. Springer, Heidelberg (2005)"},{"key":"12_CR4","unstructured":"Ganter, B.: Two basic algorithms in concept analysis. Technical Report Preprint-Nr. 831, Technische Hochschule Darmstadt, Germany (1984)"},{"key":"12_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59830-2","volume-title":"Formal Concept Analysis: Mathematical Foundations","author":"B. Ganter","year":"1999","unstructured":"Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, Heidelberg (1999)"},{"key":"12_CR6","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, New York (1979)"},{"key":"12_CR7","first-page":"5","volume":"95","author":"J.-L. Guigues","year":"1986","unstructured":"Guigues, J.-L., Duquenne, V.: Familles minimales d\u2019implications informatives resultant d\u2019un tableau de donn\u00e9es binaries. Math\u00e9matiques, Informatique et Sciences Humaines\u00a095, 5\u201318 (1986)","journal-title":"Math\u00e9matiques, Informatique et Sciences Humaines"},{"issue":"2","key":"12_CR8","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1145\/777943.777945","volume":"28","author":"D. Gunopulos","year":"2003","unstructured":"Gunopulos, D., et al.: Discovering all most specific sentences. ACM Transactions on Database Systems\u00a028(2), 140\u2013174 (2003)","journal-title":"ACM Transactions on Database Systems"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L.A. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News, Complexity Theory Column\u00a08\u00a026(1), 2\u201313 (1995)","journal-title":"SIGACT News, Complexity Theory Column\u00a08"},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Information Processing Letters\u00a027(3), 119\u2013123 (1988)","journal-title":"Information Processing Letters"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1023\/A:1013970520933","volume":"18","author":"S.O. Kuznetsov","year":"2001","unstructured":"Kuznetsov, S.O.: On computing the size of a lattice and related decision problems. Order\u00a018(4), 313\u2013321 (2001)","journal-title":"Order"},{"issue":"8","key":"12_CR12","first-page":"927","volume":"10","author":"S.O. Kuznetsov","year":"2004","unstructured":"Kuznetsov, S.O.: On the intractability of computing the Duquenne-Guigues base. Journal of Universal Computer Science\u00a010(8), 927\u2013933 (2004)","journal-title":"Journal of Universal Computer Science"},{"issue":"2-3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1080\/09528130210164170","volume":"14","author":"S.O. Kuznetsov","year":"2002","unstructured":"Kuznetsov, S.O., Obiedkov, S.A.: Comparing performance of algorithms for generating concept lattices. Journal of Experimental and Theoretical Artificial Intelligence\u00a014(2-3), 189\u2013216 (2002)","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"12_CR14","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/11671404_21","volume-title":"Formal Concept Analysis","author":"S.O. Kuznetsov","year":"2006","unstructured":"Kuznetsov, S.O., Obiedkov, S.O.: Counting pseudo-intents and #P-completeness. In: Missaoui, R., Schmidt, J. (eds.) Formal Concept Analysis. LNCS (LNAI), vol.\u00a03874, pp. 306\u2013308. Springer, Heidelberg (2006)"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(78)90009-0","volume":"17","author":"C.L. Lucchesi","year":"1978","unstructured":"Lucchesi, C.L., Osborn, S.L.: Candidate keys for relations. Journal of Computer and System Science\u00a017(2), 270\u2013279 (1978)","journal-title":"Journal of Computer and System Science"},{"key":"12_CR16","unstructured":"Maier, D.: The Theory of Relational Databases. Computer Science Press (1983)"},{"key":"12_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-540-32262-7_13","volume-title":"Formal Concept Analysis","author":"K. Nehm\u00e9","year":"2005","unstructured":"Nehm\u00e9, K., et al.: On computing the minimal generator family for concept lattices and icebergs. In: Ganter, B., Godin, R. (eds.) ICFCA 2005. LNCS (LNAI), vol.\u00a03403, pp. 192\u2013207. Springer, Heidelberg (2005)"},{"key":"12_CR18","unstructured":"Osborn, S.L.: Normal Forms for Relational Data Bases. PhD thesis, University of Waterloo, Canada (1977)"},{"key":"12_CR19","volume-title":"Computational complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading (1994)"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial-time 1-Turing reductions from #PH to #P. Theoretical Computer Science\u00a0100(1), 205\u2013221 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"12_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"12_CR22","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR23","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-540-24651-0_30","volume-title":"Concept Lattices","author":"P. Valtchev","year":"2004","unstructured":"Valtchev, P., Missaoui, R., Godin, R.: Formal concept analysis for knowledge discovery and data mining: The new challenges. In: Eklund, P.W. (ed.) ICFCA 2004. LNCS (LNAI), vol.\u00a02961, pp. 352\u2013371. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Formal Concept Analysis"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78137-0_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:59:10Z","timestamp":1619521150000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78137-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540781363","9783540781370"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78137-0_12","relation":{},"subject":[]}}