Dualization Problem over the Product of Chains: Asymptotic Estimates for the Number of Solutions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-11

AUTHORS

E. V. Djukova, G. O. Maslyakov, P. A. Prokofjev

ABSTRACT

A key intractable problem in logical data analysis, namely, dualization over the product of partial orders, is considered. The important special case where each order is a chain is studied. If the cardinality of each chain is equal to two, then the considered problem is to construct a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form, which is equivalent to the enumeration of irreducible coverings of a Boolean matrix. The asymptotics of the typical number of irreducible coverings is known in the case where the number of rows in the Boolean matrix has a lower order of growth than the number of columns. In this paper, a similar result is obtained for dualization over the product of chains when the cardinality of each chain is higher than two. Deriving such asymptotic estimates is a technically complicated task, and they are required, in particular, for proving the existence of asymptotically optimal algorithms for the problem of monotone dualization and its generalizations. More... »

PAGES

564-567

References to SciGraph publications

  • 2015-05. Asymptotically optimal dualization algorithms in COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1134/s1064562418070086

    DOI

    http://dx.doi.org/10.1134/s1064562418070086

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1111224405


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Russian Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.4886.2", 
              "name": [
                "Federal Research Center \u201cComputer Science and Control,\u201d, Russian Academy of Sciences, 119333, Moscow, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Djukova", 
            "givenName": "E. V.", 
            "id": "sg:person.013674777664.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013674777664.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Moscow State University", 
              "id": "https://www.grid.ac/institutes/grid.14476.30", 
              "name": [
                "Lomonosov Moscow State University, 119991, Moscow, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Maslyakov", 
            "givenName": "G. O.", 
            "id": "sg:person.010025071727.66", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010025071727.66"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Russian Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.4886.2", 
              "name": [
                "Mechanical Engineering Research Institute, Russian Academy of Sciences, 101990, Moscow, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Prokofjev", 
            "givenName": "P. A.", 
            "id": "sg:person.011100344127.23", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011100344127.23"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1134/s0965542515050103", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022455945", 
              "https://doi.org/10.1134/s0965542515050103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(88)90065-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022531339"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1996.0062", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051116080"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539701388768", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879304"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.21469/22233792.3.4.02", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1101329209"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-11", 
        "datePublishedReg": "2018-11-01", 
        "description": "A key intractable problem in logical data analysis, namely, dualization over the product of partial orders, is considered. The important special case where each order is a chain is studied. If the cardinality of each chain is equal to two, then the considered problem is to construct a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form, which is equivalent to the enumeration of irreducible coverings of a Boolean matrix. The asymptotics of the typical number of irreducible coverings is known in the case where the number of rows in the Boolean matrix has a lower order of growth than the number of columns. In this paper, a similar result is obtained for dualization over the product of chains when the cardinality of each chain is higher than two. Deriving such asymptotic estimates is a technically complicated task, and they are required, in particular, for proving the existence of asymptotically optimal algorithms for the problem of monotone dualization and its generalizations.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1134/s1064562418070086", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136704", 
            "issn": [
              "1064-5624", 
              "1531-8362"
            ], 
            "name": "Doklady Mathematics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "98"
          }
        ], 
        "name": "Dualization Problem over the Product of Chains: Asymptotic Estimates for the Number of Solutions", 
        "pagination": "564-567", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a2edcd967120360eef6fc5bd30bd0b9a1cdd797a0b6ae58cd2129631c5a07b63"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1134/s1064562418070086"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1111224405"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1134/s1064562418070086", 
          "https://app.dimensions.ai/details/publication/pub.1111224405"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T08:37", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000314_0000000314/records_55862_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1134%2FS1064562418070086"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1134/s1064562418070086'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1134/s1064562418070086'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1134/s1064562418070086'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1134/s1064562418070086'


     

    This table displays all metadata directly associated to this object as RDF triples.

    95 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1134/s1064562418070086 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nbae55a76857e489d885f4f6ac20675c3
    4 schema:citation sg:pub.10.1134/s0965542515050103
    5 https://doi.org/10.1006/jagm.1996.0062
    6 https://doi.org/10.1016/0020-0190(88)90065-8
    7 https://doi.org/10.1137/s0097539701388768
    8 https://doi.org/10.21469/22233792.3.4.02
    9 schema:datePublished 2018-11
    10 schema:datePublishedReg 2018-11-01
    11 schema:description A key intractable problem in logical data analysis, namely, dualization over the product of partial orders, is considered. The important special case where each order is a chain is studied. If the cardinality of each chain is equal to two, then the considered problem is to construct a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form, which is equivalent to the enumeration of irreducible coverings of a Boolean matrix. The asymptotics of the typical number of irreducible coverings is known in the case where the number of rows in the Boolean matrix has a lower order of growth than the number of columns. In this paper, a similar result is obtained for dualization over the product of chains when the cardinality of each chain is higher than two. Deriving such asymptotic estimates is a technically complicated task, and they are required, in particular, for proving the existence of asymptotically optimal algorithms for the problem of monotone dualization and its generalizations.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N937863e527a64a278eeb2c996f1dd0c6
    16 Nbcbe883e6a2d414eb91499a8175b291b
    17 sg:journal.1136704
    18 schema:name Dualization Problem over the Product of Chains: Asymptotic Estimates for the Number of Solutions
    19 schema:pagination 564-567
    20 schema:productId N7303836ba0ca4d8981929d6f9360d3ad
    21 N8e739c90848043fbb48f4de788dcd729
    22 Ndd26b6e6e6a243229c8be9df16ebbd95
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111224405
    24 https://doi.org/10.1134/s1064562418070086
    25 schema:sdDatePublished 2019-04-11T08:37
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher N5a0fa21a28804b7bb2d8a5676911bd8f
    28 schema:url https://link.springer.com/10.1134%2FS1064562418070086
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset articles
    31 rdf:type schema:ScholarlyArticle
    32 N5a0fa21a28804b7bb2d8a5676911bd8f schema:name Springer Nature - SN SciGraph project
    33 rdf:type schema:Organization
    34 N7303836ba0ca4d8981929d6f9360d3ad schema:name readcube_id
    35 schema:value a2edcd967120360eef6fc5bd30bd0b9a1cdd797a0b6ae58cd2129631c5a07b63
    36 rdf:type schema:PropertyValue
    37 N88d79ad17e39454f8570cf4321383b46 rdf:first sg:person.011100344127.23
    38 rdf:rest rdf:nil
    39 N8e739c90848043fbb48f4de788dcd729 schema:name doi
    40 schema:value 10.1134/s1064562418070086
    41 rdf:type schema:PropertyValue
    42 N937863e527a64a278eeb2c996f1dd0c6 schema:issueNumber 3
    43 rdf:type schema:PublicationIssue
    44 Nbae55a76857e489d885f4f6ac20675c3 rdf:first sg:person.013674777664.78
    45 rdf:rest Ned9c3d3a784f4385a2d7fee46e691a08
    46 Nbcbe883e6a2d414eb91499a8175b291b schema:volumeNumber 98
    47 rdf:type schema:PublicationVolume
    48 Ndd26b6e6e6a243229c8be9df16ebbd95 schema:name dimensions_id
    49 schema:value pub.1111224405
    50 rdf:type schema:PropertyValue
    51 Ned9c3d3a784f4385a2d7fee46e691a08 rdf:first sg:person.010025071727.66
    52 rdf:rest N88d79ad17e39454f8570cf4321383b46
    53 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Information and Computing Sciences
    55 rdf:type schema:DefinedTerm
    56 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Artificial Intelligence and Image Processing
    58 rdf:type schema:DefinedTerm
    59 sg:journal.1136704 schema:issn 1064-5624
    60 1531-8362
    61 schema:name Doklady Mathematics
    62 rdf:type schema:Periodical
    63 sg:person.010025071727.66 schema:affiliation https://www.grid.ac/institutes/grid.14476.30
    64 schema:familyName Maslyakov
    65 schema:givenName G. O.
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010025071727.66
    67 rdf:type schema:Person
    68 sg:person.011100344127.23 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
    69 schema:familyName Prokofjev
    70 schema:givenName P. A.
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011100344127.23
    72 rdf:type schema:Person
    73 sg:person.013674777664.78 schema:affiliation https://www.grid.ac/institutes/grid.4886.2
    74 schema:familyName Djukova
    75 schema:givenName E. V.
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013674777664.78
    77 rdf:type schema:Person
    78 sg:pub.10.1134/s0965542515050103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022455945
    79 https://doi.org/10.1134/s0965542515050103
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1006/jagm.1996.0062 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051116080
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1016/0020-0190(88)90065-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022531339
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1137/s0097539701388768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879304
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.21469/22233792.3.4.02 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101329209
    88 rdf:type schema:CreativeWork
    89 https://www.grid.ac/institutes/grid.14476.30 schema:alternateName Moscow State University
    90 schema:name Lomonosov Moscow State University, 119991, Moscow, Russia
    91 rdf:type schema:Organization
    92 https://www.grid.ac/institutes/grid.4886.2 schema:alternateName Russian Academy of Sciences
    93 schema:name Federal Research Center “Computer Science and Control,”, Russian Academy of Sciences, 119333, Moscow, Russia
    94 Mechanical Engineering Research Institute, Russian Academy of Sciences, 101990, Moscow, Russia
    95 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...