On Approximate Horn Formula Minimization View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Amitava Bhattacharya , Bhaskar DasGupta , Dhruv Mubayi , György Turán

ABSTRACT

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} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \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. More... »

PAGES

438-450

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14165-2_38

DOI

http://dx.doi.org/10.1007/978-3-642-14165-2_38

DIMENSIONS

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


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/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

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.1007/978-3-642-14165-2_38'

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.1007/978-3-642-14165-2_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14165-2_38'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14165-2_38'


 

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

146 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14165-2_38 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N25c1539fb0db465990fdf3e3aab2e5ef
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema: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} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \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.
7 schema:editor Nf41ca12fccb24409b4b9de14d8055e7d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N46485c038ab84d13ae0fb7ee9856778c
12 schema:keywords Horn formulas
13 Horn minimization
14 MAX SNP
15 algorithm
16 approximation algorithm
17 bipartite graphs
18 clauses
19 complete bipartite graph
20 direction
21 equivalence problem
22 extremal graph theory
23 first inapproximability
24 formula
25 general version
26 graph
27 graph theory
28 inapproximability
29 inapproximability results
30 independent interest
31 interest
32 introduction
33 manner
34 minimization
35 minimization problem
36 minimum number
37 new results
38 new variables
39 number
40 original formula
41 positive direction
42 problem
43 results
44 theory
45 variables
46 variants
47 version
48 schema:name On Approximate Horn Formula Minimization
49 schema:pagination 438-450
50 schema:productId N3de9968c67224599ba3d0cd4970e4059
51 N6a3ca6370cc04cb5a99709ec1698baf3
52 schema:publisher N9c88062c01e64f68be1cdbfe3c689f92
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005944805
54 https://doi.org/10.1007/978-3-642-14165-2_38
55 schema:sdDatePublished 2022-05-20T07:42
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher N1c35027fe2d44df9af978f00eac9d660
58 schema:url https://doi.org/10.1007/978-3-642-14165-2_38
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N07626436855540489e1a33fdec6c27b4 rdf:first N6cf840a128cc4d0c8586cffacfff9a33
63 rdf:rest N3117599e5bc446f3bf952b149e37d404
64 N106e9a5fbd3c4748a3a268b3ff4c9e30 rdf:first sg:person.012465675663.27
65 rdf:rest rdf:nil
66 N1c35027fe2d44df9af978f00eac9d660 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N218127cfa7b0438ab67514c54c3bc437 schema:familyName Gavoille
69 schema:givenName Cyril
70 rdf:type schema:Person
71 N25c1539fb0db465990fdf3e3aab2e5ef rdf:first sg:person.013604232267.41
72 rdf:rest Nedc04d0b6b73402790ac08940e299eeb
73 N3117599e5bc446f3bf952b149e37d404 rdf:first Ndebbfea87a9348389e72e310f7b19dee
74 rdf:rest N75df09b70d3a4a81ae63030dc0f8435f
75 N3de9968c67224599ba3d0cd4970e4059 schema:name doi
76 schema:value 10.1007/978-3-642-14165-2_38
77 rdf:type schema:PropertyValue
78 N46485c038ab84d13ae0fb7ee9856778c schema:isbn 978-3-642-14164-5
79 978-3-642-14165-2
80 schema:name Automata, Languages and Programming
81 rdf:type schema:Book
82 N58d723ed17a840febe28243afb51ff64 schema:familyName Spirakis
83 schema:givenName Paul G.
84 rdf:type schema:Person
85 N6a3ca6370cc04cb5a99709ec1698baf3 schema:name dimensions_id
86 schema:value pub.1005944805
87 rdf:type schema:PropertyValue
88 N6cf840a128cc4d0c8586cffacfff9a33 schema:familyName Kirchner
89 schema:givenName Claude
90 rdf:type schema:Person
91 N75df09b70d3a4a81ae63030dc0f8435f rdf:first N58d723ed17a840febe28243afb51ff64
92 rdf:rest rdf:nil
93 N8a0bd0cfdf3a494da45096ed62169705 rdf:first N218127cfa7b0438ab67514c54c3bc437
94 rdf:rest N07626436855540489e1a33fdec6c27b4
95 N9c88062c01e64f68be1cdbfe3c689f92 schema:name Springer Nature
96 rdf:type schema:Organisation
97 Ndebbfea87a9348389e72e310f7b19dee schema:familyName Meyer auf der Heide
98 schema:givenName Friedhelm
99 rdf:type schema:Person
100 Nedc04d0b6b73402790ac08940e299eeb rdf:first sg:person.0763403270.10
101 rdf:rest Nf8063a5fa9f243f49cf53d62576d8007
102 Nf41ca12fccb24409b4b9de14d8055e7d rdf:first Nf9109767567c4b77b356fe727d8adce2
103 rdf:rest N8a0bd0cfdf3a494da45096ed62169705
104 Nf8063a5fa9f243f49cf53d62576d8007 rdf:first sg:person.013521032647.30
105 rdf:rest N106e9a5fbd3c4748a3a268b3ff4c9e30
106 Nf9109767567c4b77b356fe727d8adce2 schema:familyName Abramsky
107 schema:givenName Samson
108 rdf:type schema:Person
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.012465675663.27 schema:affiliation grid-institutes:grid.512679.e
116 schema:familyName Turán
117 schema:givenName György
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012465675663.27
119 rdf:type schema:Person
120 sg:person.013521032647.30 schema:affiliation grid-institutes:grid.185648.6
121 schema:familyName Mubayi
122 schema:givenName Dhruv
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013521032647.30
124 rdf:type schema:Person
125 sg:person.013604232267.41 schema:affiliation grid-institutes:grid.22401.35
126 schema:familyName Bhattacharya
127 schema:givenName Amitava
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013604232267.41
129 rdf:type schema:Person
130 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.185648.6
131 schema:familyName DasGupta
132 schema:givenName Bhaskar
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
134 rdf:type schema:Person
135 grid-institutes:grid.185648.6 schema:alternateName Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL
136 Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL
137 schema:name Department of Computer Science, University of Illinois at Chicago, 60607-7053, Chicago, IL
138 Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL
139 rdf:type schema:Organization
140 grid-institutes:grid.22401.35 schema:alternateName School of Mathematics, Tata Institute of Fundamental Research, Colaba, 400 005, Mumbai, India
141 schema:name School of Mathematics, Tata Institute of Fundamental Research, Colaba, 400 005, Mumbai, India
142 rdf:type schema:Organization
143 grid-institutes:grid.512679.e schema:alternateName Research Group on Artificial Intelligence, University of Szeged, Hungary
144 schema:name Department of Mathematics, Statistics & Computer Science, University of Illinois at Chicago, 60607-7045, Chicago, IL
145 Research Group on Artificial Intelligence, University of Szeged, Hungary
146 rdf:type schema:Organization
 




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


...