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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Mathematics, Tata Institute of Fundamental Research, Colaba, 400 005, Mumbai, India", 
          "id": "http://www.grid.ac/institutes/grid.22401.35", 
          "name": [
            "School of Mathematics, Tata Institute of Fundamental Research, Colaba, 400 005, Mumbai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharya", 
        "givenName": "Amitava", 
        "id": "sg:person.013604232267.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013604232267.41"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL", 
          "id": "http://www.grid.ac/institutes/grid.185648.6", 
          "name": [
            "Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mubayi", 
        "givenName": "Dhruv", 
        "id": "sg:person.013521032647.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013521032647.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Research Group on Artificial Intelligence, University of Szeged, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.512679.e", 
          "name": [
            "Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL", 
            "Research Group on Artificial Intelligence, University of Szeged, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tur\u00e1n", 
        "givenName": "Gy\u00f6rgy", 
        "id": "sg:person.012465675663.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012465675663.27"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "The minimization problem for Horn formulas is to find a Horn formula equivalent to a given Horn formula, using a minimum number of clauses. A \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$2^{\\log^{1 - \\epsilon}(n)}$\\end{document}-inapproximability result is proven, which is the first inapproximability result for this problem. We also consider several other versions of Horn minimization. The more general version which allows for the introduction of new variables is known to be too difficult as its equivalence problem is co-NP-complete. Therefore, we propose a variant called Steiner-minimization, which allows for the introduction of new variables in a restricted manner. Steiner-minimization of Horn formulas is shown to be MAX-SNP-hard. In the positive direction, a o(n), namely, O(nloglogn/(logn)1/4)-approximation algorithm is given for the Steiner-minimization of definite Horn formulas. The algorithm is based on a new result in algorithmic extremal graph theory, on partitioning bipartite graphs into complete bipartite graphs, which may be of independent interest. Inapproximability results and approximation algorithms are also given for restricted versions of Horn minimization, where only clauses present in the original formula may be used.", 
    "editor": [
      {
        "familyName": "Abramsky", 
        "givenName": "Samson", 
        "type": "Person"
      }, 
      {
        "familyName": "Gavoille", 
        "givenName": "Cyril", 
        "type": "Person"
      }, 
      {
        "familyName": "Kirchner", 
        "givenName": "Claude", 
        "type": "Person"
      }, 
      {
        "familyName": "Meyer auf der Heide", 
        "givenName": "Friedhelm", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14165-2_38", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14164-5", 
        "978-3-642-14165-2"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation algorithm", 
      "inapproximability results", 
      "extremal graph theory", 
      "bipartite graphs", 
      "Horn minimization", 
      "new variables", 
      "complete bipartite graph", 
      "graph theory", 
      "minimization problem", 
      "independent interest", 
      "general version", 
      "new results", 
      "Horn formulas", 
      "equivalence problem", 
      "MAX SNP", 
      "minimum number", 
      "minimization", 
      "formula", 
      "graph", 
      "algorithm", 
      "problem", 
      "original formula", 
      "inapproximability", 
      "first inapproximability", 
      "version", 
      "theory", 
      "variables", 
      "results", 
      "direction", 
      "number", 
      "introduction", 
      "interest", 
      "positive direction", 
      "variants", 
      "manner", 
      "clauses"
    ], 
    "name": "On Approximate Horn Formula Minimization", 
    "pagination": "438-450", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005944805"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14165-2_38"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14165-2_38", 
      "https://app.dimensions.ai/details/publication/pub.1005944805"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_17.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14165-2_38"
  }
]

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

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

146 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES