On-line 2-satisfiability View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-09

AUTHORS

Brigitte Jaumard, Paola Marchioro, Aurora Morgana, Rossella Petreschi, Bruno Simeone

ABSTRACT

We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m2) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception. More... »

PAGES

155-165

References to SciGraph publications

  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01531076

    DOI

    http://dx.doi.org/10.1007/bf01531076

    DIMENSIONS

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


    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": {
              "name": [
                "HEC-GERAD, Montr\u00e9al, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Jaumard", 
            "givenName": "Brigitte", 
            "id": "sg:person.07721500366.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721500366.17"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Matematica, Universit\u00e0 \u201cLa Sapienza\u201d, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Marchioro", 
            "givenName": "Paola", 
            "id": "sg:person.015045661577.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015045661577.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Matematica, Universit\u00e0 \u201cLa Sapienza\u201d, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Morgana", 
            "givenName": "Aurora", 
            "id": "sg:person.010141153531.51", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010141153531.51"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Matematica, Universit\u00e0 \u201cLa Sapienza\u201d, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Statistica, Probabilit\u00e0 e Statistica Applicata, Universit\u00e0 \u201cLa Sapienza\u201d, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Simeone", 
            "givenName": "Bruno", 
            "id": "sg:person.012600006066.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(86)90006-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010923276"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(79)90002-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023830880"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(83)90033-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027487952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(80)90049-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032382216"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-0208(08)73112-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033206855"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0205048", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841334"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1990-09", 
        "datePublishedReg": "1990-09-01", 
        "description": "We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m2) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01531076", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043955", 
            "issn": [
              "1012-2443", 
              "1573-7470"
            ], 
            "name": "Annals of Mathematics and Artificial Intelligence", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "1"
          }
        ], 
        "name": "On-line 2-satisfiability", 
        "pagination": "155-165", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "85889cd57cfdf6f01dadf66b97f454f793c8df18fc2f0be361c04b31a7b90d5c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01531076"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1028030928"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01531076", 
          "https://app.dimensions.ai/details/publication/pub.1028030928"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:46", 
        "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/0000000001_0000000264/records_8664_00000488.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01531076"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01531076'

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

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


     

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

    114 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01531076 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N1ae6b634dc8b401eaf813a3b8349c384
    4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
    5 https://doi.org/10.1016/0020-0190(79)90002-4
    6 https://doi.org/10.1016/0020-0190(80)90049-6
    7 https://doi.org/10.1016/0020-0190(83)90033-9
    8 https://doi.org/10.1016/0196-6774(86)90006-4
    9 https://doi.org/10.1016/s0304-0208(08)73112-8
    10 https://doi.org/10.1137/0205048
    11 schema:datePublished 1990-09
    12 schema:datePublishedReg 1990-09-01
    13 schema:description We deal with the followingon-line 2-satisfiability problemP(m, n): starting fromC(0)=true, consider a sequence ofm Boolean formulasC(k) (inn variables and in conjunctive normal form), each of them being the intersection of the previous one with a single clause which is the union of two literals. Solve the sequence of 2-satisfiability problemsC(k)=true,k=1,...,m. It is well known that a 2-satisfiability problem involvingm clauses can be solved inO(m) time. Thus, by a naive approach one can solveP(m, n) in overallO(m2) time. We present an algorithm with overallO(nm) time complexity, which for every formula not only checks its satisfiability, but also actually computes a solution (if any), and moreover, detects all forced and all identical variables. Our algorithm makes use of an efficient on-line transitive closure procedure by Italiano. We discuss two applications to the design of integrated electronic circuits and to edge classification in automated perception.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N0b78553ba5e04c249d9471cc5dd8130a
    18 Nc53e4f28c86e4cc2beff836df571aa32
    19 sg:journal.1043955
    20 schema:name On-line 2-satisfiability
    21 schema:pagination 155-165
    22 schema:productId N6342979cf81d4ae495845ec5b9479aa0
    23 N6b19775ca77d4735b6b6fd4d6ffd1d51
    24 N940c825b881d4f86a9c40b7b6e58d267
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028030928
    26 https://doi.org/10.1007/bf01531076
    27 schema:sdDatePublished 2019-04-10T15:46
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N79cce700bcf944c490d38ff5004a6691
    30 schema:url http://link.springer.com/10.1007/BF01531076
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N037a522f1fb94a8bb6d4f2df98f026d2 schema:name HEC-GERAD, Montréal, Canada
    35 rdf:type schema:Organization
    36 N0b78553ba5e04c249d9471cc5dd8130a schema:issueNumber 1-4
    37 rdf:type schema:PublicationIssue
    38 N1ae6b634dc8b401eaf813a3b8349c384 rdf:first sg:person.07721500366.17
    39 rdf:rest Nbb784b3c6105406ab73c63acce73ff16
    40 N6342979cf81d4ae495845ec5b9479aa0 schema:name doi
    41 schema:value 10.1007/bf01531076
    42 rdf:type schema:PropertyValue
    43 N6b19775ca77d4735b6b6fd4d6ffd1d51 schema:name readcube_id
    44 schema:value 85889cd57cfdf6f01dadf66b97f454f793c8df18fc2f0be361c04b31a7b90d5c
    45 rdf:type schema:PropertyValue
    46 N79cce700bcf944c490d38ff5004a6691 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N8a024c5c530b45bb9bd7464a0ab4174e rdf:first sg:person.011402427702.78
    49 rdf:rest N9717ad615b7c475f8f3c213fadf56f00
    50 N940c825b881d4f86a9c40b7b6e58d267 schema:name dimensions_id
    51 schema:value pub.1028030928
    52 rdf:type schema:PropertyValue
    53 N9717ad615b7c475f8f3c213fadf56f00 rdf:first sg:person.012600006066.78
    54 rdf:rest rdf:nil
    55 Nbb784b3c6105406ab73c63acce73ff16 rdf:first sg:person.015045661577.05
    56 rdf:rest Nea69df233e7843b19cf9aa35d9fdc91e
    57 Nc53e4f28c86e4cc2beff836df571aa32 schema:volumeNumber 1
    58 rdf:type schema:PublicationVolume
    59 Nea69df233e7843b19cf9aa35d9fdc91e rdf:first sg:person.010141153531.51
    60 rdf:rest N8a024c5c530b45bb9bd7464a0ab4174e
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Artificial Intelligence and Image Processing
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1043955 schema:issn 1012-2443
    68 1573-7470
    69 schema:name Annals of Mathematics and Artificial Intelligence
    70 rdf:type schema:Periodical
    71 sg:person.010141153531.51 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    72 schema:familyName Morgana
    73 schema:givenName Aurora
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010141153531.51
    75 rdf:type schema:Person
    76 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    77 schema:familyName Petreschi
    78 schema:givenName Rossella
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    80 rdf:type schema:Person
    81 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    82 schema:familyName Simeone
    83 schema:givenName Bruno
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
    85 rdf:type schema:Person
    86 sg:person.015045661577.05 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    87 schema:familyName Marchioro
    88 schema:givenName Paola
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015045661577.05
    90 rdf:type schema:Person
    91 sg:person.07721500366.17 schema:affiliation N037a522f1fb94a8bb6d4f2df98f026d2
    92 schema:familyName Jaumard
    93 schema:givenName Brigitte
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721500366.17
    95 rdf:type schema:Person
    96 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    97 https://doi.org/10.1007/978-1-4684-2001-2_9
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0020-0190(79)90002-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023830880
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0020-0190(80)90049-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032382216
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0020-0190(83)90033-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027487952
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0196-6774(86)90006-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010923276
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/s0304-0208(08)73112-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033206855
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1137/0205048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841334
    110 rdf:type schema:CreativeWork
    111 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    112 schema:name Dipartimento di Matematica, Università “La Sapienza”, Roma, Italy
    113 Dipartimento di Statistica, Probabilità e Statistica Applicata, Università “La Sapienza”, Roma, Italy
    114 rdf:type schema:Organization
     




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


    ...